数据结构－堆排序

 1 #include <stdio.h>
 2 #include "string.h"
 3 int length = 0;
 4 void swap(int array[], int i, int j)
 5 {
 6     int temp;
 7     temp = array[i];
 8     array[i] = array[j];
 9     array[j] = temp;
10 }
11 void adjustment(int array[], int i, int length)
12 {
13     int temp = array[i];
14     for(int k = i*2+1; k < length ; k = k*2+1)
15     {
16         //如果左节点小于右节点的话就让k指向有节点
17         if(k+1 < length && array[k] < array[k+1])
18         {
19             k++;
20         }
21         //这是我自己想出来的代码
22 //        if(array[k] > temp)
23 //        {
24 //            swap(array, i, k);
25 //        }
26 //        else
27 //        {
28 //            break;
29 //        }
30         //这是博客源代码
31         if(array[k] >temp)
32         {
33             array[i] = array[k];
34             i = k;
35         }
36         else
37         {
38             break;
39         }
40         array[i] = temp;
41     }
42 }
43 void sort(int array[])
44 {
45     //构建大顶堆
46     for(int i = length/2-1; i >= 0; i--)
47     {
48         adjustment(array, i, length);
49     }
50     //将堆顶元素和最后一个元素交换
51     for(int j = length-1; j >= 0; j--)
52     {
53         swap(array, 0, j); //将堆顶元素和最后一个元素交换
54         adjustment(array, 0, j);//重新对堆调整
55     }
56 }
57 int main() {
58     int array[] = {2,6,5,4,9,1,3,7,10};
59     length = sizeof(array)/ sizeof(int);
60     sort(array);
61     for(int i = 0; i < length; i++)
62     {
63         printf("%d ",array[i]);
64     }
65     return 0;
66 }