快速排序及代码实现

代码

分析

它是 不稳定的 排序。 快速排序的时间主要耗费在划分（partition）上。 最坏情况也就是划分次数最多的情况，即每次划分基准元素都是当前无序区间中最大（或最小）的那个。此时退化为冒泡排序，复杂度为O(n^2) 最好情况下划分次数最少，每次划分后基准元素都在最中间。