堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

 

算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

 

复杂程度

时间复杂度O(nlog2n)                 空间复杂度O(1)

 

代码实现

void Heapify(int *arr, int m, int size) 

{ 

    int i, tmp; 

    tmp = arr[m]; 

    for (i = 2 * m; i <= size; i *= 2) { 

        if (i + 1 <= size && arr[i] < arr[i+1]) { 

            i++; 

        } 

        if (arr[i] < tmp) { 

            break; 

        } 

        arr[m] = arr[i]; 

        m = i; 

    } 

    arr[m] = tmp; 

} 

 

void BulidHeap(int *arr, int size)

{ 

    int i; 

    for (i = n / 2; i > 0; i--) { 

        Heapify(arr, i, size); 

    } 

} 

   

void swap(int *arr, int i, int j) 

{ 

    int tmp; 

    tmp = arr[i]; 

    arr[i] = arr[j]; 

    arr[j] = tmp; 

} 

 

void HeapSort(int *arr, int size) 

{ 

    int i; 

    BulidHeap(arr, size); 

    for (i = size; i > 1; i--) { 

        swap(arr, 1, i);

        Heapify(arr, 1, i - 1);

    } 

}