首页 > 海文新闻 > 面试过程中常用的排序算法汇总(二)

面试过程中常用的排序算法汇总(二)

2017年10月26日10:51:51来源:海文国际         78
分享到:

归并排序

归并排序是另一种不同的排序方法,因为归并排序使用了递归分治的思想,所以理解起来比较容易。其基本思想是,先递归划分子问题,然后合并结果。把待排序列看成由两个有序的子序列,然后合并两个子序列,然后把子序列看成由两个有序序列。。。。。倒着来看,其实就是先两两合并,然后四四合并。。。最终形成有序序列。空间复杂度为O(n),时间复杂度为O(nlogn)。

举个栗子:

面试过程中常用的排序算法汇总(二)

实现代码:

/***@Description:归并排序算法的实现*@author王旭*/publicclassMergeSort{publicstaticvoidmergeSort(int[]arr){mSort(arr,0,arr.length-1);}/***递归分治*@paramarr待排数组*@paramleft左指针*@paramright右指针*/publicstaticvoidmSort(int[]arr,intleft,intright){if(left>=right)return;intmid=(left+right)/2;mSort(arr,left,mid);//递归排序左边mSort(arr,mid+1,right);//递归排序右边merge(arr,left,mid,right);//合并}/***合并两个有序数组*@paramarr待合并数组*@paramleft左指针*@parammid中间指针*@paramright右指针*/publicstaticvoidmerge(int[]arr,intleft,intmid,intright){//[left,mid][mid+1,right]int[]temp=newint[right-left+1];//中间数组inti=left;intj=mid+1;intk=0;while(iright){if(arr[i]arr[j]){temp[k++]=arr[i++];}else{temp[k++]=arr[j++];}}while(imid){temp[k++]=arr[i++];}while(jright){temp[k++]=arr[j++];}for(intp=0;p){arr[left+p]=temp[p];}}}

计数排序

如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法,你千万不要立刻说:这不可能!虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序,只不过有前提条件,就是待排序的数要满足一定的范围的整数,而且计数排序需要比较多的辅助空间。其基本思想是,用待排序的数作为计数数组的下标,统计每个数字的个数。然后依次输出即可得到有序序列。

实现代码:

/***@Description:计数排序算法实现*@author王旭*/publicclassCountSort{publicstaticvoidcountSort(int[]arr){if(arr==null||arr.length==0)return;intmax=max(arr);int[]count=newint[max+1];Arrays.fill(count,0);for(inti=0;i){count[arr[i]]++;}intk=0;for(inti=0;i){for(intj=0;j){arr[k++]=i;}}}publicstaticintmax(int[]arr){intmax=Integer.MIN_VALUE;for(intele:arr){if(ele>max)max=ele;}returnmax;}}

桶排序

桶排序算是计数排序的一种改进和推广,但是网上有许多资料把计数排序和桶排序混为一谈。其实桶排序要比计数排序复杂许多。

对桶排序的分析和解释借鉴这位兄弟的文章(有改动):http://hxraid.iteye.com/blog/647759

桶排序的基本思想:

假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶)。然后基于某种映射函数,将待排序列的关键字k映射到第i个桶中(即桶数组B的下标i),那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。bindex=f(key)其中,bindex为桶数组B的下标(即第bindex个桶),k为待排序列的关键字。桶排序之所以能够高效,其关键在于这个映射函数,它必须做到:如果关键字k1

举个栗子:

面试过程中常用的排序算法汇总(二)

假如待排序列K={49、38、35、97、76、73、27、49}。这些数据全部在1—100之间。因此我们定制10个桶,然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中,并在每个非空的桶中进行快速排序后得到如图所示。只要顺序输出每个B[i]中的数据就可以得到有序序列了。

桶排序分析:

桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的f(k)值的计算,其作用就相当于快排中划分,希尔排序中的子序列,归并排序中的子问题,已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

对N个关键字进行桶排序的时间复杂度分为两个部分:

(1)循环计算每个关键字的桶映射函数,这个时间复杂度是O(N)。

(2)利用先进的比较排序算法对每个桶内的所有数据进行排序,其时间复杂度为∑O(Ni*logNi)。其中Ni为第i个桶的数据量。

很显然,第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此,我们需要尽量做到下面两点:

(1)映射函数f(k)能够将N个数据平均的分配到M个桶中,这样每个桶就有[N/M]个数据量。

(2)尽量的增大桶的数量。极限情况下每个桶只能得到一个数据,这样就完全避开了桶内数据的“比较”排序操作。当然,做到这一点很不容易,数据量巨大的情况下,f(k)函数会使得桶集合的数量巨大,空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

总结:桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。

实现代码:

/***@Description:桶排序算法实现*@author王旭*/publicclassBucketSort{publicstaticvoidbucketSort(int[]arr){if(arr==null&arr.length==0)return;intbucketNums=10;//这里默认为10,规定待排数[0,100)List>buckets=newArrayList>();//桶的索引for(inti=0;i){buckets.add(newLinkedList());//用链表比较合适}//划分桶for(inti=0;i){buckets.get(f(arr[i])).add(arr[i]);}//对每个桶进行排序for(inti=0;i){if(!buckets.get(i).isEmpty()){Collections.sort(buckets.get(i));//对每个桶进行快排}}//还原排好序的数组intk=0;for(Listbucket:buckets){for(intele:bucket){arr[k++]=ele;}}}/***映射函数*@paramx*@return*/publicstaticintf(intx){returnx/10;}}

基数排序

基数排序又是一种和前面排序方式不同的排序方式,基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序,如果两个人总分相同,则语文高的排在前面,语文成绩也相同则数学高的排在前面。。。如果对数字进行排序,那么个位、十位、百位就是不同优先级的关键字,如果要进行升序排序,那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的,关键字优先级低的先进行分配和收集。

举个栗子:

面试过程中常用的排序算法汇总(二)

面试过程中常用的排序算法汇总(二)

面试过程中常用的排序算法汇总(二)

实现代码:

/***@Description:基数排序算法实现*@author王旭*/publicclassRadixSort{publicstaticvoidradixSort(int[]arr){if(arr==null&arr.length==0)return;intmaxBit=getMaxBit(arr);for(inti=1;i){List>buf=distribute(arr,i);//分配collecte(arr,buf);//收集}}/***分配*@paramarr待分配数组*@paramiBit要分配第几位*@return*/publicstaticList>distribute(int[]arr,intiBit){List>buf=newArrayList>();for(intj=0;j){buf.add(newLinkedList());}for(inti=0;i){buf.get(getNBit(arr[i],iBit)).add(arr[i]);}returnbuf;}/***收集*@paramarr把分配的数据收集到arr中*@parambuf*/publicstaticvoidcollecte(int[]arr,List>buf){intk=0;for(Listbucket:buf){for(intele:bucket){arr[k++]=ele;}}}/***获取最大位数*@paramx*@return*/publicstaticintgetMaxBit(int[]arr){intmax=Integer.MIN_VALUE;for(intele:arr){intlen=(ele+"").length();if(len>max)max=len;}returnmax;}/***获取x的第n位,如果没有则为0.*@paramx*@paramn*@return*/publicstaticintgetNBit(intx,intn){Stringsx=x+"";if(sx.length()n)return0;elsereturnsx.charAt(sx.length()-n)-'0';}}

总结

在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效,要么是利用简单排序的特点加以改进,要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的,需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序,只有最适合的排序。

下面就总结一下排序算法的各自的使用场景和适用场合。

面试过程中常用的排序算法汇总(二)

1.从平均时间来看,快速排序是效率最高的,但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是,在n较大时归并排序使用时间较少,但使用辅助空间较多。

2.上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单,但序列基本有序或者n较小时,直接插入排序是好的方法,因此常将它和其他的排序方法,如快速排序、归并排序等结合在一起使用。

3.基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大,而序列中大多数记录的最高关键字均不同,则亦可先按最高关键字不同,将序列分成若干小的子序列,而后进行直接插入排序。

4.从方法的稳定性来比较,基数排序是稳定的内排方法,所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。

5.上面的算法实现大多数是使用线性存储结构,像插入排序这种算法用链表实现更好,省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。

附:基于比较排序算法时间下限为O(nlogn)的证明:

基于比较排序下限的证明是通过决策树证明的,决策树的高度Ω(nlgn),这样就得出了比较排序的下限。

面试过程中常用的排序算法汇总(二)

首先要引入决策树。首先决策树是一颗二叉树,每个节点表示元素之间一组可能的排序,它予以京进行的比较相一致,比较的结果是树的边。先来说明一些二叉树的性质,令T是深度为d的二叉树,则T最多有2^片树叶。具有L片树叶的二叉树的深度至少是logL。所以,对n个元素排序的决策树必然有n!片树叶(因为n个数有n!种不同的大小关系),所以决策树的深度至少是log(n!),即至少需要log(n!)次比较。而log(n!)=logn+log(n-1)+log(n-2)+…+log2+log1>=logn+log(n-1)+log(n-2)+…+log(n/2)>=(n/2)log(n/2)>=(n/2)logn-n/2=O(nlogn)所以只用到比较的排序算法最低时间复杂度是O(nlogn)。

本文来源于,由网友提供或网络搜集,仅供个人研究、交流学习使用,不涉及商业盈利目的。如有版权问题,请联系本站管理员予以更改或删除