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

开发者社区> 人工智能> 正文
登录阅读全文

内部排序算法:快速排序

简介:

基本思想

设当前待排序的数组无序区为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)。

  • 排序稳定性

快速排序是不稳定的。

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

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章