快速排序--挖坑法详解

68 阅读 0 评论 45 点赞

我是靠谱客的博主幽默保温杯，最近开发中收集的这篇文章主要介绍快速排序--挖坑法详解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一，思想描述：

何谓挖坑法？我们来看一看详细过程。

给定原始数列如下，要求从小到大排序：

首先，我们选定基准元素Pivot，并记住这个位置index，这个位置相当于一个“坑”。并且设置两个指针left和right，指向数列的最左和最右两个元素：

接下来，从right指针开始，把指针所指向的元素和基准元素做比较。如果比pivot大，则right指针向左移动；如果比pivot小，则把right所指向的元素填入坑中。

在当前数列中，1<4，所以把1填入基准元素所在位置，也就是坑的位置。这时候，元素1本来所在的位置成为了新的坑。同时，left向右移动一位。

此时，left左边绿色的区域代表着小于基准元素的区域。

接下来，我们切换到left指针进行比较。如果left指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把left指向的元素填入坑中。

在当前数列中，7>4，所以把7填入index的位置。这时候元素7本来的位置成为了新的坑。同时，right向左移动一位。

此时，right右边橙色的区域代表着大于基准元素的区域。

下面按照刚才的思路继续排序：

8>4，元素位置不变，right左移

2<4，用2来填坑，left右移，切换到left。

6>4，用6来填坑，right左移，切换到right。

3<4，用3来填坑，left右移，切换到left。

5>4，用5来填坑，right右移。这时候left和right重合在了同一位置。

这时候，把之前的pivot元素，也就是4放到index的位置。此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。

二，代码演示--以首位元素为基准值：

package zyh.example.demo.algorithm.kuaisupaixu;
 
import java.util.Arrays;
 
/**
* @ClassName KuaiPai13
* @Author zhangyonghui
* @Description
* @Date 2022/3/29 11:26
* @Version 1.0
**/
public class KuaiPai13 {
 
  public static void main(String[] args) {
		int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
		quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
  }
 
  /**
   * 快速排序--挖坑法
   * @param arr 数组
   * @param startIndex 左边界索引
   * @param endIndex 右边界索引
   */
  public static void quickSort(int[] arr, int startIndex, int endIndex) {
		// 递归结束条件：startIndex大等于endIndex的时候
		if (startIndex >= endIndex) {
			  return;
		}
		// 得到基准元素位置
		int pivotIndex = partition(arr, startIndex, endIndex);
		// 用分治法递归数列的两部分
		quickSort(arr, startIndex, pivotIndex - 1);
		quickSort(arr, pivotIndex + 1, endIndex);
  }
 
  /**
   * 具体每一轮的快速排序：
   * @param arr 数组
   * @param startIndex 左边界索引
   * @param endIndex 右边界索引
   * @return 返回基准值的位置，此时基准值左边的元素都小于基准值，基准值右边的元素都大于基准值
   */
  private static int partition(int[] arr, int startIndex, int endIndex) {
		// 取第一个位置的元素作为基准元素
		int pivot = arr[startIndex];
		// 初始化坑的位置，初始等于pivot基准值的位置
		int kengIndex = startIndex;
		//初始化左右游标/指针
		int leftYb = startIndex;
		int rightYb = endIndex;
		//大循环在左右指针重合时结束
		while ( leftYb<rightYb ) {
			  //right指针从右向左进行比较
			  // leftYb<rightYb ，左游标永远小于右游标，是遍历元素并发生元素变动的前提：
			  while ( leftYb<rightYb) {
					// 先遍历右边，
					//  如果元素大于基准值--右游标左移：
					if (arr[rightYb] >= pivot) {
						  rightYb--;
					}else{ //如果右边的当前元素小于基准值了，那么将该元素填入坑中，该元素本来的位置成为新的坑；
						  arr[kengIndex] = arr[rightYb];
						  kengIndex = rightYb;
						  leftYb++;
						  break;
					}
			  }
			  //再遍历左边，
			  // leftYb<rightYb ，左游标永远小于右游标，是遍历元素并发生元素变动的前提：
			  while (leftYb<rightYb) {
					//如果元素小于基准值--左游标右移，
					if (arr[leftYb] <= pivot) {
						  leftYb++;
					}else{  //如果左边的当前元素大于基准值了，那么将该元素填入坑中，该元素本来的位置成为新的坑；
						  arr[kengIndex] = arr[leftYb];
						  kengIndex = leftYb;
						  rightYb--;
						  break;
					}
			  }
		}
		//跳出了大循环，说明此时此刻左右游标是重合的，这时将基准值放在重合位置(最后一个坑)，
		// 此时，基准值左边的元素都小于基准值，基准值右边的元素都大于基准值，这一轮交换宣告结束；
		arr[kengIndex] = pivot;
		return kengIndex;
  }
 
  
}

三，随机选取基准值--代码演示：

对于快速排序来说，最简单的方式是选择数列的第一个元素，这种选择在绝大多数情况是没有问题的。

但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？

当数据有序逆序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差，如果每一轮快排都是如此，那么时间复杂度为n^2。

随机选择基准 可以降低逆序带来的O(n^2)复杂度的可能性。

基准选择的三种方式：

固定基准 （比如第一个），当原始序列或子序列逆序时，复杂度接近O(n^2)，所以应该避免使用这种方式。
随机选择 ，降低了逆序复杂度变高的可能性，但仍然不容乐观。
三数取中，随机选择三个数，取中间大小的作为基准，当然，本身三个数都是不确定的，随机选择无意义，直接取原始数列的头、中、尾三个元素，得出中间大小作为基准即可。进一步降低了数列逆序的可能性。

可以看到，即使是性能最差的 固定基准 ，也不一定是 选择第一个元素作为基准 ，所以，我们应该掌握的快排，是不以第一个元素为基准的快速排序。

既然，以 第一个元素为基准的快速排序 ，理解和代码实现都是最简单的，那么我们为什么不这样写呢？

无论你使用了哪种 基准选择 的方式，在 元素移动 之前，你都可以让你的基准先与 第一个元素 进行交换，这样是不是就变成了你手到擒来的快速排序？

所以你需要记住快速排序的总过程是：

选择基准
与第一元素交换
元素移动

通过代码分析，我们得出结论，当 随机选择基准 时，无论

挖坑法，增加判断条件
指针交换法，影响指针优先移动顺序

都会增加代码复杂度，甚至，循环判断降低了代码性能。不妨，将复杂问题简单化，统一快速排序的过程

选择基准
与第一元素交换
元素移动

      /**
       * 快速排序--挖坑法：
       *           1，任意选择一个数作为基准值，
       *           2，将基准值与首位元素进行交换，
       *           3，基准值所在的位置成为原始坑kengIndex；
       *           4，先遍历右边，如果元素大于基准值--右游标左移，如果元素小于基准值--将该元素填入坑中，该元素本来的位置成为新的坑；
       *           5，再遍历左边，如果元素小于基准值--左游标右移，如果元素大于基准值--将该元素填入坑中，该元素本来的位置成为新的坑；
       *           6，直到左右游标重合，这时将基准值放在重合位置(最后一个坑)，此时，基准值左边的元素都小于基准值，基准值右边的元素都大于基准值，这一轮交换宣告结束；
       *           7，递归调用该方法；
       * @param arr
       * @param leftIndex
       * @param rightIndex
       */
      public static void quicksort2(int[] arr, int leftIndex, int rightIndex) {
            //初始化左右游标：
            int leftYb = leftIndex;
            int rightYb = rightIndex;
            //随机选择一个数作为基准值：
            //一般简单的来说都选择第一个数即可，但是存在逆序情况导致效率极低的风险；
            // 随机选择的元素的位置：
            int suijiIndex = (leftIndex + rightIndex) / 2; //基准值所在位置为原始坑位；

            //我们将基准值和首位元素交换位置：
            int temp = arr[suijiIndex];
            arr[suijiIndex] = arr[leftIndex];
            arr[leftIndex] = temp;

            //基准值和首位元素交换位置之后，坑位位置为首位，基准值在首位；
            int kengIndex = leftIndex;
            int pivotVal = arr[kengIndex]; //基准值

            //左游标永远小于右游标，是遍历元素并发生元素变动的前提：
            while (leftYb < rightYb) {
                  //先遍历右边，
                  //如果元素大于基准值--右游标左移：
                  while (leftYb < rightYb && arr[rightYb] >= pivotVal) {
                        rightYb--;
                  }
                  //跳出了循环，说明此时的右游标所在元素小于基准值，那么将该元素填入坑中，该元素本来的位置成为新的坑；
                  arr[kengIndex] = arr[rightYb];
                  kengIndex = rightYb;

                  //再遍历左边，
                  //如果元素小于基准值--左游标右移，
                  while (leftYb < rightYb && arr[leftYb] <= pivotVal) {
                        leftYb++;
                  }
                  //跳出了循环，说明此时的左游标所在元素大于基准值，那么将该元素填入坑中，该元素本来的位置成为新的坑；
                  arr[kengIndex] = arr[leftYb];
                  kengIndex = leftYb;
            }
            //跳出了大循环，说明此时此刻左右游标是重合的，这时将基准值放在重合位置(最后一个坑)，此时，基准值左边的元素都小于基准值，基准值右边的元素都大于基准值，这一轮交换宣告结束；
            arr[kengIndex] = pivotVal;

            //递归调用：
            if (leftYb - 1 > leftIndex) {
                  quicksort2(arr, leftIndex, kengIndex - 1);
            }
            if (rightIndex > rightYb + 1) {
                  quicksort2(arr, kengIndex + 1, rightIndex);
            }

      }