搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 派先生的算法小屋 > 【排序算法 五】快速排序

【排序算法 五】快速排序

派先生的算法小屋 2020-06-12

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


【算法介绍】

核心思想:分而治之

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

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


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


还是上实例吧:

例如数列:

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,最后会退化成完全的冒泡排序(网上也有说法快速排序就是冒泡排序的优化,这可以理解为冒泡的交换位置只能相邻,而快速排序的交换位置更远,所以速度更快)。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《【排序算法 五】快速排序》的版权归原作者「派先生的算法小屋」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注派先生的算法小屋微信公众号

派先生的算法小屋微信公众号:gh_d9a0ee6e6244

派先生的算法小屋

手机扫描上方二维码即可关注派先生的算法小屋微信公众号

派先生的算法小屋最新文章

精品公众号随机推荐