内部排序算法:快速排序-阿里云开发者社区

开发者社区> shiyanjuncn> 正文

内部排序算法:快速排序

简介:
+关注继续查看

基本思想

设当前待排序的数组无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:

  • 分解:

在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无需参加后续的排序。
注意:划分的关键是要求出基准记录所在的位置pivotpos,划分的结果可以简单地表示为(注意pivot=R[pivotpos]):
R[low..pivotpos-1].keys ≤ R[pivotpos].key ≤ R[pivotpos+1..high].keys
其中low≤pivotpos≤high。

  • 求解:

通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high] 快速排序。

  • 组合:

因为当“求解”步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言, “组合”步骤不需要做什么,可看作是空操作。

算法实现

快速排序算法,Java实现,代码如下所示:

01 public abstract class Sorter {
02 public abstract void sort(int[] array);
03 }
04
05 public class QuickSorter extends Sorter {
06
07 @Override
08 public void sort(int[] array) {
09 quickSort(array, 0, array.length - 1);
10 }
11
12 /**
13 * 通过划分,基于分治思想,递归执行子任务排序最后合并
14 * @param low 数组首位置索引
15 * @param high 数组末位置索引
16 */
17 private void quickSort(int[] array, int low, int high) {
18 int pivotPos; // 划分基准元素索引
19 if (low < high) {
20 pivotPos = partition(array, low, high);
21 quickSort(array, low, pivotPos - 1); // 左划分递归快速排序
22 quickSort(array, pivotPos + 1, high); // 右划分递归快速排序
23 }
24 }
25
26 /**
27 * 简单划分方法
28 * @param i
29 * @param j
30 * @return
31 */
32 private int partition(int[] array, int i, int j) {
33 Integer pivot = array[i]; // 初始基准元素,如果quickSort方法第一次调用,pivot初始为数组第一个元素
34 while (i < j) { // 两个指针从两边向中间靠拢,不能相交
35 // 右侧指针向左移动
36 while (j > i && array[j] >= pivot) {
37 j--;
38 }
39 if (i < j) { // 如果在没有使指针i和j相交的情况下找到了array[j] >= 基准元素pivot
40 array[i] = array[j]; // 基准元素放到了j指针处
41 i++; // 左侧i指针需要向右移动一个位置
42 }
43 // 左侧指针向右移动
44 while (i < j && array[i] <= pivot) {
45 i++;
46 }
47 if (i < j) { // 如果在没有使指针i和j相交的情况下找到了array[i] <= 基准元素pivot
48 array[j] = array[i]; // 基准元素放到了i指针处
49 j--; // 右侧j指针需要向左移动一个位置
50 }
51 }
52 array[i] = pivot; // 将基准元素放到正确的排序位置上
53 return i;
54 }
55 }

快速排序算法,Python实现,代码如下所示:

01 class Sorter:
02 '''
03 Abstract sorter class, which provides shared methods being used by
04 subclasses.
05 '''
06 __metaclass__ = ABCMeta
07
08 @abstractmethod
09 def sort(self, array):
10 pass
11
12 class QuickSorter(Sorter):
13 '''
14 Quick sorter
15 '''
16 def sort(self, array):
17 length = len(array)
18 self.__quick_sort(array, 0, length - 1)
19
20 def __quick_sort(self, array, low, high):
21 if low<high:
22 pivotPos = self.__partition(array, low, high)
23 self.__quick_sort(array, low, pivotPos - 1)
24 self.__quick_sort(array, pivotPos + 1, high)
25
26 def __partition(self, array, i, j):
27 pivot = array[i]
28 while i<j:
29 # right side pointer moves to left
30 while j>i and array[j]>=pivot:
31 j = j - 1
32 if i<j:
33 array[i] = array[j]
34 i = i + 1
35 # left side pointer moves to right
36 while i<j and array[i]<=pivot:
37 i = i + 1
38 if i<j:
39 array[j] = array[i]
40 j = j - 1
41 # put the pivot element to the right position
42 array[i] = pivot
43 return i

排序过程

采用分治的思想对待排序数组进行划分。分治法的基本思想是:
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序,主要是求得一个合理的划分,从而基于此划分来分治排序。使用简单划分方法的思想是:
第一步:
设置两个指针i和j,它们的初值分别为区间的下界和上界,即i=low,i=high; 选取无序区的第一个记录R[i](即R[low])作为基准记录,并将它保存在变量pivot中;
第二步:

  1. 首先,令j自high起向左扫描,直到找到第1个关键字小于pivot.key的记录R[j],将R[j]移至i所指的位置上,这相当于R[j]和基准R[i](即pivot)进行了交换,使关键字小于基准关键字pivot.key的记录移到了基准的左边,交换后R[j]中相当于是pivot;
  2. 然后,令i指针自i+1 位置开始向右扫描,直至找到第1个关键字大于pivot.key的记录R[i],将R[i]移到i所指的 位置上,这相当于交换了R[i]和基准R[j],使关键字大于基准关键字的记录移到了基准的右边, 交换后R[i]中又相当于存放了pivot;
  3. 接着,令指针j自位置j-1开始向左扫描,如此交替改变扫 描方向,从两端各自往中间靠拢,直至i=j时,i便是基准pivot最终的位置,将pivot放在 此位置上就完成了一次划分。

快速排序示例过程,如下所示:
假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49},数组大小为20。
首先,根据数组下界和上界,求得一个划分,划分过程如下:

  • 第一次划分:

初始化:i = 0,j=19,以第一个元素array[0] = 94为基准pivot = array[0] = 94。
首先指针j向前移动:
array[19] = 49<pivot = array[0] = 94,i = 0<j = 19,继续移动j指针;
array[18] = 76<pivot = array[0] = 94,i = 0<j = 18,继续移动j指针;
……
array[1] = 12<pivot = array[0] = 94,i = 0<j = 1,继续移动j指针;
i = 0pivotPos-1 = -1排序停止;右侧部分继续递归执行快速排序。

  • 第二次划分:

对于{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}:
初始化:i = 1,j=19,以第二个元素(除了第一次划分的基准元素)array[1] = 12为基准pivot = array[1] = 12。
首先指针j向前移动:
array[19] = 49>=pivot = array[1] = 12成立,并且j = 19>i = 1,j指针继续移动;
array[18] = 76>=pivot = array[1] = 12成立,并且j = 18>i = 1,j指针继续移动;
array[17] = 65>=pivot = array[1] = 12成立,并且j = 17>i = 1,j指针继续移动;
array[16] = 12>=pivot = array[1] = 12成立,并且j = 16>i = 1,j指针继续移动;
array[15] = 37>=pivot = array[1] = 12成立,并且j = 15>i = 1,j指针继续移动;
array[14] = 90>=pivot = array[1] = 12成立,并且j = 14>i = 1,j指针继续移动;
array[13] = 83>=pivot = array[1] = 12成立,并且j = 13>i = 1,j指针继续移动;
array[12] = 68>=pivot = array[1] = 12成立,并且j = 12>i = 1,j指针继续移动;
array[11] = 5>=pivot = array[1] = 12不成立,j指针停止移动:
此时i = 1<j = 11,将j指针处的元素移动到i指针处:array[1] = 5(基准元素的拷贝为pivot = 12),同时i指针向后移动一次:i++,即i = 2;
子数组变为(下面左边的12表示基准元素,实际j指针移动后并没有移动基准元素,而是pivot变量持有它的拷贝,12 处仍然是5):
{5,34,76,26,9,0,37,55,76,37,12,68,83,90,37,12,65,76,49}。
指针i向后移动:
array[2] = 34<=pivot = 12不成立,i指针停止移动:
此时i = 2<j = 11,将i指针处的元素移动到j指针处:array[11] = 34(基准元素的拷贝为pivot = 12),同时j指针向前移动一次:j–,即j = 10;
子数组变为:
{5,12,76,26,9,0,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j:i = 2= pivot = 12成立,并且j = 10>i = 2,j指针继续移动;
array[9] = 76>= pivot = 12成立,并且j = 9>i = 2,j指针继续移动;
array[8] = 55>= pivot = 12成立,并且j = 8>i = 2,j指针继续移动;
array[7] = 37>= pivot = 12成立,并且j = 7>i = 2,j指针继续移动;
array[6] = 0>= pivot = 12不成立,j指针停止移动:
此时j = 6>i = 2,将j指针处的元素array[6] = 0移动到i指针处:array[2] = array[6] = 0(基准元素的拷贝为pivot = 12),同时i指针向后移动一次:i++,即i = 3;
子数组变为(下面左边的12表示基准元素,实际j指针移动后并没有移动基准元素,而是pivot变量持有它的拷贝,12处仍然是0):
{5,0,76,26,9,12,37,55,76,37,34,68,83,90,37,12,65,76,49}。
指针i第2次向后移动:
array[3] = 76i = 3,将i指针处的元素array[3] = 76移动到j指针处:array[6] = array[3] = 0(基准元素的拷贝为pivot = 12),同时j指针向前移动一次:j–,即j = 5;
子数组变为:
{5,0,12,26,9,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j:i = 3=pivot = 12不成立,j指针停止移动:
此时j = 5>i = 3,将j指针处的元素array[5] = 9移动到i指针处:array[3] = array[5] = 9(基准元素的拷贝为pivot = 12),同时i指针向后移动一次:i++,即i = 4;
子数组变为(下面左边的12表示基准元素,实际j指针移动后并没有移动基准元素,而是pivot变量持有它的拷贝,12处仍然是9):
{5,0,9,26,12,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
指针i第3次向后移动:
array[4] = 26i = 4,将i指针处的元素array[4] = 26移动到j指针处:array[5] = array[4] = 26(基准元素的拷贝为pivot = 12),同时j指针向前移动一次:j–,即j = 4;
子数组变为:
{5,0,9,12,26,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j:i = 4<j = 4不成立,条件不满足:
将基准元素放到i指针处,array[4] = pivot = 12;并返回基准元素的索引i = 4。
划分结束。
根据得到的基准元素的索引,递归快速排序。

算法分析

  • 时间复杂度

最好情况
在最好情况下,每次划分所取的基准都是当前无序区的”中值”记录,划分的结果是基准的左、右两个无序子区间的长度大致相等,总的关键字比较次数:0(nlgn)。
最坏情况
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。
因此,快速排序必须做n-1次划分,第i次划分开始时区间长度为n-i+1,所需的比较次数为n-i(1≤i≤n-1),故总的比较次数达到最大值:
n(n-1)/2 = O(n^2)
如果按上面给出的划分算法,每次取当前无序区的第1个记录为基准,那么当文件的记录已按递增序(或递减序)排列时,每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录,则快速排序所需的比较次数反而最多。

  • 空间复杂度

快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀,则其递归树的高度为O(logn),故递归后需栈空间为O(logn)。最坏情况下,递归树的高度为O(n),所需的栈空间为O(n)。

  • 排序稳定性

快速排序是不稳定的。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
快速排序
49 38 65 97 76 13 27——————49原始 27 38 65 97 76 13 49——————49   1次 27 38 49 97 76 13 65——————49   2次 27 38 13 97 76 49 65——————49   3次 27 38 13 49 76 97 65——————49   4次 一趟快速排序   排序1: #in
981 0
排序算法(七):快速排序
快速排序是通过分治的方式,根据选定元素将待排序集合拆分为两个值域的子集合,并对子集合递归拆分,当拆分后的每个子集合中元素个数为一时,自然就是有序状态。
697 0
【算法导论】快速排序
快速排序         快速排序的最坏运行时间为O(n2),虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为O(nlogn),并且O(nlogn)中的隐含常数因子很小。
797 0
快速排序_C++
using namespace std; void Qsort(int a[], int low, int high) { if(low >= high) { return; } int first = low; int last = hi.
826 0
【算法导论】计数排序
计数排序 比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。 常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。
893 0
排序算法(十):基数排序
基数排序也可以称为多关键字排序,同计数排序类似,也是一种非比较性质的排序算法。将待排序集合中的每个元素拆分为多个总容量空间较小的对象,对每个对象执行桶排序后,则完成排序过程。
830 0
【算法导论】基数排序
基数排序 时间复杂度:O(n). 基本思路:两个数比较大小,我们的直观感觉是先比较高位,若相同则比较低位。但是这样做需要记录额外的数据,浪费空间。
782 0
+关注
85
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载