vlambda博客
学习文章列表

【排序算法 五】快速排序

快速排序是效率最高的排序算法之一,与归并排序一样有着广泛的应用。


【算法介绍】

核心思想:分而治之

①将数列根据第一个数字分为两段,其左端是小于该数字的,右端是大于该数字的

②再次对分割出的左右两段进行操作


不难看出,对于①步骤结束后,是左右两段排序的子问题,所以一般情况下快速排序利用递归实现。


还是上实例吧:

例如数列:

6
3 7 13 5 4 8 6

(1)默认选中操作区间的第一个数字为关键字:

6
3
7 13
5 4
8 6

(2)①设置右端点j,从右向左找到"小于等于"关键字的数








j
6
3
7 13
5 4
8 6


②设置左端点i,从左向右寻找"大于"关键字的数




i




j
6
3
7 13
5 4
8 6

③交换i和j:



i




j
6
3
6 13
5 4
8 7

④j继续寻找"小于等于"关键字的数:



i


j

6
3
6 13
5 4
8 7

⑤i继续寻找"大于"关键字的数:




i
j

6
3
6 13
5 4
8 7

⑥交换i和j:




i
j

6
3
6 4 5 13
8 7

⑦j继续寻找"小于等于"关键字的数:




i j


6
3
6 4 5 13
8 7

⑧i继续寻找"大于"关键字的数过程中与i和j重叠,循环结束





ij


6
3
6 4 5 13
8 7

⑧交换关键字与i,一趟结束:





i、j


5
3
6 4 6 13
8 7

⑨至此,区间被分为"小于等于6"与"大于6"两部分,继续递归操作[1,4]区间[6,8]区间……(中间的i(j)位置的数字已经在正确的位置上了,无需再排序):





ij


5
3
6 4 6 13
8 7

【代码实现】

一趟操作:

=  L   #左端点
=  R   #右端点
while  i<j:   #当ij重叠跳出
     while  a[j]>a[L]  and  i<j: j  - =  1
     while  a[i]< = a[L]  and  i<j: i  + =  1
     tmp  =  a[i]; a[i]  =  a[j]; a[j]  =  tmp   #每次交换ij

tmp = a[L]; a[L] = a[i]; a[i] = tmp 

#跳出后交换第一个数与a[i]

剩下的,我们只需进行递归操作即可:

完整代码:

def quick_sort(a :[], L: int, R: int):

#需要参数表示区间的左右端点

     if  L> = R:  return #当只有1个数字便不用排序了
     =  L   #左端点
     =  R   #右端点
     while  i<j:   #当ij重叠跳出
         while  a[j]>a[L]  and  i<j: j  - =  1
         while  a[i]< = a[L]  and  i<j: i  + =  1
         tmp  =  a[i]; a[i]  =  a[j]; a[j]  =  tmp  #每次交换ij
     tmp  =  a[L]; a[L]  =  a[i]; a[i]  =  tmp  #跳出后交换第一个数与a[i]
     quick_sort(a, L, i - 1 #递归左边
     quick_sort(a, i + 1 , R)  #递归右边
=  [ 5 , 3 , 6 , 4 , 6 , 13 , 8 , 7 ]
quick_sort(a,  0 7 )
print (a)

【小结】

快速排序的本质是分治思想,其时间效率的期望值是O(NlogN),但是在极端数据下(例如5、4、3、2、1,要求进行升序排序),不难发现每次划分的区间长度都是原区间长度减1,最后会退化成完全的冒泡排序(网上也有说法快速排序就是冒泡排序的优化,这可以理解为冒泡的交换位置只能相邻,而快速排序的交换位置更远,所以速度更快)。