排序算法

排序算法

1  排序

       排序是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个相知有序的序列。排序分为两类：内部排序和外部排序。

1.1  内部排序

内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。内部排序算法包括冒泡排序、选择排序、堆排序、插入排序、希尔排序、快速排序、归并排序。

1.2  外部排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

2  内部排序算法

2.1  冒泡排序

冒泡排序的基本思想是：对待排序记录关键字从后往前进行多次扫描，当发现相邻两个关键字的次序与排序要求的规定不符时，就将这两个记录进行交换。这样，关键字较小的记录将逐渐从后向前移动，就像气泡在水中向上浮一样，所以该算法称为冒泡排序算法。

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3、针对所有的元素重复以上的步骤，除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2.1.1 时间复杂度

       冒泡排序的时间开销主要在外循环和内循环以及判断和交换元素的时间开销。

       1、最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[n(n-1)] / 2，最优的情况时间复杂度为：O( n^2 )。

       2、最差的情况也就是开始的时候元素是逆序的，那么每一次排序都要交换两个元素，则时间花销为：[3n(n-1)] / 2,（其中比上面最优的情况所花的时间就是在于交换元素的三个步骤）；最差的情况下时间复杂度为：O( n^2 )。

       3、最优时间复杂度可以从O( n^2 )降到O(n)，可以借助标志位来判断是否已经排序好序，遍历一遍如果没有进行交换，如果没有进行交换说明序列已经排序好序了，所以最优时间复杂度为：O( n )。

2.1.2 空间复杂度

排序过程中需要一个辅助内存，所以空间复杂度为O(1)。

2.1.3  稳定性

       冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是稳定排序算法。

2.2  选择排序

选择排序算法基本思想：对n个记录进行扫描，选择最小的记录，将其输出，接着在剩下的n-1个记录中输出,不断重复这个过程，直到剩下一个记录为止。排序过程如下图：

2.2.1  时间复杂度      

1、比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2，所以时间复杂度O(n^2）。

2、交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

2.2.2  空间复杂度

因为只需要一个辅助的内存交换空间，所以空间复杂度O(1)。

2.2.3  稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

2.3  堆排序

堆是一个完全二叉树，树中每个结点对应于源数据的一个记录，并且每个结点应满足以下条件：非叶子结点的数据大于或等于其左、右孩子结点的数据（若是按从大到小的顺序排序，则要求非叶子结点的数据小于或等于其左、右孩子结点的数据）。

由堆的定义可以看出，其根结点为最大值，堆排序就是利用这一特性进行的。堆排序过程包括两个阶段：

1、  将无序的数据构成堆。

2、  将当前无序区的堆顶元素同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

2.3.1  时间复杂度

       它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。

1、在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。

2、在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为log2i＋1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。

3、总体来说，堆排序的时间复杂度O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。

2.3.2  空间复杂度

因为只需要一个辅助的内存交换空间，所以空间复杂度O(1)。

2.3.3  稳定性

堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就是跳跃式交换数据，会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序是不稳定的排序算法。

2.4  插入排序

       插入排序的算法描述是一种简单直观的排序算法。他的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后移动，为最新元素提供插入空间。排序过程如下图：

2.4.1  时间复杂度

1、在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第n个元素，要考虑前 n - 1 个元素。因此，最坏情况下的比较次数是 1 + 2 + 3 + ... + (n - 1)，等差数列求和，结果为 n^2 / 2，所以最坏情况下的复杂度为 O(n^2)。

2、最好情况下，数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为O(n)。

2.4.2  空间复杂度

因为只需要一个辅助的内存交换空间，所以空间复杂度O(1)。

2.4.3  稳定性

       插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，所以插入排序是稳定的排序算法。

2.5  希尔排序

       希尔排序又称为缩小增量排序，也属于插入排序类算法，是对直接插入排序的一种改进。

       基本思想就是：将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使需要排序的数列基本有序，这样再使用一次直接插入排序。这样，首先对数量较小的序列进行直接插入排序可提高效率，最后对基本有序的序列进行直接插入排序，也可提高效率，从而使整个排序构成的效率得到提升。排序过程如下图：

2.5.1  时间复杂度

       希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。

2.5.2  空间复杂度

因为只需要一个辅助的内存交换空间，所以空间复杂度O(1)。

2.5.3  稳定性

      由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的排序算法。

2.6  快速排序

快速排序使用分治策略来把待排序数据序列分为两个子序列，具体步骤为：

1、  从数列中挑出一个元素，称该元素为“基准”。

2、  扫描一遍数列，将所有比“基准”小的元素排在基准前面，所有比“基准”大的元素排在基准后面。

3、  通过递归，将各子序列划分更小的序列，直到把小于基准值元素的子数列和大于基准值元素的子数列排序。

2.6.1  时间复杂度

1、快速排序最优的情况就是每一次取到的元素都刚好平分整个数组，最优的情况下时间复杂度为：O(nlogn)。

2、快速排序最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了，最差的情况下时间复杂度为：O(n^2)。

2.6.2  空间复杂度

首先就地快速排序使用的空间是O(1)的，也就是个常数级，而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据。

1、每一次都平分数组是最优情况的空间复杂度为：O(logn)。

2、退化为冒泡排序是最差情况的空间复杂度为：O( n )。

2.6.2  稳定性

       快速排序算法：

1、center_index是中枢元素的数组下标，一般取为数组第0个元素。

2、左边的i下标一直往右走，当a[i] <= a[center_index]，右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。

3、在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱。

例如：序列为 6 2 5 2 7 9 11。

现在中枢元素6和2(第4个元素，下标从1开始计)交换就会把元素2的稳定性打乱，不稳定发生在中枢元素和a[j]交换的时刻，所以快速排序是一个不稳定的排序算法。

2.7  归并排序

归并排序就是将两个或多个有序表合并成一个有序表。归并操作的工作原理：

1、  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。

2、  设定两个指针，最初位置分别为两个已经排序序列的起始位置。

3、  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。

4、  重复步骤3直到某一指针超出序列尾。

5、  将另一序列剩下的所有元素直接复制到合并序列尾。

2.7.1  时间复杂度

归并排序时间开销主要是数组划分函数和有序数组归并函数，不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都为：O( nlogn )。

2.7.2  空间复杂度

归并排序的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间，所以空间复杂度为：O(n)。

2.7.3  稳定性

       归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换)，然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。在序列合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

3  排序算法性能对比

       排序算法的时间复杂度、空间复杂度、稳定性是排序算法性能考核的主要指标，下面我们用表格列出排序算法的这些指标的对比。