快速排序是一种运用非常广的算法,但不是那么好理解。
假设有下面一组数据,需要从小到大升序排列。
快速排序的算法是
1. 确定不用排序的条件
2. 确定每次排序时,选择排序的基准值(pivot)
3. 排序依据,将当前数组中,所有比 pivot 大的数值存放到新的数组 right 挪到右边,所有比 pivot 小的数值存放到一个新的数组 left 挪到左边,然后一起拼接起来。
4. 利用递归思想,调用快速排序对 left 和 right 数组分别进行排序。
快速排序的过程比较抽象,但其实核心思想就是分治。
把复杂的问题分割成若干个同样的简单的问题,也就是化繁为简。
当然,分治思想不仅仅只是运用在快速排序上。
在快速排序中,利用分治,我们可以设定这样的条件。
最简单的问题就是长度为 1 或者为 0 的数组的排序。
因为,它们根本就不再需要排序了。
所以,快速排序就要想尽办法,创造这样的条件。
图例示意:
每次对一个新的数组排序时,选取一个值作为 pivot,这里选择了第一个。
上图中,第一趟选择了 2 作为 pivot,所以将 1 挪到了左边,6 和 4 挪到了右边。
左边的数组值有 1 ,所以它不需要排序,直接作为返回。
右边的数组有 6 和 4 两个数,所以,它还是要重新排序。
右边的数组需用 6 作为 pivot,那么 4 就挪到 6 的左边。
最终排序的结果就是 1、2、4、6。
快速排序的时间复杂度是 O(nlogn)O(nlogn)O(nlogn)
Python 代码演示:
def quick_sort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less_arr =[]
for x in arr:
if x < pivot:
less_arr.append(x)
bigger_arr =[]
for x in arr:
if x > pivot:
bigger_arr.append(x)
return quick_sort(less_arr) + [pivot] + quick_sort(bigger_arr)
if __name__ == "__main__":
arr = [3,2,8,4,1,6,5]
print("=======================")
print(arr)
result = quick_sort(arr)
print("=======================")
print(result)
运行结果如下:
=======================
[3, 2, 8, 4, 1, 6, 5]
=======================
[1, 2, 3, 4, 5, 6, 8]
可以看到,排序结果正确。
快速排序的时间复杂度是 O(nlogn)O(nlogn)O(nlogn)
这是个平均值。
快速排序最糟糕的情况是算法复杂度是 O(n2)O(n^2)O(n2)
快速排序会进行多趟,每一趟的时间复杂度是 O(n)O(n)O(n),递归调用的次数相当于递归树的层数O(logn)O(logn)O(logn),所以总共的复杂度就是O(nlogn)O(nlogn)O(nlogn)。