介绍
快速排序，又称划分交换排序，简称快排，这种排序算法，最早由东尼·霍尔提出。
演示
Sorting_quicksort
复杂度
最坏时间复杂度：O(n^2)
最优时间复杂度：O(nlog n)
平均时间复杂度：O(nlog n)
最坏空间复杂度：根据实现的方式不同而不同
步骤
快速排序使用分治法策略来把一个序列分为两个子序列。
步骤为：
- 从数列中挑出一个元素，称为基准，
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割操作。
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。
python
def quick_sort(li):
if len(li) <= 1:
return li
else:
pivot = li[0]
less = quick_sort([i for i in li[1:] if i < pivot])
more = quick_sort([i for i in li[1:] if i >= pivot])
return less + [pivot] + more
print(quick_sort(li))
java
public static void quickSort(List<Integer> items) {
if(items.size() > 1) {
List<Integer> smaller = new ArrayList<>();
List<Integer> same = new ArrayList<>();
List<Integer> larger = new ArrayList<>();
Integer chosenItem = items.get(items.size() / 2);
for(Integer i: items) {
if(i < chosenItem)
smaller.add(i);
else if(i > chosenItem)
larger.add(i);
else
same.add(i);
}
quickSort(smaller);
quickSort(larger);
items.clear();
items.addAll(smaller);
items.addAll(same);
items.addAll(larger);
}
}
