快速排序
1. 介绍
快速排序是一种高效的排序算法,它采用“分而治之”的思想。其原理是:对于一组给定的记录,通过一趟排序后,将原序列分成两部分,其中前部分的所有记录均比后面部分的所有记录小,然后再依次对前后两部分的记录进行快速排序,递归该过程,直到序列中的所有记录均有序为止。
具体算法步骤如下:
(1) 分解: 将输入的序列array[m,…,n]划分成两个非空子序列array[m,…,k]和array[k+1,…,n],使array[m,..,k]和array[k+1,…,n],使array[m,…,k]中任一元素的值不大于array[k+1,…,n]中任一元素的值。
(2) 递归求解:通过递归调用快速排序算法分别对array[m,…,k]和array[k+1,…,n]进行排序。
(3) 合并: 由于对分解出的两个子序列的排序是就地进行的,所以在array[m,…k]和array[k+1,…,n]都是排好序后,不需要执行任何计算,array[m,…,n]就已排好序。
2. Python代码实现
1 | # 如何进行快速排序 |
3 参考资料
- 《Python程序员面试算法宝典》