（一） 堆排序：由于优先队列可以花费O(NlogN)时间的排序，基于该想法的排序称之为堆排序。建立N个元素的二叉堆，基本上花费的时间为O(N)，再执行N次删除操作。按照顺序呢，最小的元素先离开该堆。通过将这些元素记录到第二个数组然后在将数组拷贝回来，就可得到N个元素的排序。由于每个Delete操作花费时间。
该算法的主要问题在于它使用了一个附加的数组，因此，存储需求增加了一倍，注意，将第二个数组拷贝回第一个数组的额外时间消耗只是O(N)，这不可能显著影响运行时间问题，这只是一个空间问题。
避免使用第二个数组的聪明的做法是：在每次delete之后，堆缩小了1，因此，位于堆中最后的单元可以用来存放刚刚删去的元素，使用这种策略，在最后一次delete之后，该数组将以递减的顺序包含这些元素。若果想使这些元素排成典型的递增的顺序，我们可以改变序的特性，是父节点的元素大于孩子节点的元素。
在实现的过程中，我们使用一个大顶堆（MaxHeap），但是由于速度原因避免了实际上的ADT（每一件事都是在一个数组中试实现的）。第一步，一线性时间建立一个堆。然后通过将堆中的最后元素与第一个元素进行交换，缩减堆的大小，并进行下滤，来实行 N - 1 次delete操作。
堆排序是一种非常稳定的算法，它平均使用的比较次数比最坏情形下的略少。
//4. 堆排序（1）【只是用一个数组，而不必建立一个堆的数据结构（使用大顶堆）：从小到大排列的】#define LChild(i) (i * 2 + 1) //去 i 节点的左孩子（因为cichu）
//建立一个大顶堆void BuildMaxHeap(int A[], int i, int N){ int Child; int tmp; //临时变量，用于存放父节点 i 的值 for(tmp = A[i]; LChild(i) < N; i = Child) //i 为父节点，LChild为其孩子节点 { Child = LChild(i); //下滤过程 if(Child != N-1 && A[Child] < A[Child + 1]) //父节点 i 与其左右孩子进行比较取最大者 Child++; if(tmp < A[Child]) A[i] = A[Child]; //使用大的孩子节点替代父节点 else break; } A[i] = tmp; //填补空穴}
//（2）建立一个小顶堆.最后得到的结果是从大到小排列的void BuildMinHeap(int A[], int i, int N){ int Child; int tmp; for(tmp = A[i]; LChild(i) < N; i = Child) { Child = LChild(i); if(Child != N -1 && A[Child] > A[Child + 1]) //寻找 i 节点的最小孩子，并将其替换 i 处的元素 Child++; if(tmp > A[Child]) //若父节点 i 大于最小孩子，则使用它的最小孩子替换 i 处的元素 A[i] = A[Child]; else break; } A[i] = tmp; //填补空穴}
void Swap(int *a, int *b){ int tmp; tmp = *a; *a = *b; *b = tmp;}
void HeapSort(int A[], int N){ int i; for(i = N / 2; i >= 0; i--) //注意 i 的起始位置 { //BuildMaxHeap(A, i, N); BuildMinHeap(A, i, N); } for(i = N - 1; i > 0; i--) { Swap(&A[0], &A[i]); //使用一个数组 //BuildMaxHeap(A, 0, i); BuildMinHeap(A, 0, i); }}
（二） 归并排序：归并排序以O(NlogN)最坏情形的时间运行，而且它使用的比较次数几乎是最优的，是递归算法的一个很好的实例。
这个算法的基本操作是合并两个已经排好序的表，由于这两个表已经排好序，所以若将输出放到第三个表中时，则该算法可以同过对这两个表的一次排序来完成。基本的排序算法是取两个排序数组 A，B，一个输出数组 C，以及三个计数器 Aptr，Bptr，Cptr分别指向三个数组的首元素。A[Aptr] 和 B[Bptr]中的较小的元素被存放到C[Cptr]中，相关计数器向下移动一个位置，当一个表用完的时候，将另一个表的剩余元素拷贝到C 数组中。
合并两个已经排好序的表所用的时间显然是线性的，因为进行了N - 1次比较，其中N是数组元素的个数。归并算法很容易描述，当N = 1时，只有一个元素需要排序，结果是显然的。否则，递归的将前半部分和后半部分的数据，各自进行归并排序。得到排序后的两部分数据，然后使用上述提到的合并算法对两个一排好序的表进行合并。
该算法是经典的分治策略：它将问题分成一些小的问题，然后递归的求解，而治的阶段是将分的阶段所得到的各个答案进行修补到一起。分治策略是递归非常有力的用法。
//归并排序（分治策略）:递归//参数：Lpos：左半部分数组的第一个元素，Rpos是右半部分数组的第一个元素，Rend是右半部分数组的最后一个元素
void Merge(int A[], int TmpArray[], int Lpos, int Rpos, int Rend){ int i, Lend, NumElements, TmpPos; //初始化
Lend = Rpos -1; // Lend是左半部分数组的最后一个元素 NumElements = Rend - Lpos + 1; //数组的总长度 TmpPos = Lpos; //TmpArray是一个临时数组，用于存放已经排好序的元素 while(Lpos <= Lend && Rpos <= Rend) { if(A[Lpos] <= A[Rpos]) TmpArray[TmpPos++] = A[Lpos++]; else TmpArray[TmpPos++] = A[Rpos++]; } while(Lpos <= Lend) //左半部分数组有剩余 TmpArray[TmpPos++] = A[Lpos++]; while(Rpos <= Rend) //右半部分数组有剩余 TmpArray[TmpPos++] = A[Rpos++];
for(i = 0; i < NumElements; i++, Rend--) //将临时数组中的元素存放到原数组中 A[Rend] = TmpArray[Rend];}
void MSort(int A[], int TmpArray[], int Left, int Right){ int Center; if(Left < Right) { Center = (Left + Right) / 2; //分界点 MSort(A, TmpArray, Left, Center); //分（左） MSort(A, TmpArray, Center + 1, Right); Merge(A, TmpArray, Left, Center + 1, Right); //合 }
}
void MergeSort(int A[], int N){ int *TmpArray; // 创建一个临时数组 TmpArray = new int[N]; if(TmpArray != NULL) { MSort(A, TmpArray, 0, N - 1); free(TmpArray); } else throw exception("No space for tmp array!");}
虽然归并排序的时间复杂度为O(NlogN)，但它很难用于主存排序，主要问题在于合并两个排序表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组，再从临时数组中拷贝回来这样一些附加工作，其结果严重放慢的排序的速度。这种拷贝可以通过在递归交替层次审慎的交换 A 和 TmpArray 的角色得到避免。对于重要的内部排序而言人们还是选择快速排序。
//各种排序算法#includeusing namespace std;typedef int ElemType;//4. 堆排序（1）【只是用一个数组，而不必建立一个堆的数据结构（使用大顶堆）：从小到大排列的】#define LChild(i) (i * 2 + 1) //去 i 节点的左孩子（因为cichu）void BuildMaxHeap(int A[], int i, int N){ int Child; int tmp; //临时变量，用于存放父节点 i 的值 for(tmp = A[i]; LChild(i) < N; i = Child) //i 为父节点，LChild为其孩子节点 { Child = LChild(i); //下滤过程 if(Child != N-1 && A[Child] < A[Child + 1]) //父节点 i 与其左右孩子进行比较取最大者 Child++; if(tmp < A[Child]) A[i] = A[Child]; //使用大的孩子节点替代父节点 else break; } A[i] = tmp; //填补空穴}//（2）建立一个小顶堆.最后得到的结果是从大到小排列的void BuildMinHeap(int A[], int i, int N){ int Child; int tmp; for(tmp = A[i]; LChild(i) < N; i = Child) { Child = LChild(i); if(Child != N -1 && A[Child] > A[Child + 1]) //寻找 i 节点的最小孩子，并将其替换 i 处的元素 Child++; if(tmp > A[Child]) //若父节点 i 大于最小孩子，则使用它的最小孩子替换 i 处的元素 A[i] = A[Child]; else break; } A[i] = tmp; //填补空穴}void Swap(int *a, int *b){ int tmp; tmp = *a; *a = *b; *b = tmp;}void HeapSort(int A[], int N){ int i; for(i = N / 2; i >= 0; i--) //注意 i 的起始位置 { //BuildMaxHeap(A, i, N); BuildMinHeap(A, i, N); } for(i = N - 1; i > 0; i--) { Swap(&A[0], &A[i]); //使用一个数组 //BuildMaxHeap(A, 0, i); BuildMinHeap(A, 0, i); }}//归并排序（分治策略）:递归//参数：Lpos：左半部分数组的第一个元素，Rpos是右半部分数组的第一个元素，Rend是右半部分数组的最后一个元素void Merge(int A[], int TmpArray[], int Lpos, int Rpos, int Rend){ int i, Lend, NumElements, TmpPos; //初始化 Lend = Rpos -1; // Lend是左半部分数组的最后一个元素 NumElements = Rend - Lpos + 1; //数组的总长度 TmpPos = Lpos; //TmpArray是一个临时数组，用于存放已经排好序的元素 while(Lpos <= Lend && Rpos <= Rend) { if(A[Lpos] <= A[Rpos]) TmpArray[TmpPos++] = A[Lpos++]; else TmpArray[TmpPos++] = A[Rpos++]; } while(Lpos <= Lend) //左半部分数组有剩余 TmpArray[TmpPos++] = A[Lpos++]; while(Rpos <= Rend) //右半部分数组有剩余 TmpArray[TmpPos++] = A[Rpos++]; for(i = 0; i < NumElements; i++, Rend--) //将临时数组中的元素存放到原数组中 A[Rend] = TmpArray[Rend];}void MSort(int A[], int TmpArray[], int Left, int Right){ int Center; if(Left < Right) { Center = (Left + Right) / 2; //分界点 MSort(A, TmpArray, Left, Center); //分（左） MSort(A, TmpArray, Center + 1, Right); Merge(A, TmpArray, Left, Center + 1, Right); //合 }}void MergeSort(int A[], int N){ int *TmpArray; // 创建一个临时数组 TmpArray = new int[N]; if(TmpArray != NULL) { MSort(A, TmpArray, 0, N - 1); free(TmpArray); } else throw exception("No space for tmp array!");}int main(){ int arr[10] = {5, 2, 8, 6, 3, 1, 7, 9, 4, 10}; HeapSort(arr, 10); for(int i = 0; i < 10; i++) cout << arr[i] << " "; cout << endl; system("pause"); return 0;}