首页 > 代码库 > 快速排序Python实现及其问题解答
快速排序Python实现及其问题解答
1.基本的快速排序算法
1 def quick_sort(arry): 2 return qsort(arry, 0, len(arry)-1) 3 4 5 def qsort(arry, left, right): 6 if left >= right: 7 return arry 8 key = arry[left] 9 lp = left10 rp = right11 while lp < rp:12 while arry[rp] >= key and lp < rp:13 rp -= 114 while arry[lp] <= key and lp < rp:15 lp += 116 arry[lp], arry[rp] = arry[rp], arry[lp]17 arry[left], arry[lp] = arry[lp], arry[rp]18 qsort(arry, left, lp-1)19 qsort(arry, lp+1, right)20 return arry
2.快速排序关于先比较右边再比较左边的解释
首先，需要说明的是，这里的先比较右边再比较左边，是基于将比较基数定为左边left，如果定为右边right，那么就要先比较左边，其他地方没有想过，类似推导吧
假设先比较左边，我们先来看一个简单的例子，例如 ls = [6, 1, 2, 7, 9]，我们的算法中初始情况下 key = 6, left = 0, right = 4, lp = 0, rp = 4
1 while lp < rp:2 while arry[lp] >= key and lp < rp:3 lp += 14 while arry[rp] <= key and lp < rp:5 lp -= 16 arry[lp], arry[rp] = arry[rp], arry[lp]7 arry[left], arry[lp] = arry[lp], arry[rp]
那么在经过第一个while循环以后，lp为3，即 arry[lp]==7, 在进行第二个while循环时，因为要arry[4]>key，而且此时rp == 4, lp ==3,所以执行while循环体，所以rp==3,此时因为lp = rp,所以推出循环，交换arry[left], arry[lp] = arry[lp], arry[rp],所以此时列表变成了[7, 1, 2, 6, 9],显然不满足，小于arry[left](之前的，那个时候为6)的都在左边，大于它的都在右边，所以先比较左边不可行，总的来说，我们总是应该先从基数的对面开始比较。
快速排序Python实现及其问题解答
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。