【排序算法五】快速排序

vlambda
2020-06-12

【排序算法五】快速排序

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

【算法介绍】

核心思想：分而治之

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

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

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

还是上实例吧：

例如数列：

（1）默认选中操作区间的第一个数字为关键字：

（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

【代码实现】

一趟操作：

i = L #左端点

j = 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个数字便不用排序了

i = L #左端点

j = 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) #递归右边

a = [ 5 , 3 , 6 , 4 , 6 , 13 , 8 , 7 ]

quick_sort(a, 0 , 7 )

print (a)

【小结】

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