归并排序的平均时间复杂度为 O(nlogn)，最好情况和最坏情况也都为 O(nlogn)。归并排序的空间复杂度为 O(n)，是一种稳定排序算法。

6. 快速排序

快速排序的核心思想是选择一个轴值 pivot，将数组分为小于轴值的部分和大于轴值的部分，然后递归地对这两部分进行排序。轴值的选择会影响算法的效率，一般选取数组的中间点作为轴值。为了设计方便，会将轴值置于数组末端，待排好序后再移动到合适位置：

//partition函数将数组的l+1~r-1划分为两个以轴值为分界的部分，并返回轴值的下标（实际上该位元素与最后一位交换后才是真正的轴值下标）
int partition(int A[],int l,int r,int& pivot){  //l,r为A[]的左右范围，pivot为轴值
    do{
        while(A[++l]pivot));
        int tmp=A[r];
        A[r]=A[l];
        A[l]=tmp;
    }while(l=j)    return;
    int pivotindex=(i+j)/2;                 //选取轴值
    int pivot=A[pivotindex];
    A[pivotindex]=A[j];						//将轴值与末尾元素互换
    A[j]=pivot;
    pivotindex=partition(A,i-1,j,A[j]);     //将l+1~r-1按轴值分部，并返回待与轴值交换元素下标
    pivot=A[j];                             //轴值还在末尾等待交换
    A[j]=A[pivotindex];
    A[pivotindex]=pivot;
    qsort(A,i,pivotindex-1);
    qsort(A,pivotindex+1,j);
}

快速排序是迄今为止所有内排序算法中在平均情况下最快的一种，当每个轴值都把数组分成相等的两个部分时，整个算法的时间代价是Θ\ThetaΘ(nlogn)。快速排序的平均时间复杂度为 O(nlogn)，最好情况为 O(nlogn)，最坏情况为 O(n2)。快速排序的空间复杂度为 O(logn)，是一种不稳定排序算法。

7. 堆排序

堆排序是基于堆数据结构的排序算法，它利用最小堆的性质来实现对数组的排序：

class heap{
private:
    int* Heap;
    int maxsize;
    int n;
    void siftdown(int pos){
        while(!isLeaf(pos)){
            int j=leftchild(pos);       //下面j表示的是lc和rc中较小值的下标
            int rc=rightchild(pos);
            if((rc=n/2)&&(pos=0;i--){
            siftdown(i);
        }
    }
    void insert(const int& it){
        int curr=n++;
        Heap[curr]=it;
        while((curr!=0)&&(Heap[curr]

void inssort(int A[],int n){
    for(int i=1;i0;j--){
            if(A[j]maxA)	maxA=A[i];
		if(A[i]