C/C++ 数组排序（平均时间复杂度 O（nlogn））归并、快速、堆、希尔之堆排序

堆排序：

给定一个int数组A以及大小n，请返回排序后的数组；

核心思想：

1、将数组调整为大堆项。

1.1、构造大堆项，需要从第i=n/2（也就是数组的一半）元素到第一个元素依次调整，倒着;

（为啥要从n/2开始呢？因为对于二叉树，当前索引的2倍是该索引的左子树索引，2倍+1是右子树索引）

1.2、然后分别与A[i]的左右子树比大小，谁大，就把它的值放到A[i]上进行对调;

1.3、依次向上走，直到i=0;这样A[0]就是最大值。

2、将大堆项的堆顶元素与最后位置对调，每次一个元素到达最终位置n，对前n-1个继续。

3、递归调用，共重复n-1次。

代码：

class HeapSort {  
public:  
    int* heapSort(int* A, int n) {  
        // write code here  
        //对于一个int数组，请编写一个堆排序算法，对数组元素排序。  
    //给定一个int数组A及数组的大小n，请返回排序后的数组。  
        //1. 将数组调整成大顶堆  
        //2. 将大顶堆的对顶元素与最后位置的元素对调，每次有一个元素到最终位置  
        //3. 将未排序的元素重复步骤1、2,共重复步骤1、 2 的次数为n-1次  
        heapProcess(A, n-1);  
          
        return A;  
    }  
      
    void heapProcess(int *A, int n){  
        if(n <= 0)  
            return;  
        heapAdjust(A, n);  
          
        int a;  
        a = A[n];  
        A[n] = A[0];  
        A[0] = a;  
          
        heapProcess(A, n-1);  
    }  
      
    //大顶堆调整，从第n/2至第一个元素依次调整  
    void  heapAdjust(int* A, int n){  
        int i = n/2;  
        int a;  
        //换位，为啥要2n+1,2n+2,为了弥补树是从0开始而不是从1开始。
        while(i>=0){  
            if(2*i+1 <= n && A[i] < A[2*i+1]){  
                a = A[i];  
                A[i] = A[2*i+1];  
                A[2*i+1] = a;  
            }  
              
            if(2*i+2 <= n && A[i] < A[2*i+2]){  
                a = A[i];  
                A[i] = A[2*i+2];  
                A[2*i+2] = a;   
            }  
              
            i--;  
        }  
    }  
};

main调用：

#include <iostream>
using namespace std;

int main(){
 int AAA[]={1,3,6,9,2,5,4,8,7};
 HeapSort H;
 int *b=H.heapSort(AAA,9);
 for(int i=0;i<9;i++){
     cout<<b[i]<<endl;
 }
 
 return 0;
}