本文共 2331 字,大约阅读时间需要 7 分钟。
目录
快速排序又称为分割交换排序法,是目前公认最佳的排序法,也是使用“分而治之"的方式,先会在数据中找到一个虚拟的中间值,并按此中间值将所有打算排序的数据分为两部分。其中小于中间值的数据放在一边,而大于中间值的数据放在另一边,再以同样的方式分别处理左右两边的数据,直到排序完成为止。
以一串数据 72, 6, 57, 88, 60, 42,83, 73, 48, 85 为例进行快速排序,将数据按照数值由小到大的顺序排序。
排序前:
72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
我们假设虚拟的中间值总位于未排序部分的最左端,因此,第一次划分的虚拟中间值x应该是72。即 x => 72。
我们将待排序数列的最左端下标变量为left = 0,最右端下标变量为right = length - 1 = 9。同时设置两个游标 i = left, j = right。
因此排序前的数列如下:
72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
x, left, i | right, j |
Step1
我们将游标j缓慢的向左移动,找到一个小于虚拟中间值的数字。显然,当游标j移动到48时,此时48 < 72 = x,因此48就是我们要找的数。此时让游标 i 对应位置的数据值填入48。
48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
left, i | j | right |
( x = 72 )
填入数据后,i 向右移动一格。
48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
left | i | j | right |
接下来我们将游标 i 缓慢的向右移动,找到一个大于虚拟中间值的数字。显然,当游标 i 移动到88时,此时88 > 72 = x,因此88就是我们要找的数。此时让游标 j 对应的位置的数据值填入88。
48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 88 | 85 |
left | i | j | right |
( x = 72 )
填入数据后,j 向左移动一格。
48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 88 | 85 |
left | i | j | right |
Step2
经过一轮移动后,并没有完全将虚拟中间值72把数列分开。因为此时两个游标并没有遍历完全部数据。
我们继续将游标 j 缓慢的向左移动,重复上面的规则,找到一个小于虚拟中间值的数字。显然,当游标 j 移动到42时,此时 42 < 72 = x,因此42就是我们要找的数。此时让游标 i 对应位置的数据值填入42。
48 | 6 | 57 | 42 | 60 | 42 | 83 | 73 | 88 | 85 |
left | i | j | right |
填入数据后,i 向右移动一格。
48 | 6 | 57 | 42 | 60 | 42 | 83 | 73 | 88 | 85 |
left | i | j | right |
我们继续将 i 缓慢向右移动,来寻找一个大于虚拟中间值的数字。当 i 再次向右移动的时候,我们发现此时 i 和 j 对应的下标重叠了。也就是说,i 左边的数字没有大于虚拟中间值的数字,而 j 右边的数字没有小于虚拟中间值的数字,此时 i 和 j 交汇的点就是本轮排序虚拟中间值所在的位置。将虚拟中间值填入该位置中:
48 | 6 | 57 | 42 | 60 | 72 | 83 | 73 | 88 | 85 |
left | i, j | right |
至此,虚拟中间值72找到了它应该所在的位置上。我们使用重复的逻辑对72之前的数列 48, 6, 57, 42, 60 和 72之后的数列 83, 73, 88, 85 进行排序,最终得到排好序的数列。
def quick_sort(array, left, right): if left >= right: return i = left j = right x = array[i] while True: # 从j开始向前找一个小于或等于x的数 while j >= i: if array[j] <= x: break j -= 1 if i >= j: array[i] = x break array[i] = array[j] i += 1 # 从i开始向后找一个大于x的数 while i < j: if array[i] > x: break i += 1 if i >= j: array[i] = x break array[j] = array[i] j -= 1 quick_sort(array, left, i-1) quick_sort(array, i+1, right)if __name__ == '__main__': demo = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85] quick_sort(demo, 0, len(demo)-1) print(demo)
转载地址:http://kdsoi.baihongyu.com/