选择排序：

void Selection_Sort(ElementType A[], int N){    int i, MinPosition;    for (i = 0; i < N; i++) {        MinPosition = scanForMin(A, i, N-1);        //从A[i]到A[N-1]中找最小元        Swap(&A[i], A[MinPosition])    }}

　　关键是找最小元的一步 普通选择排序都看一遍 时间复杂度O(N^2)

　　可用最小堆来优化 使时间复杂度降为O(NlogN)

算法1：

void Heap_Sort(ElementType A[], int N){    BuildHeap(A);  //O(N)    for (i = 0; i < N; i++)        Tmp[i] = DeleteMin(A); //O(logN)    for (i = 0; i < N; i++)  //O(N)        A[i] = TmpA[i];}

　　T(N) = O(NlogN)

　　问题：需要额外O(N)空间 且复制元素需要时间

算法2：

　　

　　调成最大堆 每次把最大的放到最后位置 堆的规模减1 然后调整最大堆

　　定理：堆排序处理N个不同元素的随机排列的平均比较次数是 2NlogN - O(Nlog logN)

　　虽然堆排序给出了最佳平均时间复杂度 但实际效果不如用Sedgewick增量序列的Shell Sort

void Swap(ElementType *a, ElementType *b){    ElementType t = *a; *a = *b; *b = t;}void PercDown(ElementType A[], int p, int N){    int Parent, Child;    ElementType X;    X = A[p];    for (Parent = p; (Parent*2+1) < N; Parent = Child)    {        Child = Parent*2 + 1;        if ( (Child!= N-1) && (A[Child] < A[Child+1]) )            Child++;        if (X >= A[Child]) break;        else            A[Parent] = A[Child];    }    A[Parent] = X;}void HeapSort(ElementType A[], int N){    int i;    for (i = N/2-1; i >= 0; i--)        PercDown(A, i, N);   //建立最大堆    for (i = N-1; i > 0; i--) {        Swap(&A[0], &A[i]);        PercDown(A, 0, i);    }}

时间复杂度： 

　　平均O(Nlog2N) 最坏O(Nlog2N) 不稳定

PTA结果：