第一篇：各种排序算法的优缺点
一、冒泡排序
已知一组无序数据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[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;i 希尔(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 二.选择排序 选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序中主要使用直接选择排序和堆排 序。 ①.直接选择排序(不稳定) 直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第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 四.归并排序 归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有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)的排序方法：快速排序、堆排序或 归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定，则可选用归并排序。但从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。 《选择排序》教学心得 教学内容： 选择排序的算法思想 选择排序的实现过程 选择排序的编码实现 总结和思考：大数据背景下的排序 排序(Sort)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。排序方法分为两大类：一类是内排序：冒泡排序、选择排序、插入排序、希尔排序、交换排序、快速排序等；另一类是外排序。 从教学理念上看，本节课利用维果斯基的“最近发展区理论”，把学生的现有水平和兴趣点，结合教学的目标，形成最近发展区。教学着眼于学生的最近发展区，提供带有难度的内容，调动学生的积极性，发挥其潜能，超越其最近发展区而达到下一发展阶段的水平，然后在此基础上进行下一个发展区的发展。 从教学方法来看，主要使用案例分析法、讲授法等，从分析当前流行的冒泡排序算法的案例开始，由浅入深的介绍选择排序的基本概念,算法思想以及编码过程。 从教学过程来看，首先从回顾冒泡排序的内容导入，在改进冒泡排序的过程中，提出选择排序的概念和思想。用直观的动画方式展现选择排序思想和过程，总结分析出关键代码，引导学生写出完整代码，最后分析选择排序的关键点，并提出思考，大数据背景下的排序改进方法。 在整个过程中一直都力求让学生在已知的知识结构中推导、归纳出需要掌握的知识点。但是上完课程后感觉案例还不够多，相对于非计算机的学生来说，算法的分析比编码的过程更加重要。所以学生感到有些难，本来已经调动起来的积极性没能保持到整节课。非计算机专业的学生思考计算机问题深度不够，在以后的备课中要更多的挖掘教学案例的广度和深度，给他们更多的思维训练。 排序算法设计 一、内容分析 【教学目标】 1、理解排序的概念 2、了解常用排序方法 3、理解冒泡排序的基本思路 4、应用冒泡排序法进行排序 【重点难点】 1、冒泡排序法的基本思路 2、应用冒泡排序法进行排序 二、教学内容 （一）常用排序 排序的概念： 排序就是把一组元素（数据或记录）按照元素的值的递增或递减的次序重新排列元素的过程。 如：49 38 76 27 13 常用排序的方法： 1、冒泡排序：冒泡排序是一种简单而饶有趣味的排序方法，它的基本思想是：每次仅进行相邻两个元素的比较，凡为逆序（a(i)>a(i+1)），则将两个元素交换。 2、插入排序：它是一种最简单的排序方法，它的基本思想是依次将每一个元素插入到一个有序的序列中去。这很象玩扑克牌时一边抓牌一边理牌的过程，抓了一张就插到其相应的位置上去。 3、选择排序：这是一种比较简单的排序方法，其基本思想是，每一趟在n-i+1（i=1，2，3，...，n-1）个元素中选择最小的元素。 冒泡排序： 冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是：每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。 整个的排序过程为： 先将第一个元素和第二个元素进行比较，若为逆序，则交换之；接着比较第二个和第三个元素；依此类推，直到第n-1个元素和第n个元素进行比较、交换为止。如此经过一趟排序，使最大的元素被安置到最后一个元素的位置上。然后，对前n-1个元素进行同样的操作，使次大的元素被安置到第n-1个元素的位置上。重复以上过程，直到没有元素需要交换为止。 例题：对49 38 76 27 13 进行冒泡排序的过程： 初始状态： [49 38 76 27 13 ] 第一趟排序后：[38 49 27 13] 76 第二趟排序后：[38 27 13 ] 49 76 第三趟排序后：[27 13 ] 38 49 76 第四趟排序后：13 27 38 49 76 课堂练习： 用冒泡排序对68 45 35 75 55 17 41进行排序，第二趟排序后的状态为： A、45 35 68 55 17 41 75 B、35 17 41 45 55 68 75 C、35 45 55 17 41 68 75 D、35 45 17 41 55 68 75 作业： 1、以下两组数据按有小到大排序，请写出每一趟排序后的结果 45 82 12 75 13 89 95 90 87 76 65 54 43 32 21 2、以下两组数据按有大到小排序，请写出每一趟排序后的结果 45 52 12 18 85 46 32 12 23 34 45 56 67 78 89 91 拓展： 随机生成10个不同的整数存于数组a（1 to 10）中，按从小到大的顺序输出。 三、小结 冒泡排序： 冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是：每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。 整个的排序过程为： 先将第一个元素和第二个元素进行比较，若为逆序，则交换之；接着比较第二个和第三个元素；依此类推，直到第n-1个元素和第n个元素进行比较、交换为止。如此经过一趟排序，使最大的元素被安置到最后一个元素的位置上。然后，对前n-1个元素进行同样的操作，使次大的元素被安置到第n-1个元素的位置上。重复以上过程，直到没有元素需要交换为止。 例题：对49 38 76 27 13 进行冒泡排序的过程： 初始状态： [49 38 76 27 13 ] 第一趟排序后：[38 49 27 13] 76 第二趟排序后：[38 27 13 ] 49 76 第三趟排序后：[27 13 ] 38 49 76 第四趟排序后：13 27 38 49 76 排序算法编程相关知识： 1、数组的定义： 声明数组的一般格式如下： Dim 数组名（[下界 to ] 上界）As 数据类型 2、数组元素的输入输出：（1）生成随机整数(1-100之间)Randomize for i=1 to n a(i)=int(rnd*100+1)next i（2）输出数组元素 for i=1 to n print a(i);next i 3、冒泡排序的算法实现： 冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是： 每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。 用两个FOR循环实现： for j=n-1 to 1 step-1 for i=1 to j if a(i)>a(i+1)then t=a(i)a(i)=a(i+1)a(i+1)=t end if next i next j 排序算法的应用： 1、随机生成10个不同的整数存于数组a（1 to 10）中，按从小到大的顺序输出。 2、随机生成20个学生的考试成绩，其中前50%的学生可以参加夏令营。输出这50%的学生的成绩。 3、数组A和数组B 分别记录6个数据，现在要把这两个数组合并成一个有序的数组。（从大到小的顺序） 《算法导论》学习总结——快速排序 曾经在程序员杂志上看到快速排序的作者，Hoare，曾经的图灵奖获得者啊，牛光闪闪的。不过当时，对快速排序什么的，印象不算深刻，毕竟没好好学。记得当时杂志上说到的是，快速排序，应该是目前最快的内部排序算法（虽然独立到语言上，C++的sort会比调用快速排序快）。现在就进入快速排序的美好复习吧。 与归并排序类似，快排也用分治模式。主要是三个步骤： 1）分解：将数组A[p....r]划分为2个子数组A[p....q-1]和A[q+1....r]，使前一个每个元素都小于A[q],后一个数组，每个元素都大于A[q]（q在划分过程中计算） 2）解决：递归调用快速排序，对2个子数组进行排序 3）合并：因为2个子数组是就地排序，所以合并不用操作，数组已排序 看到这个合并，就想到啊，和归并比，一个从小到大，一个从大到小，差距就是这么大，快排么得合并开销，一下就省了很多啊，说明，方向很重要啊，如同那句，同样一个B，S与N的差别，大家都懂的。 快速排序的实现代码如下： //================= // Name : Qsort.cpp // Author : xia // Copyright : NUAA // Description : 快速排序的实现 //================= #include #include #include #include #include using namespace std; const int MAX = 1000; void WriteToFile(vector {//将v写入文件，纯看排序结果是否正确，也可以写个test() int i; ofstream result(“Qsort.txt”); if(result.fail()) { cout << “ open data error ” << endl; exit(EXIT_FAILURE); } for(i=0;i result << v[i] << “ ”; } result.close(); } int Partion(vector int x=A[r];//x都感觉没用 int i=p-1; for(int j=p;j if(A[j] <= x) { i++; swap(A[i],A[j]); } } swap(A[i+1],A[r]); return i+1; } void Qsort(vector if(p < r) { int q = Partion(A,p,r); Qsort(A,p,q-1); Qsort(A,q+1,r); } } int main(int argc, char **argv) { vector int i; for(i=0;i< MAX;i++) v.push_back(i); random_shuffle(v.begin(),v.end());//打乱 Qsort(v,0,v.size()-1); WriteToFile(v); return 0; } 说到代码，很惭愧的，http://）由于以下两个原因： 1）做格式化时，结果常常是扭曲的，所以得不到正确的随机数（如某些数的出现频率要高于其它数） 2）rand()只支持整型数；不能用它来产生随机字符，浮点数，字符串或数据库中的记录 所以采用了STL函数random_shuffle()，先随机生成0到MAX-1的随机数，用random_shuffle()打乱，再进行排序。 另外，其实Hoare老师用的快排并不是如上代码所示，也就是说，最原始的快速排序，是这样滴： int HoarePartion(vector int x=A[p]; int i=p-1; int j=r+1; while(1) { while(A[--j] > x); while(A[++i] < x); if(i swap(A[i],A[j]); else return j; } } void Qsort(vector if(p < r) { int q = HoarePartion(A,p,r); Qsort(A,p,q); Qsort(A,q+1,r); } } 也可以参考：http://tayoto.blog.hexun.com/25048556_d.html，区别只是我的代码直接while里面用A[--j]，可读性不高，因为着实不喜欢do-while结构。 对于最原始的快排，严蔚敏老师的《数据结构》是这样实现的： int Partion(vector int pivotkey; pivotkey = v[low]; while(low < high) { while(low < high && v[high] >= pivotkey) high--; v[low] = v[high]; while(low < high && v[low] <= pivotkey) low ++; v[high] = v[low]; } v[low] = pivotkey; return low; } void quickSort(vector if(left < right) { int i = Partion(number , left, right); quickSort(number, left, i-1);// 对左边进行递归 quickSort(number, i+1, right);// 对右边进行递归 } } 当然，区别都只是在划分的过程，毕竟分治，才是快排的精髓嘛，不过这俩大同小异。 快排的运行时间，显然与划分是否对称有关，要是直接划分出来，是一个最不均衡的二叉树，那就够喝一壶的了，跟插入排序似的。下面网址有说法，是快排隐藏的二叉排序树思想，其实可以参考，虽然只是个人理解http://bbs.chinaunix.net/viewthread.php?tid=1011316。其实说到二叉，堆排序不也是吗？区别只是堆排序显式的建堆，也就构成了一笔不小的开销，如果考虑隐藏排序二叉树的话，倒是可以理解为毛快排快于堆排。 由于快排平均情况下效果显然很良好，那么怎么得到平均情况就是个值得思考的问题，所以书上给出了，在划分的时候，随机获取一个数作为枢轴，而不是用我们的A[low]。于是我们得到了快排的随机化版本如下： int Partion(vector int x=A[r]; int i=p-1; for(int j=p;j if(A[j] <= x) { i++; swap(A[i],A[j]); } } swap(A[i+1],A[r]); return i+1; } int RandomPartion(vector int i= p + rand()%(r-p+1);//i<-RANDOM(p,r) swap(A[r],A[i]); return Partion(A,p,r); } void RandomQsort(vector if(p < r) { int q = RandomPartion(A,p,r); RandomQsort(A,p,q-1); RandomQsort(A,q+1,r); } } 与常规快排的区别，就是在划分的时候，获取一个随机数下标，再用其数组中的值作为枢轴，当然，这样就充分考虑平均性能了。 还有一种改进RANDOM-QUICKSORT的方法，就是根据从子数组更仔细地选择的（而不是随机选择的元素）作为枢轴来划分。常用的做法是三数取中。可以参考： http://blog.csdn.net/zhanglei8893/article/details/6266915 本章最后还提到个很蛋疼的Stooge排序，实现如下： void StoogeSort(vector if(A[i] > A[j]) swap(A[i],A[j]); if(i+1 >=j) return; int k =(j-i+1)/3; StoogeSort(A,i,j-k);//前2/ 3 StoogeSort(A,i+k,j);//后2/3 StoogeSort(A,i,j-k);//又前2/3 // StoogeSort(A,i,i+k-1);// 如果采用1/3排不出来啊 } 对于数组A[i...j]，STOOGE-SORT算法将这个数组划分成均等的3份，分别用A, B, C表示。第8、9行从宏观上来看它进行了两趟，结果是最大的1/3到了C，最小的1/3到了B，从宏观上来看，整个数组的三个大块就有序了，再进行递归，整个数组就有序了。第8和第9行，可以看做一个冒泡过程。 不过从运行时间的测试来讲，很不给力（具体数据就不列了）。STOOGE-SORT最坏情况下的运行时间的递归式 T(n)= 2T(2n/3)+Θ(1)由主定律可以求得T(n)=n^2.71，相比插入排序、快速排序的Θ(n^2)和 堆排序、合并排序的Θ(nlgn)，不给力啊。参考自：http://blog.csdn.net/zhanglei8893/article/details/6235294。 本章最后，练习7-4还提出个尾递归的概念，起因是QuickSort的第二次递归调用不是必须的，可以用迭代控制结构来替代。如： QUICKSORT'(A, p, r)1 while p < r 2 do ▸ Partition and sort left subarray.3 q ← PARTITION(A, p, r)4 QUICKSORT'(A, p, q-1)5 p ← q + 1 具体 有效性的证明可以参考：http://blog.csdn.net/zhanglei8893/article/details/6236792，需要说明的是，当数组正序时，其递归深度和栈深度都为Θ(n)。第二篇：排序算法总结
第三篇：排序算法教学反思
第四篇：4.4排序算法设计
第五篇：《算法导论》学习总结——快速排序
点击咨询 