堆排序

（1）堆排序是对简单选择排序的改进方法。堆排序的特点在于即使在最坏情况下，它的时间复杂度仍然为O(log2N)，而且只需要一个记录大小的辅助空间，即空间复杂度为O(1) 

（2）堆排序的算法过程描述：

① 建立一个初始堆。调整线性表L中的元素L[1]，L[2]，……，L[[N/2]]，使所有元素构成一个堆。这时L[1]为堆中关键字值最大的结点。

② 把堆中结点L[N]与L[1]交换，得到由L[1]，L[2]，……，L[N-1]构成的类堆。

③ 将类堆L[1]，L[2]，……L[N-1]转化为一个堆。

④ 重复步骤②，步骤③，直到整个线性表被排序完毕

（3）堆排序算法

void heapAdjust(int list[],int u,int v){
    int i=u,j,temp=list[i];
    j=2*i;
    while(j<=v){
        if(j
            j++;
        }
        if(temp
            list[i]=list[j];
            i=j;
            j=2*i;
        }else{
            break;
        }
    }
    list[i]=temp;
}
void heapSort(int list[],int n){
    int i=0;
    for(i=n/2;i>0;i--){
        heapAdjust(list,i,n);
    }
    for(i=n;i>1;i--){
        list[0]=list[1];
        list[1]=list[i];
        list[i]=list[0];
        heapAdjust(list,1,i-1);
    }
} 

（4）完整程序 

#include
#define N 20
int list[N+1];
void insertSort(int list[],int n){
    int i,j;
    for(i=2;i<=n;i++){
        list[0]=list[i];
        j=i-1;
        while(j>0&&list[0]
            list[j+1]=list[j];
            j--;
        }
        list[j+1]=list[0];
    }
}
void bubbleSort(int list[],int n){
    int i=1,j,t,flag=1;
    for(i=1;i
        flag=0;
        for(j=1;j<=n-1;j++){
            if(list[j]>list[j+1]){
                t=list[j];
                list[j]=list[j+1];
                list[j+1]=t;
                flag=1;
            }
        }
    }
}
void SelectSort(int list[],int n){
    int i,j,k,temp;
    for(i=1;i<=n-1;++i){
        k=i;
        for(j=i+1;j<=n;j++){
            if(list[j]             k=j;
        }
        if(i!=k){
            temp=list[i];
            list[i]=list[k];
            list[k]=temp;
        }
    }
} 
void Shellinsert(int list[],int dk,int n){
    int i,j;
    for(i=dk+1;i<=n;i++){
        if(list[i]
            list[0]=list[i];
            for(j=i-dk;j>0&&list[0]
                list[j+dk]=list[j];
            }
            list[j+dk]=list[0];
        }
    }
}
void ShellSort(int list[],int dlta[],int t,int n){
    int i,k;
    for(k=0;k
        Shellinsert(list,dlta[k],n);
    }
}
int Partition(int list[],int low,int high){
    int pivotkey;
    list[0]=list[low];
    pivotkey=list[low];
    while(low
        while(low=pivotkey){
            --high;
        }
        list[low]=list[high];
        while(low
            ++low;
        }
        list[high]=list[low];
    }
    list[low]=list[0];
    return low;
}
void QSort(int list[],int low,int high){
    int pivotloc,i,pivotkey;
    pivotkey=list[low];
    if(low
        pivotloc=Partition(list,low,high);
        QSort(list,low,pivotloc-1);
        QSort(list,pivotloc+1,high);
    }
}
void heapAdjust(int list[],int u,int v){
    int i=u,j,temp=list[i];
    j=2*i;
    while(j<=v){
        if(j
            j++;
        }
        if(temp
            list[i]=list[j];
            i=j;
            j=2*i;
        }else{
            break;
        }
    }
    list[i]=temp;
}
void heapSort(int list[],int n){
    int i=0;
    for(i=n/2;i>0;i--){
        heapAdjust(list,i,n);
    }
    for(i=n;i>1;i--){
        list[0]=list[1];
        list[1]=list[i];
        list[i]=list[0];
        heapAdjust(list,1,i-1);
    }
}
int main(){
    int i,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&list[i]);
    }
    //insertSort(list,n);
    //bubbleSort(list,n);
    //SelectSort(list,n);
    int dlta[3]={5,3,1};
    //ShellSort(list,dlta,3,n);
    //QSort(list,1,n);
    heapSort(list,n);
    for(i=1;i<=n;i++){
        printf("%d ",list[i]);
    } 
    return 0;
}

（5）堆排序初看排序效率不高，因为在堆排序过程中，关键字较大的结点先移到线性表左边的位置，最后又放在线性表右边的位置上。实验证明，当N较小时这个方法不适合，但当N较大时，堆排序算法效率较高，可达到仅次于快速排序的排序效率。