排序算法二之堆排序与归并排序

堆排序

还记得上一次的数据结构文章——优先队列（堆）

吗？在那篇文章中，我们提到了大顶堆与小顶堆，并且说了优先队列出对顺序和元素的优先级有关系，今天我们说的两个算法中的堆排序，就是从优先队列而来的，既然优先队列每次出队的元素都是按元素优先级来的，那么，在排序算法中，我们不是可以将元素优先级设置为元素的大小吗——这就是我们上篇文章说提到的大顶堆与小顶堆。那么，堆排序实际很快就能写出来了，只是稍微改变而已，在例程中我们做的是大顶堆操作，然后每一次DeleteMax，就是将堆中最顶上的元素和最后一个元素进行交换，等到执行N - 1次后，我们发现实现堆结构的数组内的元素已经按从小到大的顺序排好了，具体过程如下：

堆排序代码

#define LeftChild(i) (2 * (i) + 1)

void PrecDown(ElementType A[], int i, int N) {
    int child;
    ElementType tmp;
    for(tmp = A[i];LeftChild(i)< N; i = child){
        child = LeftChild(i);
    if(child != N -1&& A[child +1]> A[child])
        child += 1;
    if(tmp < A[child])
        A[i] = A[child]
    else
        break;
    }
    A[i] = tmp;
}

void Swap(int *a, int *b) {
    int temp =*a;
    *a =*b;
    *b = temp;
}

void HeapSort(ElementType A[], int N) {
    int i;
    for(i = N /2; i >=0; i--){
        PrecDown(A, i, N);
    }
    for(i = N -1; i >0; i --){
        Swap(&A[0],&A[i]);
        PrecDown(A,0, i);
    }
}

归并排序

之前的一篇排序算法一之插入排序和希尔排序，我们介绍了排序算法的稳定性和那些排序算法是稳定的，这不，这次讲的归并排序，就是一个稳定的排序算法，现在我们来了解了解归并算法吧。

归并排序，实际上是合并两个已经按相同排序规则排序好的表，将它们合并到第三张表里面，因此，只需要一趟排序就可以完成。过程如下：我们创建第三张表C，然后开始对第一张表A、第二张表B的元素两两比较，首先比较第一张表和第二张表的首元素A1、B1，将两个中较小的（或较大）放入C表中成为C表的第一个元素C1，假设A1<B1，我们把A1放入C表的第一个元素位置，B1元素不放入C表，而是接着和A1的下一个元素进行比较。接着，我们再把A2元素和刚刚的B1元素进行比较，重复A1与B1比较的步骤……知道其中某一张表的所有元素先放入C表后，我们在把另一张表的剩余所有元素直接按序接在C表中当前最后一个元素的后面，接下来我们有图来展示下过程：

现在我们就给出代码吧：

void MSort(ElementType A[], ElementType 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(ElementType A[], int N) {
    ElementType *tmpArray;
    tmpArray = malloc(N * sizeof(ElementType));
    if(tmpArray !=NULL){
        MSort(A, tmpArray,0, N -1);
        free(tmpArray);
    }
    else
        return;
}

void Merge(ElementType A[], ElementType tmpArray[], int Lpos, int Rpos, int RightEnd) {
    int i, LeftEnd, NumElements, TmpPos;
    LeftEnd = Rpos - 1;
    TmpPos = Lpos;
    NumElements = RightEnd - Lpos + 1;
    while(Lpos <= LeftEnd && Rpos <= RightEnd) {
        if(A[Lpos]<= A[Rpos])
            tmpArray[TmpPos ++] = A[Lpos ++];
        else
            tmpArray[TmpPos ++] = A[Rpos ++];
    }
    while(Lpos <= LeftEnd)
        tmpArray[TmpPos ++] = A[Lpos ++];
    while(Rpos <= RightEnd)
        tmpArray[TmpPos ++] = A[Rpos ++];
    for(i =0; i < NumElements; i ++, RightEnd --)
        A[RightEnd] = tmpArray[RightEnd];
}