type
status
date
slug
summary
tags
category
icon
password
摘要: 排序算法的好坏决定着程序运行速度的快慢，追求一个更高性能的算法始终是人们的目标。在综述了11种不同算法后，本人为了达到提高排序算法的效率并且减少数据排序时间的目的，从随机选取关键元素、双向索引和小数组插入排序三个方面对快速排序算法进行优化。最后经过实验测试验证，改进后的快速排序算法的效率有很大提高，具有非常深远的现实意义。关键词: 排序算法、快速排序、复杂度Abstract: The quality of the sorting algorithm determines the speed of the program, and the pursuit of a higher performance algorithm is always the goal of people. After reviewing 11 different algorithms, in order to improve the efficiency of the sorting algorithm and reduce the data sorting time, I optimized the quick sorting algorithm from three aspects: random selection of key elements, bidirectional index and small array insertion sorting. Finally, the experimental results show that the efficiency of the improved quick sort algorithm has been greatly improved, which has a very far-reaching practical significance.Key Words: Sorting algorithm; Quick sort; Complexity
1 引言2 排序算法综述及情况介绍2.1 冒泡排序2.2 冒泡排序(优化版)2.3 选择排序2.4 选择排序(优化版)2.5 直接插入排序2.6 希尔排序2.7 快速排序2.8 堆排序2.9 归并排序2.10 MSD基数排序2.11 LSD基数排序3 快速排序算法的优化过程3.1 随机选取枢轴3.2 双向索引3.3 小数组插入排序4 实验结果6 结语参考文献
1 引言
在注重效率的今天，排序作为一种提高查询效率的手段越来越被人们所重视。大数据与云计算广泛应用后，若仅获取到大量的杂乱无序的数据而没有一定的规则来进行排列和查询，会给信息交换工作带来极大不便，因此对排序的研究在理论上和实践上都有重要的价值。以往，计算机存储资源的不足制约着程序的排序效率，但是在计算机存储设备急速发展的今天，存储空间已经不是排序算法的局限，只需利用计算机的高速运算能力，再配合高效、合适的排序算法，就能够减少排序时间，使信息交流和查找的效率得到极大提高。
2 排序算法综述及情况介绍
人们已经改进了多种排序算法，使排序效率有了不同程度的提升，例如，对冒泡排序法采用了设立标志位的方法，以减少其排序的循环次数。但是这些优化过的排序算法都只适用于小数组，对大量杂乱的数据排序效率并不高。本文优化快速排序算法，使其适用于处理规模越来越大的数据，符合技术发展的要求。
以下是各类排序算法综述：
2.1 冒泡排序
冒泡排序（Bubble Sort）是一种简单直观的排序算法。假设长度为n的数组arr[]，要按照从小到大排序。则冒泡排序的具体过程可以描述为：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置。这样操作后数组最右端的元素即为该数组中所有元素的最大值。接着对该数组除最右端的n-1个元素进行同样的操作，再接着对剩下的n-2个元素做同样的操作，直到整个数组有序排列。
冒泡排序算法的原理如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法分析：
若初始序列是有序的，则比较次数为O(n2)，交换次数为0；
若初始系列是逆序的，则比较次数为O(n2),交换次数为O(n2)；
所以冒泡排序最好的时间复杂度和最坏的时间复杂度都是O(n2);
对于冒泡排序来说，每次交换都是相连的两个元素进行的，没有发生长距离的交换，所以不存在相同关键码元素会倒置的情况，即冒泡排序是一种稳定的算法。
冒泡排序适用于数据量很小的排序场景，因为冒泡的实现方式较为简单。
2.2 冒泡排序(优化版)
鉴于冒泡排序不管最好情况与最坏情况比较次数都是O(n2)，考虑到在某些情况下其实并不需要比较n-1趟起泡就可以完成排序，例如，在一个完全有序情况下，只需要比较n-1次即可完成排序。
不仅如此，普通冒泡排序还有一个缺点，对于每一趟比较时，很多情况下，只是前面一部分序列需要排序，而后面一部分序列已经处于有序的情况，不需要比较和交换。
针对上述两个缺点，我们对冒泡排序进行优化：
- 定义变量sort_border，用于指示无序序列的边界
- 定义变量is_order，用于指示本趟冒泡排序结果是否发生交换，如果没有则可以说明此事已经排好序。
算法分析：
若初始序列是部分有序甚至完全有序的，则比较次数可以降低为O(n)。
对于冒泡排序来说，每次交换都是相连的两个元素进行的，没有发生长距离的交换，所以不存在相同关键码元素会倒置的情况，即冒泡排序是一种稳定的算法。
2.3 选择排序
选择排序（Selection sort）是一种简单直观的排序算法，简称为选排。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序算法通过选择和交换来实现排序，其排序流程如下：
- 首先从原始数组中选择最小的（或最大的）1个数据，将其和位于第1（n）个位置的数据交换。
- 接着从剩下的n-1个数据中选择次小的1个元素，将其和第2（n）个位置的数据交换。
- 然后，这样不断重复，直到最后两个数据完成交换。最后，便完成了对原始数组的从小到大的排序。
算法分析：
选择排序比较次数为O(n2），与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
对于选择排序来说，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，发生了长距离的交换，那么交换后稳定性就被破坏了，即选择排序是一种不稳定的算法。
2.4 选择排序(优化版)
在一般选择排序时每趟遍历中只挑选了最小的元素，但其实可以在这一趟遍历中把最大值也选出来。选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半。
算法分析：
利用这种优化方法后，降低了选择排序的时间复杂度系数，循环次数减半。选择排序适用于待排序列元素个数较少时。
2.5 直接插入排序
直接插入排序也是一种常见的排序算法，插入排序的思想是：将初始数据分为有序和无序两个部分，每一次将无序部分的第一个数据插入到前面已经排好序的有序部分中，原来位置上的元素依次向后顺移，直到插完所有元素为止。
插入排序的步骤如下：
- 每次从无序部分中取出首元素，
- 与有序部分中的元素从后向前依次进行比较，并找到合适的位置，
- 将原本位置上的元素向后顺移，将该元素插到有序序列当中。
重复以上三步，直到最后一个元素也插入有序序列。
算法分析：
- 当待排序序列是有序时，是最优的情况，只需当前数跟前一个数比较次，这时一共需要比较n- 1次，时间复杂度为O(n)。
- 当待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+n-1，所以，插入排序最坏情况下的时间复杂度为O(n2)。
综上，插入排序在平均情况运行时间是O(n2)。
直接插入排序是一种稳定的排序方式。适用于待排元素不多，且基本有序的情况。
2.6 希尔排序
希尔排序(Shell sort)又称为缩小增量排序(diminishing-increment sort)，是对直接插入排序的一种升级迭代，优化之处在于：不用每次插入一个无序序列中的元素时，就和序列中前面有序部分中的所有元素进行比较，更加适用于直接插入排序的适用场景——元素较少且基本有序。
该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数gap（gap<n）作为间隔，所有距离为gap的元素放在同一个子序列中（分成gap个子序列），在每一个逻辑数组中分别实行直接插入排序。然后缩小间隔gap，重复上述子序列划分和排序工作。直到最后取gap=1，将所有元素放在同一个序列中排序为止。
综上所述，希尔排序的实现步骤如下：
- 确定gap的值，划分子序列，子序列内进行直接插入排序。
- 不断缩小gap，继续在每个子序列进行插入排序。
重复第二步，直到gap==1，在包含所有元素的序列内进行直接插入排序。
算法分析：
本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多,希尔排序的时间的时间复杂度为O(n1.3)，希尔排序时间复杂度的下界是nlog2n。希尔排序对于中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n2)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。
2.7 快速排序
快速排序(Quick sort)的基本思想是:通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用，最终能够实现将所需排序的无序序列元素变为一个有序的序列。
本项目实现了左右指针法的快速排序，具体流程如下：
- 选定一个最左边或是最右边的元素key。
- 定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要begin先走）。
- 以最左边的值为key为例：在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。
- 此时key的左边都是小于key的数，key的右边都是大于key的数。
- 将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时得到有序序列。
算法分析：
快速排序的平均时间复杂度为O(nlog2n)，由于快速排序是递归的需要有一个栈存放每层递归调用时的指针和参数，最大递归调用层数与递归树的深度一致，因此要求存储开销为O(log2n)。
快速排序适用于待排序序列元素较多，并且元素较无序的情况，并且当元素个数很小时，快速排序往往比其他简单排序方法还要慢。
2.8 堆排序
堆排序(heap sort)是一种重要的选择排序方法，它只需要一个记录大小的辅助存储空间，每个待排序的记录仅占用一个记录大小的存储空间，因此弥补了树形选择排序的弱点。一般升序采用大顶堆，降序采用小顶堆。
堆排序的基本流程如下：
- 将这n条记录按关键字值的大小建立堆（称为初始堆）。
- 然后将堆顶的元素，与最后一个元素交换，获得最大元素。
- 接着将剩余无序序列，调整成小顶堆，重复步骤2，获得每一次调整后的最大值
直到调整到根，从而获得排序序列
算法分析：
空间复杂度：需要一个记录辅助存储空间，O(1)
最好、最坏时间复杂度：O(nlog2n)
堆排序涉及长距离交换，是一种不稳定的排序算法。
2.9 归并排序
归并排序（Merge Sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
首先将整个无序序列通过递归分为一个个子序列，以每个子序列只有一个元素或只有两个元素作为终点，在合并时将一个个有序的子序列按照一定规则合并成一个个有序的长序列。即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。
在进行元素比较和交换时，若两个元素大小相等则不必交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。
算法分析：
归并排序速度仅次于快速排序。归并算法是一个不断递归的过程，假设数组的元素个数是n。时间复杂度是T(n)的函数: T(n) = 2*T(n/2) + O(n)，整体的复杂度为O(nlog2n)。因为归并排序需要一个与原数组相同长度的数组做辅助来排序，所以空间复杂度为O(n)。
2.10 MSD基数排序
基数排序又被称为桶排序。而基数排序首先将待排序数据元素依次“分配”到不同的桶里，然后再把各桶中的数据元素“收集”到一起。通过使用对多关键字进行排序的这种“分配”和“收集”的方法，基数排序实现对单关键字进行排序。
基数排序通常分为最高位优先法和最低位优先法。
最高位优先法MSD (Most Significant Digit first)通常是一个递归的过程：
设每个元素的关键字为k1k2k3k4...kd
- 首先根据最高位关键字k1进行排序，按k1值的不同，将整个数据表分成若干个子表，每个子表中的数据元素具有相同的关键字k1。
- 然后分别对每一个每个子表中的数据元素根据关键字(k2，…，kd)用最高位优先法进行排序。
不断递归，直到对关键字kd完成排序为止。
算法分析：
- 平均时间复杂度：O(d*n) (d为整数的最高位数)
空间复杂度:O(10n)
MSD基数排序是一种稳定的算法，适用于位数比较多的序列。
2.11 LSD基数排序
最低位优先法LSD (Most Significant Digit first)流程：
设每个元素的关键字为k1k2k3k4...kd
- 首先依据最低位关键字kd对数据表中所有数据元素进行一趟排序;
- 然后依据次低位关键字kd-1对上一趟排序的结果再排序。
- 依次重复，直到按关键字k1完成最后一趟排序。
- 平均时间复杂度：O(d*(n+r)) (d为整数的最高位数)
- 空间复杂度:O(n+r)
- LSD基数排序是一种稳定的算法，适用于位数比较少的序列。
算法 | 时间复杂度 | ㅤ | ㅤ | 空间复杂度 | 稳定性 |
ㅤ | 平均情况 | 最怀情况 | 最好情况 | ㅤ | ㅤ |
冒泡排序 | O(n²) | O(n2) | O(n) | O(1) | 是 |
选择排序 | O(n²) | O(n2) | O(n2) | O(1) | 否 |
直接插入排序 | O(n²) | O(n2) | O(n) | O(1) | 是 |
希尔排序 | 0(n1.3) | O(n2) | O(n) | O(1) | 否 |
堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 否 |
快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(log2n) | 否 |
归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 是 |
LSD基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 是 |
MSD基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 是 |
表1 排序算法比较
3 快速排序算法的优化过程
为了能够通过减少交换和比较次数来减少排序时间，我们对快速排序算法进行了3步优化，即随机选取枢轴、双向索引和小数组插入排序。
因为在原始的快速排序中，每趟排序的枢轴元素都是选取待排序数据区间最前端或者最末端元素，即固定基准点，这样，如果数组是有序的，则排序的时间复杂度就会退化到最坏的情况0（n2），且每趟排序对每个子序列只产生一个有序位置，所以对数组中相等元素的处理效率不是很高。
3.1 随机选取枢轴
快速排序在最佳情况下的时间复杂度是O（nlog2n），最坏情况下是0（n2）。在对有序数组排序时，快速排序算法的性能会退化到最坏情况，如利用随机产生器产生一个随机位置作为下标，则可避免因选择固定基准点而产生最坏情况。改进后的代码如下：
3.2 双向索引
扫描过程如图1所示。假设数组的前端坐标为p，末端坐标为r，采用两个下标索引i、j分别从数组的首、末两端向中间进行扫描。当i遇到比基准点（即图1（a）中的T）小的元素时，就将此元素与p+1位置的元素进行交换，同时p加1；当j遇到比基准点大的元素时，就将此元素交换至r位置，同时r减1。这一过程直到当j小于等于i时停止。这样，最终的划分点便落在j，再将基准点交换到j上，用以上方法递归排序j点左右两端的子序列，以此类推，直至排序完成。
改进后的代码如下：
3.3 小数组插入排序
插入排序的时间复杂度是0（n2）；但是对有序排列的数组，插入排序的最佳情况是0（n）。插入排序中包含的常数因子使得当n较小时，算法运行得较快。因此，当数组递归子序列的规模在一个固定阀值（阀值指数组的最大长度）以下时，采用插入排序对子序列进行排序，能够缩短排序时间。测试结果表明，阀值在7个元素左右时效率较高。改进后的代码如下：
4 实验结果
图2为数据规模n为50万个元素时，快速排序优化前后的对比图。从图2可以看出，优化后的排序时间比优化前大大缩短，排序的效率大大提升。
图1 快速排序优化前后对比
6 结语
针对排序的比较次数和移动交换次数，文中讨论了快速排序算法以及插入排序算法的优化策略，对比了算法优化前后的排序时间。结果表明，优化后的算法对各种数组的排序效率很高，符合目前对效率的要求，达到了优化的目的。
参考文献
- 严蔚敏，吴伟民.数据结构［M］.北京：清华大学出版社，2009：265-279.
- 张晓刚，李明树.智能搜索引擎技术的研究与发展［J］.计算机工程与应用，2001（24）：67-70.
更多有关数据结构课程资料，参见git数据结构版块
- Author:S+M
- URL:http://www.sujiaming.top/article/quick-sorting
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!