排序算法总结

1、注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理一、 排序问题1.1 排序问题的定义排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。设为非空集合上的二元关系，如果满足自反性(对于每一个，)，反对称性()和传递性()，则称为上的偏序关系，记作。如果，则记作，读作“小于等于”。存在偏序关系的集合称为偏序集。（注意，这里的不是指数的大小，而是指在偏序关系中的顺序性。的含义是：按照这个序，x排在y前面。根据不同的偏序定义，有不同的解释。例如整除关系是偏序关系，36的含义是3

2、整除6。大于或等于关系也是偏序关系，针对这个关系54是指在大于或等于关系中5排在4的前面，也就是说5比4大。）在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个主键域key，key域的类型是某一个偏序集，记录的其他域称为数据。比较线性表中的两个元素Li和Lj的大小，实际上是比较Li.key和Lj.key的大小（这种比较当然也是偏序集中的比较）。举例而言，某公司的数据库里记 录了员工的数据，每一项纪录包括姓名，编号，年龄，工资等几个域，如果以编号为key域对员工记录排序，则是将员工记录按照编号排序；如果以工资为key域对员工记录排序，则是将员工记录

3、按照工资高低排序；如果以姓名为key域对员工记录排序，则是以员工姓名的汉语拼音按照字典顺序排序。1.2 排序问题的分类如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做原地置换排序算法(in place sort)；如果排序后并不改变表中相同的元素原来的相对位置，那么这种排序算法叫做稳定排序算法(stable sort)。排序问题一般分为内排序( internal sorting )和外排序( external sorting )两类：内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中；外排序：待排序的记录个数足够多，以至于他们

4、必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。1.3 排序问题的计算复杂性对排序算法计算时间的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。为了对有n个元素的线性表进行排序，至少必须扫描线性表一遍以获取这n个元素的信息，因此排序问题的计

5、算复杂性下界为。如果我们对输入的数据不做任何要求，我们所能获得的唯一信息就是各个元素的具体的值，我们仅能通过比较来确定输入序列的元素间次序。即给定两个元素和，通过测试中的哪一个成立来确定和间的相对次序。这样的排序算法称为比较排序算法。下面我们讨论一下比较排序算法在最坏情况下至少需要多少次比较，即比较排序算法的最坏情况复杂性下界。我们假设每次比较只测试 ，如果 成立则排在 前面，否则排在 后面。任何一个比较排序算法可以描述为一串比较序列:表示我们首先比较，然后比较，.，比较，.，直到我们获取了足够的信息可以确定所有元素的顺序。显而易见，如果我们对所有的元素

6、两两进行一次比较的话(总共比较了次)，就一定可以确定所有元素的顺序。但是，如果我们运气足够好的话，我们可能不必对所有元素两两进行一次比较。比如说对于有三个元素的线性表进行排序，如果我们先比较和，得到；然后比较和，得到；则不必比较和，因为根据偏序集的传递性，必有；但是如果，我们还必须比较和才能确定和的相对位置。如果我们适当的安排比较的次序的话，也可以减少比较的次数。这样我们可以用一棵二叉树表示比较的顺序，如下图所示：图 二叉树表示比较的顺序该树的每一个非叶节点表示一次比较，每一根树枝表示一种比较结果，每一个叶节点表示一种排列顺序。这样的一棵二叉树叫做决策树，它用树枝表示了每次决策做出的选择。如此

7、我们可以将任何一个比较排序算法用一棵决策树来表示。请注意上图只表明了对三个元素的一种比较算法，这种比较算法依次比较，一旦中间某步得到足够的信息就可以停止比较，但是当算法执行完后（三次比较后），一定可以确定三个元素间的次序。因此我们有理由将算法在最坏情况下的比较次数作为算法复杂性的度量，对于本例该算法在最坏情况下要进行次比较。显然，一棵决策树中最高叶节点的高度就是该决策树对应的算法在最坏情况下所需的比较次数，而决策树中最低叶节点的高度就是该决策树对应的算法在最好情况下所需的比较次数。我们的问题就变为：对于任意一棵决策树（任意一种比较排序算法），它的最高的树叶的高度是多少？这个高度就对应于比较排序

8、算法所需的最多比较次数（在运气最坏的情况下）；换句话说，对于任何一个输入，该算法至少需要比较多少次就可以对元素进行排序。我们发现，决策树的每个叶节点对应一个个元素的排列，其中可能有重复的；但是由于决策树表明了所有可能遇到的情况，因而个元素的所有排列都在决策树中出现过。个元素共有种排列，即决策树的叶节点数目至少为。又因为一棵高度为的二叉树（指二叉树的最高树叶高度为）的叶节点数目最多为个（这时正好是满二叉树，即每个非叶节点都有两个子节点），因此，得到，其中log以2为底。根据Stirling公式有，于是，即。这样我们就证明了对于任意一种利用比较来确定元素间相对位置的排序算法，其最坏情况下复杂性为。

9、在下文中我们将讨论几种比较排序算法，其中快速排序在平均情况下复杂性为，最坏情况下复杂性为；堆排序和合并排序在最坏情况下复杂性为，因此堆排序和合并排序是渐进最优的比较排序算法。排序算法是否还能够改进呢？从前文我们知道，如果要改进排序算法的效率，就不能只利用比较来确定元素间相对位置。因此我们还需要知道元素的其他附加信息，光知道元素的大小信息是不够的。下文中我们介绍的计数排序，基数排序和桶排序是具有线性时间复杂性的排序算法，这些算法无一例外地对输入数据作了某些附加限制，从而增加已知的信息，因此可以不通过比较来确定元素间的相对位置。1.4 常见排序算法表 各排序算法的时间复杂度、空间复杂度及稳定性类别

10、排序方法时间复杂度空间复杂度稳定性平均情况最好情况最坏情况辅助存储插入排序直接插入稳定希尔排序不稳定选择排序直接选择不稳定堆排序不稳定交换排序冒泡排序稳定快速排序不稳定归并排序稳定基数排序稳定二、直接插入排序法(插入排序)2.1 算法思想每次选择一个元素K插入到之前已排好序的部分A1i中，插入过程中K依次由后向前与A1i中的元素进行比较。若发现发现Ax>=K,则将K插入到Ax的后面，插入前需要移动元素。图 直接插入排序法思想2.2 代码实现(C语言)/参数：Array:待排序序列，n:序列长度，AscendFlag:升降排序标志位，true为升序template <class Da

11、taType>/使用函数模板，方便适应各种类型数据的排序bool InsertSort(DataType Array,int n,bool AscendFlag = true)if (Array = NULL | n < 1)/判断待排序序列的有效性return false;int i,j;DataType temp;if (AscendFlag)/若为升序，进行升序排序for (i =1;i<n;i+)if (Arrayi < Arrayi-1)temp = Arrayi;j = i-1;do/寻找插入位置，将插入位置之后的当前已排序位置后移Arrayj+1 = Ar

12、rayj;j-;while (j>=0 && temp < Arrayj);Arrayj+1 = temp;else/若为降序，进行降序排序for (i =1;i<n;i+)if (Arrayi > Arrayi-1)temp = Arrayi;j = i-1;doArrayj+1 = Arrayj;j-;while (j>=0 && temp > Arrayj);Arrayj+1 = temp;return true;2.3 算法时间复杂度最好的情况下：正序有序(从小到大)，这样只需要比较次，不需要移动。因此时间复杂度为。&

13、#160;    最坏的情况下：逆序有序,这样每一个元素就需要比较次，共有个元素，因此实际复杂度为。     平均情况下：。2.4 稳定性稳定性，就是有两个相同的元素，排序先后的相对位置是否变化，主要用在排序时有多个排序规则的情况下。在插入排序中，K1是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面(没有必要插到K1的前面，这样做还需要移动！)，因此，插入排序是稳定的。、三、希尔排序算法(插入排序)3.1算法思想希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。它的基本思想

14、是先取定一个小于的整数作为第一个增量,把表的全部记录分成个组,所有距离为的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量,重复上述的分组和排序,直至所取的增量,即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。   例如：将 个记录分成个子序列：     图 希尔排序示例说明： 时，先从开始向前插入，判断，然后与比较，如此类推，这一回合后将原序列分为个组。<由后向前>3.2代码实现(C语言)/参数：Array:待排序序列，n:序列长度，Asc

15、endFlag:升降排序标志位，true为升序template <class DataType>bool ShellSort(DataType Array,int n,bool AscendFlag)if (Array = NULL | n < 1)/判断待排序序列的有效性return false;int i,j;int d = n/2;/d的初值取为n/2DataType temp;while (d > 0)for (i=d;i<n;i+)/将Arraydn-1分别插入各组当前有序区j = i - d;while(j >= 0)if (AscendFlag

16、)if (Arrayj > Arrayj+d)/将Arrayj与Arrayj+d交换temp= Arrayj;Arrayj= Arrayj+d;Arrayj+d= temp;elseif (Arrayj < Arrayj+d)/将Arrayj与Arrayj+d交换temp= Arrayj;Arrayj= Arrayj+d;Arrayj+d= temp;j = j-d;d = d/2;/递减增量dreturn true;3.3算法时间复杂度最好情况：由于希尔排序的好坏和步长d的选择有很多关系，因此，目前还没有得出最好的步长如何选择(现在有些比较好的选择了，但不确定是否是最好的)。所以

17、，不知道最好的情况下的算法时间复杂度。      最坏情况下：，最坏的情况下和平均情况下差不多。      平均情况下：。3.4稳定性由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(方便记忆：一般来说，若存在不相邻元素间交换，则很可能是不稳定的排序。)四、冒泡排序算法(交换排序)4.1算法思想冒泡排序（Bubble Sort）是一

18、种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。4.2代码实现(C语言)/参数：Array:待排序序列，n:序列长度，AscendFlag:升降排序标志位，true为升序template <class DataType>bool BubbletSort(DataType Array,int n,bool AscendFlag = true)if (Array = NULL | n <

19、1)/判断待排序序列的有效性return false;int i,j;bool IsChanged = false;/发生交换标识DataType temp;for (i = 0;i < n;i+)IsChanged = false;for (j = n-1;j >= i;j-)if (AscendFlag)if (Arrayj+1<Arrayj)temp = Arrayj+1;Arrayj+1 = Arrayj;Arrayj = temp;IsChanged = true;elseif (Arrayj+1>Arrayj)temp = Arrayj+1;Arrayj+1

20、 = Arrayj;Arrayj = temp;IsChanged = true;if (!IsChanged)/若序列是升序或降序序列，则跳出循环break;return true;4.3算法时间复杂度最好情况下：正序有序，则只需要比较次，故为。  最坏情况下:  逆序有序，则需要比较，故为。4.4稳定性排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以，它们的相对位置并没有改变，冒泡排序算法是稳定的。五、快速排序算法(交换排序)5.1算法思想它是由冒泡排序改进而来的。其基本思想是：在待排序的n个记录中任取一个记

21、录(通常取第一个记录),把该记录放入适当位置后, 通过一趟排序将要排序的数据分割成独立的两部分。其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。其最核心的思想是将小的部分放在左边，大的部分放到右边，实现分割。         5.2代码实现(C语言)/参数：Array:待排序序列，StartIndex:排序区间开始下标/EndIndex:排序区间结尾下标，AscendFlag:升降序标识，true为升

22、序template <class DataType>bool QuickSort(DataType Array,int StartIndex,int EndIndex,bool AscendFlag )/检查待排序序列的有效性if (Array = NULL | StartIndex < 0 | EndIndex <0 |EndIndex < StartIndex)return false;int i,j;DataType roll = ArrayStartIndex;/以排序区间第一个记录作为标准DataType temp;/将序列中元素以roll为基准分为独立

23、的两部分for (i = StartIndex+1,j = i;i<=EndIndex;i+)if (AscendFlag)if (Arrayi < roll)/将小于roll的值移动到左边temp = Arrayj;Arrayj = Arrayi;Arrayi = temp;j+;/记录当前满足条件的值的个数elseif (Arrayi > roll) /将大于roll的值移动到左边temp = Arrayj;Arrayj = Arrayi;Arrayi = temp;j+;temp = ArrayStartIndex;/将基准移到两个独立区间的分界点ArrayStartI

24、ndex = Arrayj-1;Arrayj-1 = temp;/对独立的两部分进行递归快速排序int split = j-1;/保存区间分界点QuickSort(Array,StartIndex,split-1,AscendFlag);QuickSort(Array,split+1,EndIndex,AscendFlag);return true;5.3算法时间复杂度最好的情况下：因为每次都将序列分为两个部分(一般两部分复杂度都和相关)，故为 。  最坏的情况下：基本有序时，退化为冒泡排序，几乎要比较次，故为。5.4稳定性由于每次都需要和中轴元素交换，因此原来的顺序就可能

25、被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以，快速排序是不稳定的。六、直接选择排序算法(选择排序)6.1算法思想直接选择排序(Selection sort)是一种简单直观的排序算法。其基本思想为：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列末尾。以此类推，直到所有元素均排序完毕。其具体做法是：选择最小的元素与未排序部分的首部交换，使所得序列的前面为有序。6.2代码实现(C语言)/参数：Array:待排序序列，n:序列长度，AscendFlag:升降排序标志位，true为升序templa

26、te <class DataType>bool SelectSort(DataType Array,int n,bool AscendFlag = true)if (Array = NULL | n < 1)/判断待排序序列的有效性return false;int i,j,mark;DataType temp,MinOrMax;for (i=0;i<n;i+)MinOrMax = Arrayi;/设置最大值或最小值为Arrayifor (j = i+1;j<n;j+)/从已排序的下一个位置开始查找if (AscendFlag)if (Arrayj < Min

27、OrMax)MinOrMax = Arrayj;/跟新最小值mark = j;/保存新的最小值的位置elseif (Arrayj > MinOrMax)MinOrMax = Arrayj;/跟新最大值mark = j;/保存新的最大值的位置if (MinOrMax != Arrayi)/若最值更新，将找到的最值与已排序序列末尾交换temp = Arrayi;Arrayi = Arraymark;Arraymark = temp;return true;6.3算法时间复杂度最好情况下：交换0次，但是每次都要找到最小的元素，因此大约必须遍历次，因此为。减少了交换次数。  

28、   最坏情况下，平均情况下：。6.4稳定性由于每次都是选取未排序序列中的最小元素与中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的。七、堆排序算法7.1算法思想堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序的基本思想是：利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或者最小)的记录。也就是说，以最小堆为例，根节点为最小元素，较大的节点偏向于分布在堆底附近。

29、0;图 堆排序算法示例7.2代码实现(C语言)7.3算法时间复杂度最坏情况下接近于，因此它是一种效果不错的排序算法。7.4稳定性堆排序需要不断地调整堆，因此它是一种不稳定的排序。八、归并排序算法8.1算法思想归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并操作的过程如下：（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置（

30、4）重复步骤3直到某一指针达到序列尾（5）将另一序列剩下的所有元素直接复制到合并序列尾 图 归并排序示例8.2代码实现(C语言)8.3算法时间复杂度最好的情况下：一趟归并需要次，总共需要次，因此为 最坏的情况下：接近于平均情况下，为 （说明：对长度为的文件，需进行 趟二路归并，每趟归并的时间为，故其时间复杂度无论是在最好情况下还是在最坏情况下均是。）8.4稳定性归并排序最大的特色就是它是一种稳定的排序算法。归并过程中是不会改变元素的相对位置的。 其缺点是，它需要的额外空间，但是很适合于多链表排序九、基数排序算法9.1算法思想基数排序(Radix sort

31、)是一种非比较型的整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。9.2代码实现(C语言)9.3算法时间复杂度9.4稳定性十、排序算法分析比较10.1直接插入排序如果目标是把n个元素的序列升序排列，那么采用直接插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。直接插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说直接插

32、入排序算法复杂度为O(n2)。因而，直接插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么直接插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。10.2希尔排序希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN)，因此中等大小规模表现良好，对规模非常大的数据排序不

33、是最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法.希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，

34、不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的10.3冒泡排序时间复杂度为O（n2），虽然不及堆排序、快速排序的O（nlogn，底数为2），但是有两个优点：1.“编程复杂度”很低，很容易写出代码；2.具有稳定性。其中若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。10.4快速

35、排序 在最好的情况，每次我们执行一次分割，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递回调用处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作 log n 次巢状的调用。这个意思就是调用树的深度是O(log n)。但是在同一阶层的两个程序调用中，不会处理到原来数列的相同部份；因此，程序调用的每一阶层总共全部仅需要O(n)的时间（每个调用有某些共同的额外耗费，但是因为在每一阶层仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。另外一个方法是为T(n)设立一个递回

36、关系式，也就是需要排序大小为n的数列所需要的时间。在最好的情况下，因为一个单独的快速排序调用牵涉了O(n)的工作，加上对n/2大小之数列的两个递回调用，这个关系式可以是：T(n) = O(n) + 2T(n/2)解决这种关系式型态的标准数学归纳法技巧告诉我们T(n) = O(n log n)。事实上，并不需要把数列如此精确地分割；即使如果每个基准值将元素分开为 99% 在一边和 1% 在另一边，调用的深度仍然限制在 100log n，所以全部执行时间依然是O(nlog n)。然而，在最坏的情况是，两子数列拥有大各为 1 和 n-1，且调用树（c

37、all tree）变成为一个 n 个巢状（nested）呼叫的线性连串（chain）。第 i 次呼叫作了O(n-i)的工作量，且递回关系式为：T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)这与插入排序和选择排序有相同的关系式，以及它被解为T(n) = O(n2)。 讨论平均复杂度情况下，即使如果我们无法随机地选择基准数值，对于它的输入之所有可能排列，快速排序仍然只需要O(n log n)时间。因为这个平均是简单地将输入之所有可能排列的时间加总起来，除以n这个

38、因子，相当于从输入之中选择一个随机的排列。当我们这样作，基准值本质上就是随机的，导致这个算法与乱数快速排序有一样的执行时间。更精确地说，对于输入顺序之所有排列情形的平均比较次数，可以借由解出这个递回关系式可以精确地算出来。在这里，n-1 是分割所使用的比较次数。因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。这意味着，它比最坏情况较接近最好情况。这个快速的平均执行时间，是快速排序比其他排序算法有实际的优势之另一个原因。讨论空间复杂度时 被快速排序所使用的空间，依照使用的

39、版本而定。使用原地（in-place）分割的快速排序版本，在任何递回呼叫前，仅会使用固定的額外空間。然而，如果需要产生O(log n)巢状递回呼叫，它需要在他们每一个储存一个固定数量的资讯。因为最好的情况最多需要O(log n)次的巢状递回呼叫，所以它需要O(log n)的空间。最坏情况下需要O(n)次巢状递回呼叫，因此需要O(n)的空间。然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是left和right，不再被认为是占据固定的空间；也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中

40、都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log2 n)空间的位元数，以及最坏情况下O(n log n)的空间。然而，这并不会太可怕，因为如果一个数列大部份都是不同的元素，那么数列本身也会占据O(n log n)的空间字节。非原地版本的快速排序，在它的任何递回呼叫前需要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，因为递回的每一阶中，使用与上一次所使用最多空间的一半，且它的最坏情况是很恐怖的，需要空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部份

41、都是不同的，每一个将会需要大约O(log n)为原来储存，导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。10.5直接选择排序选择排序的交换操作介于0和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。比较次数O(n2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+.+1=n*(n-1)/2。 交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。 交换次数比冒泡排序少多了，由于交换所需CPU时间比比

42、较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。10.6堆排序堆排序的平均时间复杂度为(nlogn)，空间复杂度为(1)。由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。10.7归并排序归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有

43、序性不敏感。若数据节点数据量大，那将不适合。10.8基数排序基数排序的时间复杂度是 O(k·n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n)，因为k的大小一般会受到 n 的影响。 以排序n个不同整数来举例，假定这些整数以B为底，这样每位数都有B个不同的数字，k就一定不小于logB(n)。由于有B个不同的数字，所以就需要B个不同的桶，在每一轮比较的时候都需要平均n·log2(B) 次比较来把整数放到合适的桶中去，所以就有：k 大于或等于 logB(n)每一轮(平均)需要 n·log2(B)

44、 次比较所以，基数排序的平均时间T就是：T  logB(n)·n·log2(B) = log2(n)·logB(2)·n·log2(B) = log2(n)·n·logB(2)·log2(B) = n·log2(n)所以和比较排序相似，基数排序需要的比较次数：T  n·log2(n)。 故其时间复杂度为 (n·log2(n) = (n·log n) 。十一、排序算法的选择(1)若n较小(如n50)，可采用直接插入或直接选择排序。     当记录