介绍

快速排序，又称划分交换排序，简称快排，这种排序算法，最早由东尼·霍尔提出。

演示

Sorting_quicksort

复杂度

最坏时间复杂度：O(n^2)
最优时间复杂度：O(nlog n)
平均时间复杂度：O(nlog n)
最坏空间复杂度：根据实现的方式不同而不同

步骤

快速排序使用分治法策略来把一个序列分为两个子序列。
步骤为：

1. 从数列中挑出一个元素，称为基准，
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割操作。
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

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);
        }
    }