排序算法小结

排序算法小结

By 覃左言一、介绍

在计算机科学中，排序算法就是将一列元素按照某种顺序放置。最常见的顺序是数序和字典序。高效的排序算法对于优化其他需要排序操作的算法非常重要，譬如查找和归并。自从计算机科学出现以来，排序算法就得到了很大关注，譬如，冒泡排序法从1956年就已经开始被分析，尽管它也算一种解决方案，但是依然不断有新的算法涌现，例如图书馆排序算法就是在2004年的时候被首次提出的。而排序算法也常常被用来作为计算机算法的教学材料，因为大量的排序算法是阐述诸如大O记法、分治思想、数据结构、随机算法、最坏最好及平均时间度分析、时间空间权衡等概念的很好的切入点。

排序算法分类标准众多，常见的有：

?计算复杂度（就元素比较次数而言）：与待排序数组长度n相关的元素比较次数。

典型来说一个比较好的算法的复杂度可能是O(nlogn)，而较差的算法的复杂度可能

是O(n2)。

?计算复杂度（就元素交换次数而言）。

?空间复杂度：排序过程中需要使用的额外的内存大小。有些算法是“In place”算

法，也就是说它们只需要O(1)或者O(nlogn)的额外内存。

?递归性。有的算法或者是递归的或者是非递归的，还有些算法使用两种方式都可以。

?稳定性：如果一个算法在排序过程中保持等值元素在序列中的相对位置不变，则称

之为稳定的排序算法。

?是否是比较排序算法。比较排序算法在排序过程中对元素的处理仅在于使用比较操

作符比较两个元素的大小。

?适应性：输入的元素次序是否对算法运行时间产生影响。

二、不同排序算法的比较

下面表格中，我们用n表示待排序的元素个数。“Average”和“Worst”给出了平均复杂度和最坏情况下的复杂度，在计算复杂度的时候我们把比较、交换以及其他类似的操作的处理时间看作常数。“Memory”给出了空间复杂度，尤其指除去输入的元素表本身所需空间后需要的额外存储空间。

三、典型的排序算法

1、交换排序

交换排序（Exchange Sort）的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

冒泡排序（Bubble Sort）是简单而直接的交换排序算法。正如其名字一样，冒泡排序过程就是不停扫描数组，同时比较相邻的两个元素，如果这两个元素次序相反，就将他们互相交换位置，直到没有反序的记录位置。假设扫描方向是从低向高，第一次扫描完时，最大的元素必然会被交换到数组末尾，而第二趟扫描完时次大的元素必然会被交换到数组末尾，由此类推，每扫描一趟，就会有一个元素到达正确位置。整个排序过程最多经过(n-1)趟就可以完成。因此最坏时间复杂度为O(n2)。通过增加标志位可以对算法进行改进，即每一轮扫描的时候设置一个标志位，标记这一轮是否有过交换操作，如果没有，说明已经排好序了，算法可以提前结束。最好的情况，即输入已经有序的情况下，如果设置了标志位，则只需要一次扫描算法就可以结束。所以最好情况下时间复杂度为O(n)，但是平均时间复杂度仍然是O(n2)。

虽然冒泡排序是最简单的排序算法之一，而且看起来它和插入排序最坏情况下时间复杂度差不多，但是实验表明，对于随机输入，插入排序性能要明显好于冒泡排序，甚至连选择排序性能也要略好于冒泡排序，因此冒泡排序一般很少在现实中使用，通常只作为教学使用。

冒泡排序中存在有趣的“兔子与乌龟”现象。当扫描方向是从低向高时，大的元素

总是能很快地被交换到正确的位置，快得就跟“兔子”一样；但是如果小的元素出现在数组末尾，那么它被交换到数组首端的速度将会很慢（一次扫描过程只能移动一个位置），慢得就像“乌龟”一样。可以想象，如果输入数组中，最小元素出现在末尾，即使其他大部分数据都是有序，扫描次数仍然需要(n-1)次。譬如整数数组a[] = {1,2,3,4,5,6,7,8,9,0}，虽然1至9都已经有序，但是末尾的0仍然需要9次扫描才能交换到最前面。

鸡尾酒排序（Cocktail Sort）针对“兔子与乌龟”现象做了改进，又被称作“来回排序”，即排序过程不是单向扫描，而是交替地进行双向扫描。该算法在输入序列基本有序的情况下，计算复杂度接近O(n)，但是在最坏情况下时间复杂度依然是O(n2)。

梳子排序（Comb Sort）是针对“乌龟”问题的另一个改进算法，最初提出于1980年，其想法同样是去掉序列中的“乌龟”（也就是出现在序列末尾的较小的元素），基本思想类似希尔排序的缩小增量法（但希尔排序是对插入排序的改进），即每次比较的元素对之间的距离（gap）可能大于1（冒泡排序中该距离总是为1）。最开始，使gap等于数组长度除以一个缩减因子（shrink factor）并根据该gap进行类似冒泡法的排序，然后现有gap除以该缩减因子得到新的gap并根据新的gap再次排序，直到gap减至1。最后一步实际上就是冒泡排序，但是此时序列中影响性能的“乌龟”已经不存在了，因此性能得到提升。实验表明该缩减因子大约为1.3时算法性能最好，平均时间复杂度接近O(nlogn)，差不多可以和快速排序算法媲美。

奇偶排序（Odd-even Sort）是冒泡排序的另一种变形。它与冒泡算法的区别在于它首先比较所有(odd,even)对，如果有逆序则交换，然后比较所有(even,odd)对，如果有逆序则交换，如此交替迭代，直至全部有序。该过程可以看作是冒泡排序的并行版本，即两个CPU同时进行冒泡排序，只是排序的起始位置不同。该算法最坏情况时间复杂度也是O(n2)。

快速排序（Quick sort）是由C. A. R. Hoare于1962年提出的划分交换排序算法，也是当前世界上使用最多的排序算法之一。它采用了一种分治的策略，设当前待排序的无序区为R[low..high]，其基本思想可以描述为：在R[low..high]中任选一个元素作为基准（Pivot），以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有元素均小于等于基准元素，右边的子区间中所有元素的关键字均大于等于基准元素，而基准元素本身则位于正确的位置上，它无须参加后续的排序；通过递归调用快速排序对左、右子区间进行快速排序（作为递归终止条件，当子序列长度为0或者1时，序列已然有序）；当两个递归调用结束时，其左、右两个子区间已有序，对快速排序而言“合并”步骤无须做什么，可看作是空操作。

快速排序最好时间复杂度为O(nlogn)，此时，每次划分都将待排序列划分为等长的两个子序列。当子序列长度为1时递归终止，因此递归深度为logn。在递归的每一层，需要处理的元素总和都是n，因此总的时间复杂度为O(nlogn)。

但是在最差情况下，即每次划分都将待排序列划分为长度为1和n-1的子序列时，递归深度为n，此时最坏情况时间复杂度为O(n2)。

影响快速排序性能的关键在于基准元素的选择。简单的办法是选择第一个或者最后一个元素作为基准，这种方法在待排序列已经有序的情况下性能是O(n2)的；一个变体是使用中间元素作为基准，但是最坏情况复杂度依然是O(n2)；另外一种方法是取前述三种元素（第一个、中间一个和最后一个元素）的中位数作为基准，虽然这种方法在实际中效果较好，但是仍然存在特定的输入序列（称为Median-of-3 Killer）可以使算法需要O(n2)的时间；随机选择基准元素可以使得出现最坏情况的可能性降到极小，但是它为算法带来了不确定性因素，即对相同输入的两次不同运行，可能导致不一样的结果（将

运行时间也考虑为结果的一部分），另外，该方法还需要一个随机数生成器；还有一种方法称为“中位数的中位数素算法”（Median of Medians algorithm），它首先将待排序列划分为5个一组，对每组求得其中位数，然后将所有的中位数收集在一起看作新的待排序列，用同样的办法递归求它们的“中位数的中位数”，直到最后得到一个所有中位数的中位数，将其作为划分基准元素，该方法保证每次划分的比率在30%/70%到70%/30%之间，所以保证最坏情况复杂度为O(nlogn)。

从稳定性来说，快速排序是不稳定的排序。从空间复杂度来说，使用就地划分和尾递归方法实现时，快速排序只需要使用O(logn)的额外空间（用作递归栈）。在通常情况下，快速排序要快于堆排序，但是堆排序的最坏情况复杂度为O(nlogn)，因此各有优势。

自省排序（Introspective sort / Introsort）是David Musser于1997年提出来的对快速排序的改进算法。它首先使用快速排序，但是在执行过程中监控递归调用的深度，如果深度超过了某个阀值（与logn相关），就转向使用堆排序算法。因此它是集合了两种算法的优势，即最快情况时间复杂度为O(nlogn)，而性能又接近快速排序。

2、选择排序

选择排序（Selection Sort）的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

直接选择排序（Straight Selection Sort）是时间复杂度为O(n2)的选择排序，其基本过程是：找出序列中最小的元素；将最小元素与第一个位置的元素交换；将剩下的元素看作为排好序的子序列，重复前面的过程。无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为n*(n-1)/2；当初始文件为正序时，交换次数为0，而当文件初态为反序时，每趟排序均要执行交换操作，总的交换次数取得最大值n次。因此直接排序算法的平均时间复杂度为O(n2)。由于直接排序算法不需要额外辅助空间，因为空间复杂度为O(1)，即就地排序算法。

在时间复杂度O(n2)的算法中，直接选择排序要好于冒泡排序，但是通常都慢于插入排序。由于直接选择排序在每次选择下一个最小元素的时候总是需要扫描所有剩余元素，所以它的性能与输入序列的有序程度无关，有时适合用于一些实时应用。

直接选择排序与插入排序的另一个区别在于前者交换操作的复杂度为O(n)而后者为O(n2)，而交换操作需要进行写，因此在写操作明显比读操作昂贵时（譬如闪存），可以考虑使用直接选择排序。

由于在排序过程中最小元素与第一个位置的元素交换时可能导致等值元素在序列中的相对位置发生改变，因此直接选择排序是不稳定的。为了使其成为稳定的排序算法，就需要将交换操作变为插入操作（将最小元素插入首位置），但这样就需要支持高效插入和删除的数据结构，譬如链表。

堆排序（Heap Sort）是使用堆数据结构对直接选择排序的改进。通过使用堆结构，能够在O(logn)的时间复杂度找到最小元素，因此排序的平均时间复杂度为O(nlogn)。

其工作过程如下：首先将输入的所有元素插入大顶堆中；然后每次从堆顶取得最大元素，放入已排序列表中，并对堆进行重建；重复前面过程直到堆为空。

为了使空间复杂度将为O(1)，实现时使用二分堆结构存储在输入数组的未排序的部分。每次从堆顶取得最大元素后，就与堆尾元素进行交换，同时堆大小减1，这样数组中位于堆之后的有序部分就增加了一个元素；而此时堆顶元素可能不再满足堆的性质，需要在log(n)时间内对堆进行重建。

从某种程度上，堆排序可能慢于快速排序，但是由于堆排序最坏情况时间复杂度也是O(nlogn)，而快速排序最坏情况时间复杂度是O(n2)，可能遭到针对最坏情况的攻击，带来安全风险。对于关心安全问题或者具有实时限制的嵌入式系统经常使用堆排序。

而堆排序在建堆时进行的元素交换也使其成为不稳定的排序算法。

3、插入排序

插入排序（Insertion Sort）的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

直接插入排序（Straight Selection Sort）是向有序数组中一次放入一个元素的比较排序算法。简单地说，就是每一次迭代从输入数据中取得一个元素（可以是任意元素），将其插入到已经有序的数组中的正确位置，直到所有输入数据都处理完。

最好的情况，即输入数据已经有序的情况下，直接插入排序的时间复杂度是O(n)，即每次插入时只需要与有序数组的最右元素比较一次即可；最坏的情况，即输入数据逆序排列的情况下，直接插入排序的时间复杂度是O(n2)。虽然插入排序的平均时间复杂度是O(n2)，但插入排序却是待排序元数个数小于10时最快的算法之一。另外由于在n 比较小的情况下（10到20之间），插入排序比某些基于分治的排序算法如快速排序和归并排序都要快，所以常常被用来优化基于分治的排序算法，即在子序列的长度足够小时使用插入排序。

插入排序优点很多：首先它实现简单；对于小数据量它的效率很高；对于部分有序的输入具有很好的适应性；比冒泡排序和选择排序都要快；是稳定的排序算法；几乎不需要额外空间，是就地的排序算法；是在线的排序算法，每获得一个数据就将其插入正确位置，在接收数据的同时总是能得到有序列表。

希尔排序（Shell Sort）是对直接插入排序的重大改进，又被称为“缩小增量插入排序”，由Donald Shell于1959年提出。其基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。它使用较大的步长（gap）将元素向正确的位置移动，同时随着迭代轮次增加，步长逐减，直至步长为1时退化成直接插入排序，但此时整个序列已经基本有序，所以直接插入排序的效率也会很高。

从另一个角度，希尔排序的过程可以看作为：将待排序序列放置在矩阵中，使用直接插入排序将每一列排好序。重复此过程，每次使矩阵列数减少，但每一列变长。最终，该矩阵变成只有一列，此时使用直接插入排序就能使序列完全有序。

希尔排序的时间复杂度分析是个复杂的问题，针对不同的步长，有不同的最坏情况复杂度。在使用“gap=round(gap/2)”的迭代公式时，最坏情况复杂度为O(n2)；而使用Hibbard的增量序列2k-1时，最坏情况复杂度为O(n3/2)；在使用Sedgewick的增量序列9*4i+9*2i+1时，最坏情况复杂度为O(n4/3)；在使用Pratt的增量序列2i3j时，最坏情况复杂度为O(nlog2n)；还存在使最坏情况复杂度为O(nlogn)的增量序列。目前已知的最好的增量序列是[1,4,10,23,57,132,301,701,1750]，使用该序列的希尔排序要快过直接插入排序和堆排序，甚至在小数据量的情况下也快过快速排序。1750后的序列可以使用公式“gap=round(gap/2.2)”求得。

树排序（Tree sort）就是使用待排序元素为关键字，建立二分搜索树结构，然后遍历该树使得关键字按顺序输出。其常常被用来对来自文件流的数据排序。将一个元素插入二分搜索树平均时间复杂度为O(logn)，因此将n个元素全部插入树的平均时间复杂度为O(nlogn)。但是将一个元素插入非平衡的二分搜索树时，最坏情况为O(n)复杂度，这是这棵树看起来就像是一个链表，导致O(n2)的最坏时间复杂度（当使用数排序算法对已经有序序列进行排序的时候就会出现这种情况）。但是如果使用平衡二分搜索树结构，就能使算法最坏情况时间复杂度降至O(nlogn)。

图书馆排序（Library sort）于2004年提出，其与直接插入排序基本相同，只不过在数组中预留空隙以加速插入速度。它的缺陷在于它需要使用相对较多的额外空间。

小园丁高登排序（Gnome sort）被称为最简单的排序算法，其思想是基于小园丁高登将一行花盘排序的技术：他站在一行待排序的花盘旁边，观察位于他面前的相邻的两个花盘，如果这两个花盘正序（或者他已经不能再后退），则前进一步，否则交换它们的位置，并后退一步；重复此过程，直到他已经到达这行花盘最尽头，不能再往前走。

使用C语言编写代码差不多只要5行左右。该算法实际上非常类似直接插入排序，除了在将元素插入正确位置的时候使用的是类似冒泡排序的交换相邻元素法。其时间复杂度是O(n2)。

4、归并排序

归并排序（Merge Sort）最初由John von Neumann于1945年提出，利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

概括地说，归并排序工作流程如下：1、如果序列长度为0或者1，那么它已经有序；2、将待排序序列划分为两个大小差不多的子序列；3、递归使用归并排序对子序列排序；4、将排好序的子序列重新合并成一个序列。

归并排序最坏和平均时间复杂度都是O(nlogn)。设将长度为n的有序序列进行归并排序的时间为T(n)，则可以得到递归公式T(n)=2T(n/2)+n，根据“Master Theorem”可知其复杂度为O(nlogn)。

相对于快速排序来说，归并排序通常需要较少的比较次数，很多情况下也需要较少的移动次数。而且在输入序列已然有序的情况下，归并排序能到达O(n)的复杂度。

在数据只能被顺序存取的条件下，归并排序具有相当的优势，因此它比较适合于使用速度相对较慢的磁带存储作为输入和输出设备，也适合对链表结构的序列进行排序。

归并排序通常作为外排序算法的首选，此时归并排序只需要非常少的主存，并且与待排序数据的规模无关。

归并排序的缺点在于，它需要O(n)的额外空间，当然，就地算法也是能够实现的，只是比较复杂。另一方面，归并的时候也需要进行较多的数据拷贝工作，解决这一问题的可选办法是使用一个指针（或者引用）将比较键值与该键值对应的数据域关联起来，这样移动的时候只需修改指针值，而不需要移动整个数据域。

四、总结

排序算法种类众多，其中聚集了许多人的智慧，我们不仅要学习算法本身，更要学习其中蕴含的思想，启迪我们的算法思维。

五、附录

[edit] Bubble sort

Bubble sort is a straightforward and simplistic method of sorting data that is used in computer science education. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass. While simple, this algorithm is highly inefficient and is rarely used except in education. For example, if we have 100 elements then the total number of comparisons will be 10000. A slightly better variant, cocktail sort, works by inverting the ordering criteria and the pass direction on alternating passes. Bubble sort average case and worst case are both O(n2).

[edit] Insertion sort

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one. Shell sort (see below) is a variant of insertion sort that is more efficient for larger lists.

[edit] Shell sort

Shell sort was invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort. Although this method is inefficient for large data sets, it is one of the fastest algorithms for sorting small numbers of elements

[edit] Merge sort

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n).

[edit] Heapsort

Heapsort is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree. Once the data list has been made into a heap, the root node is guaranteed to be the largest(or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root. Using the heap, finding the next largest element takes O(log n) time, instead of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time.

[edit] Quicksort

Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array, we choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. This can be done efficiently in linear time and in-place. We then recursively sort the lesser and greater sublists. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice. Together with its modest O(log n) space usage, this makes quicksort one of the most popular sorting algorithms, available in many standard libraries. The most complex issue in quicksort is choosing a good pivot element; consistently poor choices of pivots can result in drastically slower O(n2) performance, but if at each step we choose the median as the pivot then it works in O(n log n).

[edit] Bucket sort

Bucket sort is a sorting algorithm that works by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. Thus this is most effective on data whose values are limited (e.g. a sort of a million integers ranging from 1 to 1000). A variation of this method called the single buffered count sort is faster than the quicksort and takes about the same time to run on any set of data.

[edit] Radix sort

Radix sort is an algorithm that sorts a list of fixed-size numbers of length k in O(n· k) time by treating them as bit strings. We first sort the list by the least significant bit while preserving their relative order using a stable sort. Then we sort them by the next bit, and so on from right to left, and the list will end up sorted. Most often, the counting sort algorithm is used to accomplish the bitwise sorting, since the number of values a bit can have is minimal - only '1' or '0'.

[edit] Distribution sort

Distribution sort refers to any sorting algorithm where data is distributed from its input to multiple intermediate structures which are then gathered and placed on the output. It is typically not considered to be very efficient because the intermediate structures need to be created, but sorting in smaller groups is more efficient than sorting one larger group.

[edit] Shuffle sort

Shuffle sort is a type of distribution sort algorithm (see above) that begins by removing the first 1/8 of the n items to be sorted, sorts them recursively, and puts them in an array. This creates n/8 "buckets" to which the remaining 7/8 of the items are distributed. Each "bucket" is then sorted, and the "buckets" are concatenated into a sorted array.