【数据结构与算法】快速排序(三种代码实现以及工程优化)

概念

快速排序是一种分治的排序算法。它将一个数组分成两个子数组,将两个部分独立地排序。递归调用发生在处理整个数组之后。

快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别,再将其排列成以下形式。
[ 比基准值小的数] 基准值 [ 比基准值大的数]

代码实现

单向扫描分区法

image

  • 第一个元素也就是下标low所指元素作为基准值pivot
  • 左指针i开始指向第二个元素。
  • 右指针j开始指向最后一个元素。
  • 如果i所指向元素小于等于pivot,则i向右移动一位
  • 如果i所指向元素大于pivot,则i不动,i所指向元素与j所指向元素交换,j向左移动一位
  • 最终状态是i和j相邻,并且j位于i的左边,j指向小于等于区域的最后一个元素,i指向大于区域的第一个元素。
  • 把pivot和j所指向元素交换,即可把pivot放到中间位置(每个区域内部不用考虑有序性)。
public static void main(String[] args) {
        int[] arr = {2, 2, 2, 0, 0, 0, 1};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length < 2 || high <= low) return;
        int j = partition(arr, low, high);  //切分
        quickSort(arr, low, j - 1);  //将左半部分arr[low...j-1]排序
        quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
    }

    private static int partition(int[] arr, int low, int high) {
        int i = low + 1, j = high;  //左右扫描指针
        int pivot = arr[low];       //切分元素,设定基准值为从左向右第一个元素的下标
        while (i <= j) {
            if (arr[i] <= pivot)  //扫描元素小于基准值,左指针右移
                i++;
            else {
                swap(arr, i, j);  //扫描元素大于基准值,两个指针的元素交换,右指针左移。使该元素到基准值右侧(确定i所指向元素属于大于区域,那就把它放到大于区域)
                j--;              
            }
        }                   //j最后所指向的位置是小于区域的最后一个元素
        swap(arr, low, j);  //将基准值插入到相应位置,也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
        return j;
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

双向扫描分区法

双向扫描的思路是,头尾指针往中间扫描,从左找到大于主元的元素,从右找到小于等于主元的元素二者交换,继续扫描,直到左侧无大元素,右侧无小元素

  • 第一个元素也就是下标low所指元素作为基准值pivot
  • 左指针i开始指向第二个元素。
  • 右指针j开始指向最后一个元素。
  • 开始外层循环,条件是i<=j
    • 如果i所指向元素小于等于pivot,则i向右移动一位,循环进行,直到i所指向元素大于等于pivot
    • 如果j所指向元素大于pivot,则j向左移动一位,循环进行,直到j所指向元素小于pivot
    • 交换i和j所指向元素
  • 最终状态是i和j相邻,并且j位于i的左边,j指向小于等于区域的最后一个元素,i指向大于区域的第一个元素。
  • 把pivot和j所指向元素交换,即可把pivot放到中间位置(每个区域内部不用考虑有序性)。
public static void main(String[] args) {
        int[] arr = {1,5,6,3,2,1,4,5,2};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    private static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length < 2 || high <= low) return;
        int j = partition(arr, low, high);  //切分
        quickSort(arr, low, j - 1);  //将左半部分arr[low...j-1]排序
        quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
    }
    private static int partition(int[] arr,int low,int high){
        int i = low + 1, j = high;  //左右扫描指针
        int pivot = arr[low];       //切分元素,设定基准值为从左向右第一个元素
        while(i<=j){
            while(i<=j&&arr[i]<=pivot) //扫描元素小于基准值,左指针右移(注意保证i<=j)
                i++;
            while(i<=j&&arr[j]>pivot)  //扫描元素大于基准值,右指针左移(注意保证i<=j)
                j--;
            if(i<j)  //注意该处判断
                swap(arr,i,j);    //左右指针指向元素交换
        }
        swap(arr,low,j);     //将基准值插入到相应位置,也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
        return j;
    }
    private static void swap(int[] arr,int a,int b){
        int tmp = arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;
    }

有相同元素的快速排序——三分法

双向扫描的思路是,多考虑相等的情况,i 指针从左向右扫描,j 指针从右向左扫描,e永远指向相等区域的第一个元素(小于区域的后面第一个元素)。

  • 第一个元素也就是下标low所指元素作为基准值pivot
  • 左指针i开始指向第二个元素。
  • 右指针j开始指向最后一个元素。
  • 中间指针e开始指向第二个元素
  • 开始外层循环,条件是i<=j
    • 如果i所指向元素小于pivot,i所指向元素和e所指向元素交换(e左边是小于区域,把i的元素放到小于区域),i向右移动一位,e向右移动一位。
    • 如果i所指向元素等于pivot,i向右移动一位。(相等于等于区域扩大一位)
    • 如果j所指向元素大于pivot,交换i所指向元素和j所指向元素,j左移一位。(相当于把i的元素放到大于区域)
  • 最终状态是i和j相邻,并且j位于i的左边,j指向等于区域的最后一个元素,i指向大于区域的第一个元素,e指向等于区域的第一个元素(即小于区域的后面第一个元素)。
  • 把pivot和(e-1)所指向元素交换,即可把pivot放到中间位置(每个区域内部不用考虑有序性)。
  • 返回等于区域左边第一个元素下标和等于区域右边最后一个元素下标。

image

public static void main(String[] args) {
        int[] arr = {5,2,1,3,6,7};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    private static void quickSort(int[] arr,int low,int high){
        if(arr==null||arr.length<2||low>=high) return;
        int []j = partition(arr,low,high); //返回两个坐标
        quickSort(arr,low,j[0]-1);  //将左半部分arr[low...j[0]-1]排序
        quickSort(arr,j[1]+1,high); //将右半部分arr[j[0]+1...high]排序
    }
    private static int[] partition(int[] arr,int low,int high){
        int i = low+1;  
        int j = high;
        int pivot = arr[low];
        int e = low+1;
        while(i<=j){
            if(arr[i]<pivot){  //小于pivot,i位置和e位置交换,e++,i++
                swap(arr,i,e);
                e++;
                i++;
            }
            else if(arr[i]==pivot){ //等于pivot,i++
                i++;
            }else{
                swap(arr,i,j);   //大于pivot,s位置和j位置交换,j--
                j--;
            }
        }
        swap(arr,low,e-1);    //将基准值插入到相应位置
        return new int[]{e,j};  //返回等于区域左边第一个元素下标和等于区域右边最后一个元素下标。
    }
    private static void swap(int[] arr,int a,int b){
        int tmp = arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;
    }

工程实践中的其他优化

优化策略

分析一下上面的双向扫描分区法,在定义pivot时都指定第一个元素为pivot的值,有可能pivot的值不在数组中居中,有可能退化成O(n^2)时间复杂度。

举个极端情况的例子:

image

每次选取pivot都为首元素,而pivot的值恰好为最大元素,则pivot最后需要到最右的位置,那么下一次递归调用右半部分arr[j+1…high]就没有了,只有左半部分arr[low…j-1]。而不巧下一次递归pivot选取第一个元素又是最大的,又要重复以上步骤。

数据规模类似从n 到n-1 到n-2 ……到1 ,做n层,最后时间复杂度是O(n^2)级,然而理想的时间复杂度是O(nlogn)级别。

理想情况:

如果每次pivot恰好是中间大小元素,那每次数据规模都变为n/2。写出时间复杂度的递推式:
T(n) = 2T(n/2)+O(n) (O(n)是遍历数组的复杂度,T(n/2)是递归一个分支的复杂度)

利用Master公式:

T(N) = a*T(N/b) + O(N^d)

  • log(b,a) > d -> 复杂度为O(N^log(b,a))
  • log(b,a) = d -> 复杂度为O(N^d * logN)
  • log(b,a) < d -> 复杂度为O(N^d)

其中 a >= 1 and b > 1 是常量,其表示的意义是n表示问题的规模,a表示递归的次数也就是生成的子问题数,b表示每次递归是原来的1/b之一个规模,O(N^d)表示分解和合并等其他操作所要花费的时间复杂度。
使用前提是递归子问题规模相同。

可以得到,a=2,b=2,d=1,log(b,a)=d,复杂度为O(N^d * logN)也就是O(nlogn)

所以我们要做的就是尽力让pivot每次都能选到数组中间大小元素位置。

三点中值法

在low,high,midIndex(low和high的中间元素下标)之间,选一个中间大小值作为主元。

优化一下双向扫描分区法的patition函数:

private static int partition(int[] arr, int low, int high) {
        int i = low + 1, j = high;  //左右扫描指针
        int midIndex = low + ((high - low) >> 2);  //中间下标
        int midValueIndex = -1;  //中值的下标

        if ((arr[low] <= arr[midIndex] && arr[high] >= arr[midIndex]) || (arr[low] >= arr[midIndex] && arr[high] <= arr[midIndex]))
            midValueIndex = midIndex;
        else if ((arr[high] <= arr[low] && arr[midIndex] >= arr[low]) || (arr[high] >= arr[low] && arr[midIndex] <= arr[low]))
            midValueIndex = low;
        else midValueIndex = high;

        swap(arr,low,midValueIndex);  //交换中间大小值和low位的值,让pivot依然位于low的位置,但其值变为中间大小值
        int pivot = arr[low];       //切分元素,设定基准值为从左向右第一个元素
        while (i <= j) {
            while (i <= j && arr[i] <= pivot) //扫描元素小于基准值,左指针右移(注意保证i<=j)
                i++;
            while (i <= j && arr[j] > pivot)  //扫描元素大于基准值,右指针左移(注意保证i<=j)
                j--;
            if (i < j)  //注意该处判断
                swap(arr, i, j);    //左右指针指向元素交换
        }
        swap(arr, low, j);     //将基准值插入到相应位置,也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
        return j;
    }

三点中值法使用比较广。java中使用三点中值法。

绝对中值法

保证pivot是数组的绝对中值
但会使复杂度的的常数因子扩大,有可能得不偿失。

把数组按照每五个元素为一组分组,使用插入排序选出每组中的中值,再把这些中值放到一个数组中使用插入排序选出中值也就是pivot,将其与low的值做交换,保证程序剩下部分正常运行。

private static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length < 2 || high <= low) return;
        int j = partition(arr, low, high);  //切分
        quickSort(arr, low, j - 1);  //将左半部分arr[low...j-1]排序
        quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
}

private static int partition(int[] arr, int low, int high) {
        int i = low + 1, j = high;  //左右扫描指针
        int midValueIndex = getMedian(arr, low, high);
        swap(arr,midValueIndex,low);
        int pivot = arr[low];
        while (i <= j) {
            while (i <= j && arr[i] <= pivot) //扫描元素小于基准值,左指针右移(注意保证i<=j)
                i++;
            while (i <= j && arr[j] > pivot)  //扫描元素大于基准值,右指针左移(注意保证i<=j)
                j--;
            if (i < j)  //注意该处判断
                swap(arr, i, j);    //左右指针指向元素交换
        }
        swap(arr, low, j);     //将基准值插入到相应位置,也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
        return j;
}

private static int getMedian(int[] arr, int p, int r) {  //获取中值方法
        int size = r - p + 1;  //数组长度
        //每五个元素一组
        int groupSize = (size % 5 == 0) ? (size / 5) : (size / 5 + 1);
        //存储各小组中值
        int medians[] = new int[groupSize];
        int indexOfMedians = 0;
        //对每一组进行插入排序
        for (int j = 0; j < groupSize; j++) {
            //单独处理最后一组,因为最后一组可能不满5个元素
            if (j == groupSize - 1) {
                InsertionSort(arr, p + j * 5, r);  //排序最后一组
                medians[indexOfMedians++] = arr[(p + j * 5 + r) / 2];  //最后一组的中间那个
            } else {
                InsertionSort(arr, p + j * 5, p + j * 5 + 4);  //排序非最后一个组的某个组
                medians[indexOfMedians++] = arr[p + j * 5 + 2];  //当前组(排序后)的中间那个
            }
        }
        InsertionSort(medians, 0, medians.length - 1);
        return medians[medians.length / 2];
}
private static void InsertionSort(int[] arr,int begin,int end){  //插入排序
        if(arr==null||arr.length<2) return;     //去除无效情况
        for(int i = begin+1; i < end; i++){
            for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--)
                swap(arr,j,j+1);
        }
}
private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
}

用的较少,看需求。

待排序列表较短时,使用插入排序

插入排序的真实复杂度是n(n-1)/2,快速排序的真实复杂度是n(logn+1)
估计一下:

  • n<8 时用插入排序更快
  • n>8 时用快排更快
  public static void quickSort(int[] A, int p, int r) {
    if (p < r) {
      //待排序个数小于等于8的时候,插入排序
      if (p - r + 1 <= 8) {
        InsertionSort(A, p, r);   //插入排序
      } else {                    //快排
        int q = partition2(A, p, r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
      }
    }
  }