经典排序算法归纳笔记(3)

    这是排序算法的最后一篇了，剩下归并排序、堆排序和快速排序了，关于各种排序算法的效率、适用场合和性能的分析留到下一篇再讲。

归并排序
   归并排序是基于归并操作的，归并操作的思想很简单，针对两个已经排好序的有序序列：
   1、申请一块额外的存储空间，空间的大小等于两个待操作序列长度之和；
   2、设定两个指针，初始位置分别指向两个有序序列的开始处；
   3、比较两个指针所指元素的值，较小者放到合并空间里，同时指针向后移动；
   4、重复步骤3直到某个指针达到序列末尾；
   5、如果另外一个序列的指针为到达末尾，则将该序列里剩下的元素拷贝到合并空间的尾部。

   这便是归并操作的核心思想，其归并过程如下：

   我们看到一趟归并操作，要求参与归并的序列必须有序，如果参与归并操作的两个序列(即我们常见的两路归并)长度分别是M和N，则还需要额外M+N的辅助存储空间。归并排序的基本操作就是归并操作，所以归并排序其实是“分治策略”的第一个典型应用。将待排序序列拆分成两个等长序列，然后将每个子序列继续拆分，直到最后的子序列长度为1为止。然后对拆分后的子序列两两执行归并操作，最后就达到了归并排序的目的。所以说归并排序算法分两步：第一步是拆分，第二步是归并。还是以前面见到过的测试序列A={6,3,1,9,2,5,8,7,4}为例，先看一下其拆分过程：

   待排序最终被拆分成长度为1的子序列，然后对这些子序列两两执行归并操作。根据上述归并操作的思想，我们可以很容易写出归并操作的核心代码：

int merge_ops(int a[],int alen,int b[],int blen){
        int i,j,k,len=alen+blen;
        int ele_size = sizeof(int);
        int *tmp = (int*)malloc(ele_size*len);              //为归并后的结果申请临时存储空间
        if(NULL == tmp){
            perror("Error!can't alloc mem!");
            return -1;
        }

        memset(tmp,0,ele_size*len);                         //清空临时缓冲区

        i=j=k=0;
        while(i<alen && j<blen){
                tmp[k++] = ((a[i]<b[j]) ? a[i++]:b[j++]);  //执行归并过程
        }

        //将某一序列的剩余元素追加到归并后的存储空间里(如果有的话)
        if(i>=alen && j<blen){
                memcpy(tmp+k,b+j,ele_size*(blen-j));
        }
        if(j>=blen && i<alen){
                memcpy(tmp+k,a+i,ele_size*(alen-i));
        }

        memcpy(a,tmp,ele_size*len);
        free(tmp);
        tmp = NULL;
        return 0;
}

    可以看到，上述归并操作的代码逻辑并不复杂，接下来我们需要完成归并排序的另一项工作，那就是拆分。我们要将待排序序列不断拆分，最终变成一个个长度为1的子序列，用于实现这个拆分过程最好的办法就是递归。因此，拆分的递归代码如下：

int merge(int a[],int len){
    if(len == 1){          //当子序列长度为1时则停止拆分
         return 0;
    }

    //拆分的过程
    if(merge(a,len/2)<0)
        return -1;
    if(merge(a+len/2,len-len/2)<0)
        return -1;

    //归并的过程
    return merge_ops(a,len/2,a+len/2,len-len/2);
}

    归并排序的效率还是蛮高的，它包含了“拆分”和“归并”两个过程。对于长度为n的待排序序列而言，将其拆分成长度是1的子序列时，如果拆分每一个元素所需要的时间为固定值C，那么拆分n个元素的时间总和就是Cn。在归并过程中，我们是在深度为log(n)+1的二叉树上执行的，二叉树每一层上的元素个数都是相同的，同样地，如果归并一个元素需要的时间为P，那么归并n个元素需要的时间总和就是Pn，即每一层都需要Pn的时间，所以归并log(n)+1层就需要Pn(log(n)+1)的时间。最后归并排序总耗费的时间：
T(n)=Cn+Pn(log(n)+1)=Pn*log(n)+(C+P)n，取C和P中较大者，假如记作M，则T(n)=Mn*log(n)+Mn。相比于nlog(n)来说，常数M和Mn可以忽略不计，所以可以得到归并排序的时间复杂度为O(nlog(n))。

堆排序
   排序算法里的堆和计算机进程地址空间里的堆并不是一个概念。堆又分二叉堆和N叉堆，其中二叉堆比较常见(目前我们只讨论这种，后面我们提到堆时默认情况下都指的是二叉堆)，是一个类似于完全二叉树的数据结构。堆排序主要是借助堆这种数据结构来实现的排序算法。堆的主要特性就是：父节点的值总是大于(或者小于)等于任意一个子节点的值。

   我们将父节点的值总是大于等于任意一个子节点的值的堆叫做大堆(或者大根堆)；同样地，父节点的值总是小于等于任意一个子节点的值的堆叫做小堆(或者小根堆)。

   通常情况下，堆都是用一维数组进行存储。编号为i的节点，其左子节点在数组中的下标为2×i+1，右子节点的下标为2×i+2；编号为i的子节点，其父节点的标号为(i-1)/2取整。例如：A={6,3,1,9,2,5,8,7,4}

   所以我们看到，堆排序的核心点是如何建立一个堆，这方面在STL里已经有很好的封装和实现了。当然，这里我们不是拿来主义，如果自己不对算法、原理本身进行研究，总感觉雾里看花似的。因为我是进行升序排列，所以需要建大根堆(小根堆原理一样)。可能有人会觉得应该建立小根堆才对，因为我们的堆是借助数组存储的，不使用树形结构，所以当堆调整成大根堆之后，将堆的根部元素依次和后面的叶子节点进行交换。然后再把堆调整成大根堆，依次循环下去，直到堆里仅剩一个元素为止。这样堆排序就完成了，且是原地排序，空间复杂度为O(1)。以上面的序列A为例，先看一下将其调整成大根堆的过程：

   如果序列的长度为n则我们需要从编号为(n/2)-1的元素开始调整，直到编号为0。因为对于编号为i(注意数组小标是i从0开始编号)的节点，其子节点的编号需要满足2*i+1    第一步时，index=3，所以其左右子节点的编号分别为7和8，在左右子节点a[7]和a[8]里找一个较大者，然后和a[3]进行比较。发现a[3]已经是三个参与比较的值中最大的了，因此这一步不用调整，index减1，后执行第二步，如下：

   如上所示，第二步时index=2，在根节点和两个子节点之间进行比较，将最大值交换到根节点上，如右所示；

   如上所示，第三步时index=1，最大值其左子节点a[3]=9，调整后的结果如右所示。节点a[1]=3的值“下沉”后我们发现它打破了原来左下角那个二叉树的平衡，所以接下来需要对其重新调整，使它满足大根堆的特性，过程如第四步所示：

   第四步调整时，index的值并没有改变，而是对index的左子节点所表示的二叉树进行了调整。当然，如果左子节点的任意一个子节点还是一棵二叉树，则需要一直递归调整下去，直到不需要调整或者遇到叶子节点为止。

    第五步时，index=0，调整后的结果如右所示。同样地，我们发现，根节点的左子节点“下沉”后也破坏原有二叉树的平衡性，因此需要继续调整：

    到此为止，我们的大根堆就算建立好，即任意一个节点如果有子节点，则根节点的值大于等于其左右子节点的值。
   根据上述建堆的过程，我们可以用递归算法来实现，但递归不方便理解，所以先看一个非递归的建堆过程：

//取得节点编号为i的左子节点的编号
int leftChildIndex(int i){
        return (2*i+1);
}

//取得节点编号为i的右子节点的编号
int rightChildIndex(int i){
        return (2*i+2);
}

//交换两个数
void swap(int *a,int *b){
        int t;
        t = *a;
        *a = *b;
        *b = t;
}

/××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××
 功能描述：AdjustHeap用于在堆里对编号为i的节点进行调整，使其满足大根堆的特性
 输入参数:
          a  ：待排序的序列；
          len：待排序序列长度；
          i  ：要调整的节点编号
 输出参数：无
 返 回 值：无
 ××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××/
void AdjustHeap(int a[],int len,int i){
        int left,right,bigger;
        left = leftChildIndex(i);
        right = rightChildIndex(i);

        //如果i节点左右子节点编号均未越界才执行此循环
        while(left<len || right<len){
            //如果右子节点编号未越界，则左子节点的下标也一定不会越界
            if(right<len){
                bigger = ((a[left]>a[right])?left:right);  //在左右子节点里找出较大者，将其编号用bigger标记
            }else if(left<len){
                bigger = left;                           //如果右子节点越界，但左子节点未越界，则直接将左子节点标记为较大者
            }else{
                break;                                  //否则的话，说明节点i是叶子节点，直接退出
            }

            //如果编号为i的根节点的值，小于从其左右子节点里选出来的较大的值，则进行交换
            if(a[bigger]>a[i]){
                swap(&a[i],&a[bigger]);

                i = bigger;             /*
                                         交换完成后，用i标记新的较大者，即将i记为新的根节点，然后取其左右子节点重复迭代调整
                                         如果把这个步骤改成递归算法，其实也不复杂
                                         */
                left = leftChildIndex(i);
                right = rightChildIndex(i);
            }else
                break;
        }
}
/*******************************************************
 功能描述：BuildHeap对长度为len的无序列a，将其构建成一个大根堆
 输入参数：
            a ：待排序的无序序列首地址
            len：无序序列的长度
 输出参数：无
 返 回 值：无
 *******************************************************/
void BuildHeap(int a[],int len){
     int i;
     for(i=len/2-1;i>=0;i--){    //注意前面分析的为什么要从编号为n/2-1的元素开始依次递减进行调整
         AdjustHeap(a,len,i);
     }
}

   当建好堆之后，堆排序的第一步就完成了。第二步就是不断的将堆的根元素交换到数组的末尾，然后重新再将堆调整成大根堆，并继续将堆的根元素继续和一维数组倒数第二个位的元素进行交换。一直这样下去，直到堆里剩下一个元素为止。还是看过程，下面是我们通过调用BuildHeap()将序列A建成的大根堆：

   我们将堆根元素和最后一个叶子元素4进行交换：

   因为此时，数组中的最后一个元素即堆的最末尾一个叶子元素已经被固定了，就相当于已经排好序了，所以在调整剩下来的大根堆时，序列的总长度要减1，即len=len-1，然后从堆的根元素开始调整，重新将其调整成大根堆，过程如下：

   然后再继续调整大根堆剩下来的部分，和上面的调整、排序流程是一模一样地：

   根据以上这个执行流程，现在我们就可以写出堆排序的核心代码了，非常简单、明了：

void heap_sort(int a[],int len){
        int i;
        BuildHeap(a,len);                //建堆

        while(--len > 0){                //如果堆里仅剩下一个元素则停止排序
                swap(&a[0],&a[len]);     //从后向前，将堆的根节点和数组尾部依次执行交换
                AdjustHeap(a,len,0);     //交换完成后，再以堆的根节点作为参照，将堆重新调整成大根堆
        }
}

   堆排序的时间主要包含两部分：“建堆的时间”+“排序时调整堆的之间”。建堆和调整堆时我们都调用AdjustHeap()函数，这个函数会将根节点向下沉，且节点下沉的深度不会超过二叉树的深度，即log(n)+1，因此AdjustHeap()函数的时间复杂度为O(log(n))。在建堆的时候，我们一共执行了n/2-1次，也就是说调用了n/2-1次AdjustHeap()函数，还不明白这个n/2-1是如何来的童鞋强烈建议从头再认真、仔细看一遍。最后我们可以得出建堆的时间是(n/2-1)×log(n)，即建堆的时间复杂度为O(nlog(n))。
   那么堆排序的时候，根元素依次和叶子节点进行交换的时间为O(1)，主要的时间开销还在交换完成后重新调整堆上面。堆排序时一共需要交换n-1，也就是所执行过n-1次AdjustHeap()，所以在进行堆排序时所耗费的时间为(n-1)×log(n)，即排序时的时间复杂度同样为O(nlog(n))。因此，堆排序总的时间复杂度为O(nlog(n))。


快速排序
   快速排序本质上其实是对冒泡排序的一种改进，它和归并排序同样都是“分治策略”的一种典型应用。快速排序也分两个步骤：第一步，现将待排序序列依次拆分成子序列，然后在每个子序列上执行下述操作：
   1、两个指针分别指向序列的头和尾，且定义一个关键参考值=头指针所指向的元素的值；
   2、如果尾指针所指的元素值比头指针所指的元素值大，则尾指针向前移动，头指针不动；
   3、继续步骤2，如果尾指针所指的元素小于头指针所指的元素，且头、尾指针没有相遇，则将尾指针指向的元素值赋值给头指针所指向的元素值，同时头指针开始向头移动，尾指针不动；
   4、继续执行步骤3，如果头、尾指针相遇则程序停止，否则如果满足条件2则只习惯步骤2，否则继续执行步骤3.
   这样一趟快速排序下来后，所有比较关键参考值小得元素都在其左边，所有比它大的元素都在其右边了。然后在以关键参考值所在的位置为分界线，在分别对其左边和右边两个子序列重复执行这个过程，直到最后所有子序列的长度为1则停止。

    还是看一下序列A={6,3,1,9,2,5,8,7,4}的一趟快速排序过程：

   初始时我们选择key=a[low]=6作为关键参考元素，low指向a的头部，hight指向数组a的尾部，从后向前开始。
   第1步时，由于key>a[high]，所以a[low]=a[high]，然后low++；
   第2步时，由于a[low]    第3步和第2步一样；
   第4步时，a[low]>key，则执行a[high]=a[low]，然后high--；
   ... ... 
   这样一直下去直到第11步，当low和high相遇就停止，最后将a[low]=key，同时以low(或者以high也可以)为分界线对它的左右两个子序列重复执行刚才的操作，直到序列长度为1则停止。

   所以，我们现在可以写出一次快速排序的核心代码了：

int partoff(int a[],int low,int high)
{
    int key = a[low];   //取a[low]为关键参考元素
    while(low<high)
    {
        while(low<high&&key<=a[high])       //从后向前找第一个比key小的元素
              high--;
        if(low<high)
              a[low++] = a[high];          //找到后执行一次赋值，然后开始从前向后找

        while(low<high && key >= a[low])  //从前先后找第一个比key大的元素
              low++;
        if(low<high)
              a[high--] = a[low];        //找到后也执行一次赋值，然后再从后向前找
    }

    //如果low和high相遇，则退出上面的while循环，将key安放在low所指定的位置上，并返回low用于下一次拆分子序列时当参考定标
    a[low] = key;
    return low;
}

    整个快速排序的过程就是不断调用上述函数的过程，那么采用递归的算法就很容易实现整个快速排序的过程了：

void quick_sort(int a[],int low,int high)
{
    int index=0;
    if(low<high)
    {
        index = partoff(a,low,high);
        quick_sort(a,low,index-1);
        quick_sort(a,index+1,high);
    }
}

   快速排序是目前已知的内部(后面会解释内部排序)排序中效率比较高的排序算法。待排序序序列最终被拆分成深度为log(n)+1的二叉树，和前面的堆排序一样。
   第一次拆分时，总共的执行时间是Cn(C为固定的单位时间常数)；第二次拆分时，每个子序列的执行时间为Cn/2，一共两个子序列，则总的执行时间是Cn/2+Cn/2=Cn；第三次拆分时，总时间时Cn/4+Cn/4+Cn/4+Cn/4+=Cn，以此类推，总共拆分了log(n)次，所以快速排序最终的时间损耗为Cn×log(n)，也就是说快速排序的时间复杂度为O(nlog(n))。
   未完，待续...