快速排序

快排核心操作

传统快排核心操作partition会基于一个枢轴元素pivot将数组划分为三部分：<= pivot、= pivot和>= pivot。每一次partition都会确定一个数组元素的最终位置。

• partition解法1
  假设以最后一个元素为枢轴pivot，
  定义两个变量i和j，i先找到下一个比pivot大的元素，j再找到下一个比pivot小的元素，然后交换两个位置的值，然后i和j一直遍历下去，直到i == j。
  

注意：这里i先找，到i == j时，i正好是>= pivot部分的第一个元素

public class QuickSort {
    private static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    private static int partition(int[] arr, int begin, int end){
        int i = begin, j = end;
        int pivot = arr[end];
        while(i != j){
            while(arr[i] <= pivot && i < j){
                i++;
            }
            while(arr[j] >= pivot && i < j){
                j--;
            }
            //交换位置
            if(i < j){
                swap(arr, i, j);
            }
        }
        //将枢轴元素放置到最终的排序位置
        swap(arr, i, end);
        return i;
    }
    private static void quickSort(int[] arr, int begin, int end){
        if(begin < end){
            int i = partition(arr, begin, end);
            quickSort(arr, begin, i - 1);
            quickSort(arr, i + 1, end);
        }
    }
    private static void quickSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
}

• partition解法2
  定义两个变量L和R，分别表示<= pivot部分的最后一个元素和>= pivot部分的第一个元素。cur遍历数组
  
  cur遇到的元素有两种情况：
  • arr[cur] <= pivot，L向右扩，cur++
  • arr[cur] > pivot，交换cur和R前一个位置的元素，R向左扩，cur不变
    
    最后cur == R结束遍历，将枢轴位置的元素和R位置的元素交换以确定枢轴元素的最终位置。

    private static int partition(int[] arr, int begin, int end){
        int L = begin - 1, R = end;
        int cur = begin;
        int pivot = arr[end];
        while(cur != R){
            if(arr[cur] <= pivot){
                L++;
                cur++;
            }else{
                swap(arr, cur, --R);
            }
        }
        //将枢轴元素放置到最终的排序位置
        swap(arr, R, end);
        return R;
    }

分析

排序算法	时间复杂度 (平均)	时间复杂度 (最坏)	时间复杂度 (最好)	空间复杂度	稳定性
快速排序					不稳定

• 决定快排时间复杂度的一个重要环节是枢轴元素的选择，枢轴元素的最终位置如果位于数组的中心位置，是最好的；如果枢轴元素的最终位置落到边缘上，那么就会退化为O(n^2)。有个优化策略就是随机选枢轴元素。
• bfprt算法就是在枢轴元素的选择上做优化，保证枢轴元素的最终位置会落在数组中心附近。