{"id":39,"date":"2016-10-15T02:39:04","date_gmt":"2016-10-15T02:39:04","guid":{"rendered":"http:\/\/www.haoyuan.info\/?p=39"},"modified":"2016-10-20T03:35:35","modified_gmt":"2016-10-20T03:35:35","slug":"%e5%a0%86%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=39","title":{"rendered":"\u5806\u6392\u5e8f"},"content":{"rendered":"

[hide]\u4e00\u4e2a\u5173\u4e8e\u5806\u6392\u5e8f\u5728OJ\u91cc\u9762\u51fa\u73b0\u7684\u5e94\u7528\u3002<\/p>\n

 <\/p>\n

[code lang=”c”]
\n#include <stdio.h>
\n#include <stdlib.h><\/p>\n

void swap(int* a, int* b) {
\n\tint temp = *b;
\n\t*b = *a;
\n\t*a = temp;
\n}<\/p>\n

void max_heapify(int arr[], int start, int end) {
\n\t\/\/\u5efa\u7acb\u7236\u7bc0\u9ede\u6307\u6a19\u548c\u5b50\u7bc0\u9ede\u6307\u6a19
\n\tint dad = start;
\n\tint son = dad * 2 + 1;
\n\twhile (son <= end) { \/\/\u82e5\u5b50\u7bc0\u9ede\u6307\u6a19\u5728\u7bc4\u570d\u5167\u624d\u505a\u6bd4\u8f03
\n\t\tif (son + 1 <= end && arr[son] < arr[son + 1]) \/\/\u5148\u6bd4\u8f03\u5169\u500b\u5b50\u7bc0\u9ede\u5927\u5c0f\uff0c\u9078\u64c7\u6700\u5927\u7684 son++; if (arr[dad] > arr[son]) \/\/\u5982\u679c\u7236\u7bc0\u9ede\u5927\u65bc\u5b50\u7bc0\u9ede\u4ee3\u8868\u8abf\u6574\u5b8c\u7562\uff0c\u76f4\u63a5\u8df3\u51fa\u51fd\u6578
\n\t\t\treturn;
\n\t\telse { \/\/\u5426\u5247\u4ea4\u63db\u7236\u5b50\u5167\u5bb9\u518d\u7e7c\u7e8c\u5b50\u7bc0\u9ede\u548c\u5b6b\u7bc0\u9ede\u6bd4\u8f03
\n\t\t\tswap(&arr[dad], &arr[son]);
\n\t\t\tdad = son;
\n\t\t\tson = dad * 2 + 1;
\n\t\t}
\n\t}
\n}<\/p>\n

void heap_sort(int arr[], int len) {
\n\tint i;
\n\t\/\/\u521d\u59cb\u5316\uff0ci\u5f9e\u6700\u5f8c\u4e00\u500b\u7236\u7bc0\u9ede\u958b\u59cb\u8abf\u6574
\n\tfor (i = len \/ 2 – 1; i >= 0; i–)
\n\t\tmax_heapify(arr, i, len – 1);
\n\t\/\/\u5148\u5c07\u7b2c\u4e00\u500b\u5143\u7d20\u548c\u5df2\u6392\u597d\u5143\u7d20\u524d\u4e00\u4f4d\u505a\u4ea4\u63db\uff0c\u518d\u5f9e\u65b0\u8abf\u6574\uff0c\u76f4\u5230\u6392\u5e8f\u5b8c\u7562
\n\tfor (i = len – 1; i > 0; i–) {
\n\t\tswap(&arr[0], &arr[i]);
\n\t\tmax_heapify(arr, 0, i – 1);
\n\t}
\n}<\/p>\n

int main() {
\n int number,ci;
\n scanf("%d",&number);
\n int arr[number+1];
\n for(ci=0;ci<number;ci++)
\n {
\n scanf("%d",&arr[ci]);
\n }
\n scanf("%d",&arr[number]);
\n\tint len = (int) sizeof(arr) \/ sizeof(*arr);
\n\theap_sort(arr, len);
\n\tint i;
\n\tfor (i = 0; i < len; i++){
\n if(i==len-1)
\n {
\n printf("%d\\n",arr[i]);
\n return 0;
\n }
\n\t\tprintf("%d ", arr[i]);
\n\t}
\n\tprintf("\\n");
\n\treturn 0;
\n}<\/p>\n

[\/code][\/hide]<\/p>\n","protected":false},"excerpt":{"rendered":"

[hide]\u4e00\u4e2a\u5173\u4e8e\u5806\u6392\u5e8f\u5728OJ\u91cc\u9762\u51fa\u73b0\u7684\u5e94\u7528\u3002   [code lang=”c&#82 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[1],"tags":[],"class_list":["post-39","post","type-post","status-publish","format-standard","hentry","category-1"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-D","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/39","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=39"}],"version-history":[{"count":2,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/39\/revisions"}],"predecessor-version":[{"id":59,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/39\/revisions\/59"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=39"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=39"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=39"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}