首页 > 精品范文库 > 15号文库
各种排序算法的优缺点
编辑:落花时节 识别码:24-815595 15号文库 发布时间: 2023-11-28 19:14:48 来源:网络

第一篇:各种排序算法的优缺点

一、冒泡排序

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与 a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变。再比 较a[3]与a[4],以此类推,最后比较a[n-1]与a[n]的值。这样处理一轮后,a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮,以此类推。共处理 n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

优点:稳定;

缺点:慢,每次只能移动相邻两个数据。

二、选择排序

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:

①初始状态:无序区为R[1..n],有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟 排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

优点:移动数据的次数已知(n-1次);

缺点:比较次数多。

三、插入排序

已知一组升序排列数据a[1]、a[2]、……a[n],一组无序数据b[1]、b[2]、……b[m],需将二者合并成一个升序数列。首先比较b[1]与a[1]的值,若b[1]大于a[1],则跳过,比较b[1]与a[2]的值,若b[1]仍然大于a[2],则继续跳过,直到b[1]小于a数组中某一数据a[x],则将a[x]~a[n]分别向后移动一位,将b[1]插入到原来 a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。(若无数组a,可将b[1]当作n=1的数组a)

优点:稳定,快;

缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决这个问题。

四、缩小增量排序

由希尔在1959年提出,又称希尔排序(shell排序)。

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。发现当n不大时,插入 排序的效果很好。首先取一增量d(d

优点:快,数据移动少;

缺点:不稳定,d的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取。

五、快速排序

快速排序是冒泡排序的改进版,是目前已知的最快的排序方法。

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先任取数据a[x] 作为基准。比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数 据a[x],然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。

优点:极快,数据移动少;

缺点:不稳定。

六、箱排序

已知一组无序正整数数据a[1]、a[2]、……a[n],需将其按升序排列。首先定义一个数组x[m],且m>=a[1]、a[2]、……a[n],接着循环n次,每次x[a]++.优点:快,效率达到O(1)缺点:数据范围必须为正整数并且比较小

六、归并排序

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1)3(2)2(3)2(4)5(5)(括号中是记录的关键字)时输出的 1(1)2(3)2(4)3(2)5(5)中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.归并排序:归并排序是一种非就地排序,将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并,将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大,那将不适合。但可改造成索引操作,效果将非常出色。

堆排序:由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤:-是建堆,二是排序(调整堆)。所以一般在小规模的序列中不合适,但对于较大的序列,将表现出优越的性能。

第二篇:排序算法总结

排序算法总结

所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。当待排序记录的关键字都不相同时,排序结果是惟一的,否则排序结果不惟一。

在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生改变,则称这种排序方法是不稳定的。

要注意的是,排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。

一.插入排序

插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小,插到前面已经排好的文件中的适当位置,直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。

①.直接插入排序(稳定)接插入排序的过程为:在插入第i个记录时,R1,R2,..Ri-1已经排好序,将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较,找到适当的位置。使用直接插入排序,对于具有n个记录的文件,要进行n-1趟排序。

代码如下:

void Dir_Insert(int A[],int N)//直接插入排序 { int j,t;for(int i=1;it){ A[j+1]=A[j];j--;} A[j+1]=t;} } ②.希尔排序(不稳定):

希尔(Shell)排序的基本思想是:先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取得第二个增量d2

一般取d1=n/2,di+1=di/2。如果结果为偶数,则加1,保证di为奇数。

希尔排序是不稳定的,希尔排序的执行时间依赖于增量序列,其平均时间复杂度为O(n^1.3).代码如下:

void Shell(int A[],int n)//Shell排序 { int i,j,k,t;(n/2)%2 == 0 ? k = n/2+1 : k = n/2;//保证增量为奇数

while(k > 0){ for(j=k;j=0 && A[i]>t){ A[i+k]=A[i];i=i-k;} A[i+k]=t;} if(k == 1)break;(k/2)%2 ==0 ? k=k/2+1 : k=k/2;} }

二.选择排序

选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录,顺序存放在已排序的记录序列的后面,直到全部排完。选择排序中主要使用直接选择排序和堆排 序。

①.直接选择排序(不稳定)

直接选择排序的过程是:首先在所有记录中选出序码最小的记录,把它与第1个记录交换,然后在其余的记录内选出排序码最小的记录,与第2个记录交换......依次类推,直到所有记录排完为止。

无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需要做n-i次比较,因此,总的比较次数为n(n-1)/2=O(n^2)。当初始文件为正序时,移动次数为0;文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n^2)。直接选择排序是不稳定的。

代码如下:

void Dir_Choose(int A[],int n)//直接选择排序 { int k,t;for(int i=0;i②.堆排序(不稳定)

堆排序是一种树形选择排序,是对直接选择排序的有效改进。n个关键字序列 K1,K2,...,Kn称为堆,当且仅当该序列满足(Ki<=K2i且Ki<=K2i+1)或(Ki>=K2i且Ki>=K2i+1),(1<=i<=n/2)。根结点(堆顶)的关键字是堆里所有结点关键字中最小者,称为小根堆;根结点的关键字是堆里所有结点关键字中最大者,称为大根堆。若将此序列所存储的向量R[1..n]看作是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

堆排序的关键步骤有两个:一是如何建立初始堆;二是当堆的根结点与堆的最后一个结点交换后,如何对少了一个结点后的结点序列做调整,使之重新成为堆。堆排序的最坏时间复杂度为O(nlog2n),堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较 次数较多,所以堆排序不适宜于记录较少的文件。堆排序是就地排序,辅助空间为O(1),它是不稳定的排序方法。

代码略..三.交换排序

交换排序的基本思想是:两两比较待排序记录的排序码,并交换不满足顺序要求的那写偶对,直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序.①.冒泡排序(稳定的)

冒泡排序将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R;凡扫描到违反本原则的轻气泡,就使其向上“漂浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。

冒泡排序的具体过程如下:

第一步,先比较k1和k2,若k1>k2,则交换k1和k2所在的记录,否则不交换。继续对k2和k3重复上述过程,直到处理完kn-1和kn。这时最大的排序码记录转到了最后位置,称第1次起泡,共执行n-1次比较。

与第一步类似,从k1和k2开始比较,到kn-2和kn-1为止,共执行n-2次比较。

依次类推,共做n-1次起泡,完成整个排序过程。

若文件的初始状态是正序的,一趟扫描即可完成排序。所需关键字比较次数为n-1次,记录移动次数为0。因此,冒泡排序最好的时间复杂度为O(n)。

若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1<=i<=n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较次数达到最大值n(n-1)/2=O(n^2),移动次数也达到最大值3n(n-1)/2=O(n^2)。因此,冒泡排序的最坏时间复杂度为O(n^2)。

虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均性能比直接插入排序要差得多。冒泡排序是就地排序,且它是稳定的。

代码如下: void QP(int A[],int n)//优化的冒泡排序

{ int count=0,t,flag;for(int i=0;i②.快速排序:(不稳定的)

快速排序采用了一种分治的策略,通常称其为分治法,其基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

快速排序的具体过程如下:

第一步,在待排序的n个记录中任取一个记录,以该记录的排序码为准,将所有记录分成两组,第1组各记录的排序码都小于等于该排序码,第2组各记录的排序码都大于该排序码,并把该记录排在这两组中间。

第二步,采用同样的方法,对左边的组和右边的组进行排序,直到所有记录都排到相应的位置为止。

代码如下:

void Quick_Sort(int A[],int low,int high)//low和high是数组的下标 { if(low=t)h--;if(h>l){ temp=A[l];A[l]=A[h];A[h]=temp;} } Quick_Sort(A,low,l-1);Quick_Sort(A,l+1,high);} }

四.归并排序

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并。直到得到长度为n的有序表,排序结束。

归并排序是一种稳定的排序,可用顺序存储结构,也易于在链表上实现,对长度为n的文件,需进行log2n趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。

代码略...五.基数排序

设单关键字的每个分量的取值范围均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值个数rd称为基数.基数的选择和关键字的分解因关键字的类型而异.

(1).若关键字是十进制整数,则按个、十等位进行分解,基数rd=10,C0=0,C9=9,d为最长整数的位数.

(2).若关键字是小写的英文字符串,则rd=26,C0='a',C25='z',d为最长字符串的长度.

基数排序的基本思想是:从低位到高位依次对待排序的关键码进行分配和收集,经过d趟分配和收集,就可以得到一个有序序列.

按平均时间将排序分为四类:

(1)平方阶(O(n2))排序

一般称为简单排序,例如直接插入、直接选择和冒泡排序;

(2)线性对数阶(O(nlgn))排序

如快速、堆和归并排序;

(3)O(n1+£)阶排序

£是介于0和1之间的常数,即0<£<1,如希尔排序;

(4)线性阶(O(n))排序

如基数排序。

各种排序方法比较

简单排序中直接插入最好,快速排序最快,当文件为正序时,直接插入和冒泡均最佳。

影响排序效果的因素

因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法应综合考虑下列因素:

①待排序的记录数目n;

②记录的大小(规模);

③关键字的结构及其初始状态;

④对稳定性的要求;

⑤语言工具的条件;

⑥存储结构;

⑦时间和辅助空间复杂度等。

不同条件下,排序方法的选择

(1)若n较小(如n≤50),可采用直接插入或直接选择排序。

当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;(3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或 归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

若要求排序稳定,则可选用归并排序。但从单个记录起进行两两归并的 排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件,然后再两两归并之。因为直接插入排序是稳定的,所以改进后的归并排序仍是稳定的。

第三篇:51CTO下载-排序和算法总结

事先声明,此文档来自某技术论坛,内容归原作者所有。

1.基本思想:

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。2.排序过程: 【示例】:

初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 [38 65 97 76 49 27 49] 第二趟排序后 13 27 [65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97 3.void selectionSort(Type* arr,long len){ long i=0,j=0;/*iterator value*/ long maxPos;assertF(arr!=NULL,“In InsertSort sort,arr is NULLn”);for(i=len-1;i>=1;i--){ maxPos=i;for(j=0;j插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。直接插入排序

直接插入排序(Straight Insertion Sort):将一个记录插入到排好序的有序表中,从而得到一个新的、记录数增1的有序表。直接插入排序算法

哨兵(监视哨)有两个作用:一是作为临变量存放R[i](当前要进行比较的关键字)的副本;二是在查找循环中用来监视下标变量j是否越界。

当文件的初始状态不同时,直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序,此时算法的时间复杂度为O(n),最坏情况是文件初态为反序,相应的时间复杂度为O(n2),算法的平均时间复杂度是O(n2)。算法的辅助空间复杂度是O(1),是一个就地排序。

直接插入排序是稳定的排序方法。三.冒泡排序

[算法思想]:将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上“飘浮”。如此反

复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。

[算法]:

void BubbleSort(SeqList R){ //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序 int i,j;

Boolean exchange; //交换标志

for(i=1;i

exchange=FALSE; //本趟排序开始前,交换标志应为假

for(j=n-1;j>=i;j--)//对当前无序区R[i..n]自下向上扫描 if(R[j+1].key

R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元 R[j+1]=R[j]; R[j]=R[0];

exchange=TRUE; //发生了交换,故将交换标志置为真 } if(!exchange)return;//本趟排序未发生交换,提前终止算法 } //endfor(外循环)} //BubbleSort [分析]:起泡排序的结束条件为:最后一趟没有进行“交换”。从起泡排序的过程可见,起泡排序是一个增加有序序列长度的过程,也是一个缩小无序序列长度的过程,每经过一趟起泡,无序序列的长度只缩小1。[算法思想]:将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上“飘浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。

[算法]:

void BubbleSort(SeqList R){ //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序 int i,j;

Boolean exchange; //交换标志

for(i=1;i

exchange=FALSE; //本趟排序开始前,交换标志应为假

for(j=n-1;j>=i;j--)//对当前无序区R[i..n]自下向上扫描 if(R[j+1].key

R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元 R[j+1]=R[j]; R[j]=R[0];

exchange=TRUE; //发生了交换,故将交换标志置为真 } if(!exchange)return;//本趟排序未发生交换,提前终止算法 } //endfor(外循环)} //BubbleSort [分析]:起泡排序的结束条件为:最后一趟没有进行“交换”。从起泡排序的过程可见,起泡排序是一个增加有序序列长度的过程,也是一个缩小无序序列长度的过程,每经过一趟起泡,无序序列的长度只缩小1。四.希尔排序 基本思想:

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d

l的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2

该方法实质上是一种分组插入方法。给定实例的shell排序的排序过程

假设待排序文件有10个记录,其关键字分别是: 49,38,65,97,76,13,27,49,55,04。

增量序列的取值依次为: 5,3,1 Shell排序的算法实现

1. 不设监视哨的算法描述

void ShellPass(SeqList R,int d){//希尔排序中的一趟排序,d为当前增量 for(i=d+1;i<=n;i++)//将R[d+1..n]分别插入各组当前的有序区 if(R[i].key

R[j+d];=R[j]; //后移记录 j=j-d; //查找前一记录

}while(j>0&&R[0].key

R[j+d]=R[0]; //插入R[i]到正确的位置上 } //endif } //ShellPass void ShellSort(SeqList R){ int increment=n; //增量初值,不妨设n>0 do { increment=increment/3+1; //求下一增量

ShellPass(R,increment); //一趟增量为increment的Shell插入排序 }while(increment>1)} //ShellSort 注意:

当增量d=1时,ShellPass和InsertSort基本一致,只是由于没有哨兵而在内循环中增加了一个循环判定条件“j>0”,以防下标越界。2.设监视哨的shell排序算法 算法分析

1.增量序列的选择

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征:

① 最后一个增量必须为1;

② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验,给出了目前较好的结果:当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。

2.Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因:

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。

③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。

因此,希尔排序在效率上较直接插人排序有较大的改进。3.稳定性 希尔

排序是不稳定的。参见上述实例,该例中两个相同关键字49在排序前后的相对次序发生了变化。五.堆排序

1、堆排序定义

n个关键字序列Kl,K2,„,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):

(1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。

2、大根堆和小根堆

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。注意:

①堆中任一子树亦是堆。

②以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。

3、堆排序特点

堆排序(HeapSort)是一树形选择排序。

堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】,在当前无序区中选择关键字最大(或最小)的记录。

4、堆排序与直接插入排序的区别

直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果,可减少比较次数。

5、堆排序

堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。(1)用大根堆排序的基本思想

① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区

② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key ③ 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有

序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。

„„

直到无序区只有一个元素为止。(2)大根堆排序算法的基本操作: ① 初始化操作:将R[1..n]构造为初始堆;

② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。注意:

①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。

②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻,堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。(3)堆排序的算法:

void HeapSort(SeqIAst R){ //对R[1..n]进行堆排序,不妨用R[0]做暂存单元 int i;

BuildHeap(R); //将R[1-n]建成初始堆

for(i=n;i>1;i--){ //对当前无序区R[1..i]进行堆排序,共做n-1趟。R[0]=R[1];R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换

Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆,仅有R[1]可能违反堆性质 } //endfor } //HeapSort(4)BuildHeap和Heapify函数的实现

因为构造初始堆必须使用到调整堆的操作,先讨论Heapify的实现。① Heapify函数思想方法

每趟排序开始前R[l..i]是以R[1]为根的堆,在R[1]与R[i]交换后,新的无序区R[1..i-1]中只有R[1]的值发生了变化,故除R[1]可能违反堆性质外,其余任何结点为根的子树均是堆。因此,当被调整区间是R[low..high]时,只须调整以R[low]为根的树即可。“筛选法”调整堆

R[low]的左、右子树(若存在)均已是堆,这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字,则R[low]未违反堆性质,以R[low]为根的树已是堆,无须调整;否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换,即R[low]与R[large](R[large].key=max(R[2low].key,R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质,同样由于该结点的两棵子树(若存在)仍然是堆,故可重复上述的调整过程,对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质,或者该结点已是叶子为止。上述过程就象过筛子一样,把较小的关键字逐层筛下去,而将较大的关键字逐层选上来。因此,有人将此方法称为“筛选法”。

②BuildHeap的实现

要将初始文件R[l..n]调整为一个大根堆,就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。

显然只有一个结点的 树是堆,而在完全二叉树中,所有序号 的结点都是叶子,因此以这些结点为根的子树均已是堆。这样,我们只需依次将以序号为,-1,„,1的结点作为根的子树都调整为堆即可。

具体算法【参见教材】。

5、大根堆排序实例

对于关键字序列(42,13,24,91,23,16,05,88),在建堆过程中完全二叉树及其存储结构的变化情况参见。

6、算法分析

堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。

由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序,辅助空间为O(1),它是不稳定的排序方法。六.快速排序

快速排序的基本思路是:首先我们选择一个中间值middle(程序中我们可使用数组中间值),把比中间值小的放在其左边,比中间值大的放在其右边。由于这个排序算法较复杂,我们先给出其进行一次排序的程序框架(从各类数据结构教材中可得): void QuickSort(int *pData, int left, int right){ int i, j;int middle, iTemp;i = left;j = right;middle = pData[(left + right)/ 2];//求中间值

do {

while((pData[i] < middle)&&(i < right))//从左扫描大于中值的数

i++;

while((pData[j] > middle)&&(j > left))//从右扫描小于中值的数

j--;

if(i <= j)//找到了一对值

{

//交换

iTemp = pData[i];

pData[i] = pData[j];

pData[j] = iTemp;

i++;

j--;

} } while(i <= j);//如果两边扫描的下标交错,就停止(完成一次)

//当左边部分有值(left

if(left

QuickSort(pData,left,j);

//当右边部分有值(right>i),递归右半边

if(right>i)

QuickSort(pData,i,right);} 对于n个成员,快速排序法的比较次数大约为n*logn 次,交换次数大约为(n*logn)/6次。如果n为100,冒泡法需要进行4950 次比较,而快速排序法仅需要200 次,快速排序法的效率的确很高。快速排序法的性能与中间值的选定关系密切,如果每一次选择的中间值都是最大值(或最小值),该算法的速度就会大大下降。快速排序算法最坏情况下的时间复杂度为O(n2),而平均时间复杂度为O(n*logn)。七.合并排序 說明

之前所介紹的排序法都是在同一個陣列中的排序,考慮今日有兩筆或兩筆以上的資料,它可能是不同陣列中的資料,或是不同檔案中的資料,如何為它們進行排序? 解法

可以使用合併排序法,合併排序法基本是將兩筆已排序的資料合併並進行排序,如果所讀入的資料尚未排序,可以先利用其它的排序方式來處理這兩筆資料,然後再將排序好的這兩筆資料合併。

有人問道,如果兩筆資料本身就無排序順序,何不將所有的資料讀入,再一次進行排序?排序的精神是儘量利用資料已排序的部份,來加快排序的效率,小筆資料的排序較為快速,如果小筆資料排序完成之後,再合併處理時,因為兩筆資料都有排序了,所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率。那麼可不可以直接使用合併排序法本身來處理整個排序的動作?而不動用到其它的排序方式?答案是肯定的,只要將所有的數字不斷的分為兩個等分,直到最後剩一個數字為止,然後再反過來不斷的合併,就如下圖所示:

不過基本上分割又會花去額外的時間,不如使用其它較好的排序法來排序小筆資料,再使用合併排序來的有效率。

下面這個程式範例,我們使用快速排序法來處理小筆資料排序,然後再使用合併排序法處理合併的動作。例子

C

#include #include #include #define MAX1 10 #define MAX2 10 #define SWAP(x,y){int t;t = x;x = y;y = t;} int partition(int[], int, int);void quicksort(int[], int, int);void mergesort(int[], int, int[], int, int[]);int main(void){ int number1[MAX1] = {0};int number2[MAX1] = {0};int number3[MAX1+MAX2] = {0};int i, num;srand(time(NULL));printf(“排序前:”);printf(“nnumber1[]:”);for(i = 0;i < MAX1;i++){ number1[i] = rand()% 100;printf(“%d ”, number1[i]);} printf(“nnumber2[]:”);for(i = 0;i < MAX2;i++){ number2[i] = rand()% 100;printf(“%d ”, number2[i]);} // 先排序兩筆資料

quicksort(number1, 0, MAX1-1);quicksort(number2, 0, MAX2-1);printf(“n排序後:”);printf(“nnumber1[]:”);for(i = 0;i < MAX1;i++)printf(“%d ”, number1[i]);printf(“nnumber2[]:”);for(i = 0;i < MAX2;i++)printf(“%d ”, number2[i]);// 合併排序

mergesort(number1, MAX1, number2, MAX2, number3);printf(“n合併後:”);for(i = 0;i < MAX1+MAX2;i++)printf(“%d ”, number3[i]);printf(“n”);return 0;} int partition(int number[], int left, int right){ int i, j, s;s = number[right];i = left-1;for(j = left;j < right;j++){ if(number[j] <= s){ i++;SWAP(number[i], number[j]);} } SWAP(number[i+1], number[right]);return i+1;} void quicksort(int number[], int left, int right){ int q;if(left < right){ q = partition(number, left, right);quicksort(number, left, q-1);quicksort(number, q+1, right);} } void mergesort(int number1[], int M, int number2[], int N, int number3[]){ int i

=

0, j = 0, k = 0;while(i < M && j < N){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < M)number3[k++] = number1[i++];while(j < N)number3[k++] = number2[j++];} Java

public class MergeSort { public static int[] sort(int[] number1, int[] number2){ int[] number3 = new int[number1.length + number2.length];int i = 0, j = 0, k = 0;while(i < number1.length && j < number2.length){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < number1.length)number3[k++] = number1[i++];while(j < number2.length)number3[k++] = number2[j++];return number3;} } 八。基数排序

基数排序是根据组成关键字的各位值,用“分配”和“收集”的方法进行排序。例如,把扑克牌的排序看成由花色和面值两个数据项组成的主关键字排序。

花色:梅花<方块<红心<黑桃

面值:2<3<4<...<10若要将一副扑克牌排成下列次序:

梅花2,...,梅花A,方块2,...,方块A,红心2,...,红心A,黑桃2,...,黑桃A。

有两种排序方法:

一、先按花色分成四堆,把各堆收集起来;然后对每堆按面值由小到大排列,再按花色从小到大按堆收叠起来。----称为“最高位优先”(MSD)法。

二、先按面值由小到大排列成13堆,然后从小到大收集起来;再按花色不同分成四堆,最后顺序收集起来。----称为“最低位优先”(LSD)法。

[例] 设记录键值序列为{88,71,60,31,87,35,56,18},用基数排序(LSD)。如图所示:其中f[i]、e[i]为按位分配面值为i的队列的队头和队尾指针。

#define D 3 typedef struct { int key;float data;int link;} JD

key data link int jspx(JD r[],int n){ /*链式存储表示的基数排序*/ int i,j,k,t,p,rd,rg,f[10],e[10];/*p为r[]的下标,rd,rg为比例因子,f[j],e[j]是代码为j的队的首尾指针*/ for(i=1;i0);j=0;/*按位收集--调整分配后的链接*/ while(f[j]==0)j=j+1;p=f[j];t=e[j];for(k=j+1;k<10;k++)if(f[k]>0){ r[t].link=f[k];t=e[k];}/*调整链接*/ r[t].link=0;/*链尾为0*/ rg=rg*10;rd=rd*10;/*提高一位*/ } return(p);/*返回有序链表的首地址*/ 九 枚举排序

将每个记录项与其他诸项比较计算出小于该项的记录个数,以确定该项的位置。

第四篇:排序算法教学反思

《选择排序》教学心得

教学内容:

选择排序的算法思想 选择排序的实现过程 选择排序的编码实现

总结和思考:大数据背景下的排序

排序(Sort)是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个关键字有序的序列。排序方法分为两大类:一类是内排序:冒泡排序、选择排序、插入排序、希尔排序、交换排序、快速排序等;另一类是外排序。

从教学理念上看,本节课利用维果斯基的“最近发展区理论”,把学生的现有水平和兴趣点,结合教学的目标,形成最近发展区。教学着眼于学生的最近发展区,提供带有难度的内容,调动学生的积极性,发挥其潜能,超越其最近发展区而达到下一发展阶段的水平,然后在此基础上进行下一个发展区的发展。

从教学方法来看,主要使用案例分析法、讲授法等,从分析当前流行的冒泡排序算法的案例开始,由浅入深的介绍选择排序的基本概念,算法思想以及编码过程。

从教学过程来看,首先从回顾冒泡排序的内容导入,在改进冒泡排序的过程中,提出选择排序的概念和思想。用直观的动画方式展现选择排序思想和过程,总结分析出关键代码,引导学生写出完整代码,最后分析选择排序的关键点,并提出思考,大数据背景下的排序改进方法。

在整个过程中一直都力求让学生在已知的知识结构中推导、归纳出需要掌握的知识点。但是上完课程后感觉案例还不够多,相对于非计算机的学生来说,算法的分析比编码的过程更加重要。所以学生感到有些难,本来已经调动起来的积极性没能保持到整节课。非计算机专业的学生思考计算机问题深度不够,在以后的备课中要更多的挖掘教学案例的广度和深度,给他们更多的思维训练。

第五篇:10种排序算法总结

10种排序算法总结

排序算法有很多,所以在特定情景中使用哪一种算法很重要。为了选择合适的算法,可以按照建议的顺序考虑以下标准:(1)执行时间(2)存储空间(3)编程工作

对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要。主要排序法有:

一、冒泡(Bubble)排序——相邻交换

二、选择排序——每次最小/大排在相应的位置

三、插入排序——将下一个插入已排好的序列中

四、壳(Shell)排序——缩小增量

五、归并排序

六、快速排序

七、堆排序

八、拓扑排序

九、锦标赛排序

十、基数排序

一、冒泡(Bubble)排序

---Code 从小到大排序n个数-----voidBubbleSortArray(){ for(int i=1;ia[j+1])//比较交换相邻元素 { int temp;temp=a[j];a[j]=a[j+1];a[j+1]=temp;} } } }------------------Code-----------------效率 O(n²),适用于排序小列表。

二、选择排序

---Code 从小到大排序n个数-voidSelectSortArray(){ intmin_index;for(int i=0;i三、插入排序

-------------Code 从小到大排序n个数------voidInsertSortArray(){ for(int i=1;i=0 &&arr[j]>temp)/*将temp与已排序元素从小到大比较,寻找temp应插入的位置*/ { arr[j+1]=arr[j];j--;} arr[j+1]=temp;} }------------------------------Code 最佳效率O(n);最糟效率O(n²)与冒泡、选择相同,适用于排序小列表 若列表基本有序,则插入排序比冒泡、选择更有效率。

四、壳(Shell)排序——缩小增量排序

------Code 从小到大排序n个数------voidShellSortArray(){ for(intincr=3;incr<0;incr--)//增量递减,以增量3,2,1为例 { for(int L=0;L<(n-1)/incr;L++)//重复分成的每个子列表 { for(int i=L+incr;i=0&&arr[j]>temp){ arr[j+incr]=arr[j];j-=incr;} arr[j+incr]=temp;} } } }-------Code------------适用于排序小列表。

效率估计O(nlog2^n)~O(n^1.5),取决于增量值的最初大小。建议使用质数作为增量值,因为如果增量值是2的幂,则在下一个通道中会再次比较相同的元素。

壳(Shell)排序改进了插入排序,减少了比较的次数。是不稳定的排序,因为排序过程中元素可能会前后跳跃。

五、归并排序

---------------Code 从小到大排序--------voidMergeSort(intlow,int high){ if(low>=high)return;//每个子列表中剩下一个元素时停止

else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素,则在左边子列表大于右侧子列表*/ MergeSort(low,mid);//子列表进一步划分 MergeSort(mid+1,high);int [] B=new int [high-low+1];//新建一个数组,用于存放归并的元素

for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)/*两个子列表进行排序归并,直到两个子列表中的一个结束*/ { if(arr[i]<=arr[j];){ B[k]=arr[i];I++;} else { B[k]=arr[j];j++;} } for(;j<=high;j++,k++)//如果第二个子列表中仍然有元素,则追加到新列表 B[k]=arr[j];for(;i<=mid;i++,k++)//如果在第一个子列表中仍然有元素,则追加到新列表中 B[k]=arr[i];for(int z=0;z

六、快速排序

-----Code-------------/*快速排序的算法思想:选定一个枢纽元素,对待排序序列进行分割,分割之后的序列一个部分小于枢纽元素,一个部分大于枢纽元素,再对这两个分割好的子序列进行上述的过程。*/ void swap(inta,int b){intt;t =a;a =b;b =t;} int Partition(int [] arr,intlow,int high){ int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素 while(low < high){ //从后往前栽后半部分中寻找第一个小于枢纽元素的元素 while(low < high &&arr[high] >= pivot){--high;} //将这个比枢纽元素小的元素交换到前半部分 swap(arr[low], arr[high]);//从前往后在前半部分中寻找第一个大于枢纽元素的元素 while(low

此算法的总时间取决于枢纽值的位置;选择第一个元素作为枢纽,可能导致O(n²)的最糟用例效率。若数基本有序,效率反而最差。选项中间值作为枢纽,效率是O(nlogn)。基于分治法。

七、堆排序

最大堆:后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字,此时位于堆顶的节点的关键字是整个序列中最大的。思想:

(1)令i=l,并令temp= kl;(2)计算i的左孩子j=2i+1;(3)若j<=n-1,则转(4),否则转(6);(4)比较kj和kj+1,若kj+1>kj,则令j=j+1,否则j不变;

(5)比较temp和kj,若kj>temp,则令ki等于kj,并令i=j,j=2i+1,并转(3),否则转(6)(6)令ki等于temp,结束。

----------Code---------------------------void HeapSort(SeqIAst R){ //对R[1..n]进行堆排序,不妨用R[0]做暂存单元 int I;BuildHeap(R); //将R[1-n]建成初始堆for(i=n;i>1;i--)//对当前无序区R[1..i]进行堆排序,共做n-1趟。{ R[0]=R[1];R[1]=R[i];R[i]=R[0];//将堆顶和堆中最后一个记录交换 Heapify(R,1,i-1);//将R[1..i-1]重新调整为堆,仅有R[1]可能违反堆性质 } }--------Code-------

堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序是就地排序,辅助空间为O(1),它是不稳定的排序方法。

堆排序与直接插入排序的区别: 直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果,可减少比较次数。

八、拓扑排序

例 :学生选修课排课先后顺序

拓扑排序:把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。方法:

在有向图中选一个没有前驱的顶点且输出 从图中删除该顶点和所有以它为尾的弧

重复上述两步,直至全部顶点均已输出(拓扑排序成功),或者当图中不存在无前驱的顶点(图中有回路)为止。

--------Code-------void TopologicalSort()/*输出拓扑排序函数。若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR*/ { intindegree[M];inti,k,j;char n;int count=0;Stack thestack;FindInDegree(G,indegree);//对各顶点求入度indegree[0....num] InitStack(thestack);//初始化栈 for(i=0;i

九、锦标赛排序

锦标赛排序的算法思想与体育比赛类似。

首先将n个数据元素两两分组,分别按关键字进行比较,得到n/2个比较的优胜者(关键字小者),作为第一步比较的结果保留下来,然后对这n/2个数据元素再两两分组,分别按关键字进行比较,„,如此重复,直到选出一个关键字最小的数据元素为止。

-Code in C--------#include #include #include #include #define SIZE 100000 #define MAX 1000000 struct node { long num;//关键字 char str[10];intlastwin;//最后胜的对手 int killer;//被击败的对手 long times;//比赛次数 }data[SIZE];long CompareNum=0;long ExchangeNum=0;long Read(char name[])//读取文件a.txt中的数据,并存放在数组data[]中;最后返回数据的个数 { FILE *fp;long i=1;fp=fopen(name,“rw”);fscanf(fp,“%d%s”,&data[i].num,data[i].str);while(!feof(fp)){ i++;fscanf(fp,“%d%s”,&data[i].num,data[i].str);} return(i-1);} long Create(long num)//创建胜者树,返回冠军(最小数)在数组data[]中的下标 { int i,j1,j2,max,time=1;long min;//记录当前冠军的下标 for(i=1;pow(2,i-1)num)data[i].num=MAX;} for(i=1;i<=max;i+=2)//第一轮比赛 { ++CompareNum;if(data[i].num<= data[i+1].num){ data[i].lastwin = i+1;data[i+1].killer=i;++data[i].times;++data[i+1].times;min=i;} else { data[i+1].lastwin=i;data[i].killer=i+1;++data[i].times;++data[i+1].times;min=i+1;} } j1=j2=0;//记录连续的两个未被淘汰的选手的下标 while(time <=(log(max)/log(2)))//进行淘汰赛 { for(i=1;i<=max;i++){ if(data[i].times==time && data[i].killer==0)//找到一名选手 { j2=i;//默认其为两选手中的后来的

if(j1==0)//如果第一位置是空的,则刚来的选手先来的 j1=j2;else//否则刚来的选手是后来的,那么选手都已到场比赛开始 { ++CompareNum;if(data[j1].num<= data[j2].num)//先来的选手获胜 { data[j1].lastwin = j2;//最后赢的是j2 data[j2].killer=j1;//j2是被j1淘汰的 ++data[j1].times;++data[j2].times;//两选手场次均加1 min=j1;//最小数下标为j1 j1=j2=0;//将j1,j2置0 } else//同理 { data[j2].lastwin=j1;data[j1].killer=j2;++data[j1].times;++data[j2].times;min=j2;j1=j2=0;} } } } time++;//轮数加1 } return min;//返回冠军的下标 } void TournamentSort(long num)//锦标赛排序 { long tag=Create(num);//返回最小数下标 FILE *fp1;fp1=fopen(“sort.txt”,“w+”);//为写入创建并打开文件sort.txt while(data[tag].num!= MAX)//当最小值不是无穷大时 { printf(“%d %sn”,data[tag].num,data[tag].str);//输出数据 fprintf(fp1,“%d %sn”,data[tag].num,data[tag].str);//写入数据 data[tag].num=MAX;//将当前冠军用无穷大替换 tag=Create(num);//返回下一个冠军的下标 } } int main(){ intnum;char name[10];printf(“Input name of the file:”);gets(name);num=Read(name);//读文件

TournamentSort(num);//锦标赛排序

printf(“CompareNum=%dnExchangeNum=%dn”,CompareNum,ExchangeNum);return 0;}-----------Code------

十、基数排序

基数排序又被称为桶排序。与前面介绍的几种排序方法相比较,基数排序和它们有明显的不同。

前面所介绍的排序方法都是建立在对数据元素关键字进行比较的基础上,所以可以称为基于比较的排序; 而基数排序首先将待排序数据元素依次“分配”到不同的桶里,然后再把各桶中的数据元素“收集”到一起。

通过使用对多关键字进行排序的这种“分配”和“收集”的方法,基数排序实现了对多关键字进行排序。——————————————————————————————————————— 例:

每张扑克牌有两个“关键字”:花色和面值。其大小顺序为: 花色:§<¨<©<ª 面值:2<3<„„<K<A 扑克牌的大小先根据花色比较,花色大的牌比花色小的牌大;花色一样的牌再根据面值比较大小。所以,将扑克牌按从小到大的次序排列,可得到以下序列: §2,„,§A,¨2,„,¨A,©2,„,©A,ª2,„,ªA 这种排序相当于有两个关键字的排序,一般有两种方法实现。

其一:可以先按花色分成四堆(每一堆牌具有相同的花色),然后在每一堆牌里再按面值从小到大的次序排序,最后把已排好序的四堆牌按花色从小到大次序叠放在一起就得到排序的结果。其二:可以先按面值排序分成十三堆(每一堆牌具有相同的面值),然后将这十三堆牌按面值从小到大的顺序叠放在一起,再把整副牌按顺序根据花色再分成四堆(每一堆牌已按面值从小到大的顺序有序),最后将这四堆牌按花色从小到大合在一起就得到排序的结果。

——————————————————————————————————————— 实现方法:

最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。

最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。

--Code in C#-----------

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace LearnSort

{

class Program

{

static void Main(string[] args)

{

int[] arr = CreateRandomArray(10);//产生随机数组

Print(arr);//输出数组

RadixSort(ref arr);//排序

Print(arr);//输出排序后的结果

Console.ReadKey();

}

public static void RadixSort(ref int[] arr)

{

intiMaxLength = GetMaxLength(arr);

RadixSort(ref arr, iMaxLength);

}

private static void RadixSort(ref int[] arr, intiMaxLength)

{

List list = new List();//存放每次排序后的元素

List[] listArr = new List[10];//十个桶

char currnetChar;//存放当前的字符比如说某个元素123 中的2

string currentItem;//存放当前的元素比如说某个元素123

for(int i = 0;i

listArr[i] = new List();

for(int i = 0;i

{

foreach(int number in arr)//分桶

{

currentItem = number.ToString();//将当前元素转化成字符串

try { currnetChar = currentItem[currentItem.Length-i-1];}//从个位向高位开始分桶

catch { listArr[0].Add(number);continue;}//如果发生异常,则将该数压入listArr[0]。比如说5 是没有十位数的,执行上面的操作肯定会发生越界异常的,这正是期望的行为,我们认为5的十位数是0,所以将它压入listArr[0]的桶里。

switch(currnetChar)//通过currnetChar的值,确定它压人哪个桶中。

{

case '0': listArr[0].Add(number);break;

case '1': listArr[1].Add(number);break;

case '2': listArr[2].Add(number);break;

case '3': listArr[3].Add(number);break;

case '4': listArr[4].Add(number);break;

case '5': listArr[5].Add(number);break;

case '6': listArr[6].Add(number);break;

case '7': listArr[7].Add(number);break;

case '8': listArr[8].Add(number);break;

case '9': listArr[9].Add(number);break;

default: throw new Exception(“unknow error”);

}

}

for(int j = 0;j

foreach(int number in listArr[j].ToArray())

{

list.Add(number);

listArr[j].Clear();//清空每个桶

}

arr = list.ToArray();//arr指向重新排列的元素

//Console.Write(“{0} times:”,i);

Print(arr);//输出一次排列的结果

list.Clear();//清空list

}

}

//得到最大元素的位数

private static intGetMaxLength(int[] arr)

{

intiMaxNumber = Int32.MinValue;

foreach(int i in arr)//遍历得到最大值

{

if(i >iMaxNumber)

iMaxNumber = i;

}

return iMaxNumber.ToString().Length;//这样获得最大元素的位数是不是有点投机取巧了...}

//输出数组元素

public static void Print(int[] arr)

{

foreach(int i in arr)

System.Console.Write(i.ToString()+'t');

System.Console.WriteLine();

}

//产生随机数组。随机数的范围是0到1000。参数iLength指产生多少个随机数

public static int[] CreateRandomArray(intiLength)

{

int[] arr = new int[iLength];

Random random = new Random();

for(int i = 0;i

arr[i] = random.Next(0,1001);

return arr;

}

}

}--Code--------------基数排序法是属于稳定性的排序,其时间复杂度为O(nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。

各种排序算法的优缺点
TOP