快速排序 §

快速排序使用分治思想。每次选取一个数据做为分区点 p，将小于 p 的数据放在 p 左边，大于 p 的数据放在 p 右边。然后对 p 左边和右边两个区块分别重复上述操作，直至整个数组有序。

快速排序是非稳定的排序算法。

代码实现 §

这个版本代码的分区点采用了随机选取的方式，可以避免在数据排列极端的情况下，算法的性能下降。

private static final Random RANDOM = new Random();  
  
public void quicksort(int[] nums, int left, int right) {  
    int pindex = partition(nums, left, right);  
    if (left < pindex - 1) {  
        quicksort(nums, left, pindex - 1);  
    }  
    if (right > pindex + 1) {  
        quicksort(nums, pindex + 1, right);  
    }  
}  
  
private int partition(int[] nums, int left, int right) {  
    int randomIndex = RANDOM.nextInt(right - left + 1) + left;  
    swap(nums, left, randomIndex);  
    int lt = left;  
    for (int i = left + 1; i <= right; ++i) {  
        if (nums[i] < nums[left]) {   
            swap(nums, i, ++lt);  
        }  
    } 
    swap(nums, left, lt);  
    return lt;  
}  
  
private void swap(int[] nums, int index1, int index2) {  
    int tmp = nums[index1];  
    nums[index1] = nums[index2];  
    nums[index2] = tmp;  
}

时空复杂度 §

• 时间复杂度：分治次数在大多数情况下为log(n)，每次排序时间复杂度为O(n)，总时间复杂度为O(nlogn)。当极端情况下（数据近乎完全有序），分治次数为n次，算法退化为O(n^2)。为避免快速排序的最差情况，可以在每次 partition() 执行前进行一次shuffle()，将数组打乱；或者向上面代码那样，随机选取分割点。
• 空间复杂度：O(1)

与归并排序的比较 §

见 与 快速排序 比较

利用快速排序求第k大元素 §

求数组第K大元素这一经典题目可以使用堆排序和快速排序两种方法。如使用快速排序，通过确定所求数在分区点的左侧还是右侧，可以减少一半的排序操作，时间复杂度为O(n)。