这是排序算法的最后一篇了,剩下归并排序、堆排序和快速排序了,关于各种排序算法的效率、适用场合和性能的分析留到下一篇再讲。
归并排序
归并排序是基于
归并操作的,归并操作的思想很简单,针对两个
已经排好序的有序序列:
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))。
未完,待续...
阅读(1103) | 评论(0) | 转发(0) |