深入学习高级排序算法：Java实现快速排序的详细教程与代码分享

前言

今天持续进行算法学习，这次学习的是高级排序当中的快速排序。本文的代码部分有调用公共方法，能够在文章“简单排序算法之冒泡、插入和选择排序 - Java 实现版”以及“高级排序之归并排序、希尔排序”中去查找相关的方法。此外，本文还给出了测试时所使用的完整代码，要是对其他算法不感兴趣的话，可以在文章的末尾找到完整的源代码。

快速排序

快速排序的本质在于将一个数组划分成两个子数组，接着递归地调用自身，为每一个子数组进行“快速排序”以达成目的。这里存在一个问题，那就是怎样进行划分？

在快速排序里，为了对数组进行划分，提出了“枢纽”这一说法，它所指代的是待排序序列中的一个数据项。快速排序通过枢纽把数组分成两部分。一部分在枢纽左侧，这里面都是小于该枢纽所表示的数据项。另一部分在枢纽右侧，这些都大于该枢纽所表示的数据项。需注意，此时左右两侧的数据项是无序的。枢纽被放置在左右两侧的中间位置，这样该枢纽就已经处于排序的正确位置了。枢纽是快速排序要排序的对象，而实现“排序”的关键就在于调整枢纽的位置。通过这样的递归划分，最终会出现左侧只有一个数据项的情况，这个数据项既是左侧子数组又是枢纽，此时左侧递归结束，开始划分右侧数组……以此类推。这里产生了另一个问题，那就是如何选择枢纽呢？

也可以选择最左侧的数据项作为枢纽。

上图演示了以子数组最右侧数据项做枢纽的排序过程

代码演示（枢纽始终使用子数组的最右侧数据项）

在给定的范围内，将数组进行分区操作。指定左侧边界为 left，右侧边界为 right，枢轴值为 pivot，针对给定的数组 array 进行分区。具体来说，就是将数组中小于等于枢轴值的元素移到左侧，大于枢轴值的元素移到右侧，然后返回枢轴值最终所在的位置。
    int leftPtr = left-1;
    int rightPtr = right;
    while(true){
      // 查找左侧子数组大于枢纽的位置
当比较（数组[++leftPtr]，枢轴）时<0){
      }
      // 查询右侧子数组小于枢纽的位置
      while(rightPtr>如果比较数组中右指针所指元素与枢轴元素，即比较 array[--rightPtr] 和 pivot，且结果大于 0 ，那么
      }
      if(leftPtr>=rightPtr){
        break;
      }
      // 交换需要调整位置的两个数据项
      swap(leftPtr,rightPtr,array);
    }
    // 将枢纽挪到两侧中间
    swap(leftPtr,right,array);
    return leftPtr;
  }
    返回 i，即分区点的索引。
    if(right-left<=0){
      return;
    }
    // 选择的枢纽
    int pivot = array[right];
    int partition = partitionIt(left,right,pivot,array);
    recQuickSort(left,partition-1,array);
    recQuickSort(partition+1,right,array);
  }
  public static void quickSort(int[] array){
    compareCount=0;
    swapCount=0;
创建了一个名为 start 的 long 类型变量，通过 new Date().getTime() 获取当前时间的时间戳并赋值给 start
    recQuickSort(0,array.length-1,array);
创建了一个名为 long end 的变量，该变量被赋值为当前时间的时间戳，即 new Date().getTime() 的返回值。
    printResult("快速排序","交换次数",start,end);
  }

运行结果

冒泡排序的比较次数为 49995000，交换次数为 25153125，耗时 173 毫秒。

选择排序的比较次数为 49995000，交换次数为 9987，耗时 65 毫秒。

插入排序的比较次数为 25075792，复制次数为 25075793，耗时 42 毫秒。

归并排序的比较次数为 120459，复制次数为 267232，耗时 3 毫秒。

希尔排序的比较次数为 233896，复制次数为 238266，耗时 5 毫秒。

对随机序列进行排序，其中快速排序的比较次数为 165181 次，交换次数为 31700 次，耗时 3 毫秒。

对逆序序列进行排序：快速排序的比较次数为 49825881，交换次数为 9976，耗时 54 毫秒

从运行结果来看，对于随机序列，快速排序算法的执行速度很快，与归并排序的速度相同。然而，在给逆序序列排序时，其效果却非常差，几乎和选择排序的效率一样。这是为什么呢？

根本原因在于枢纽的选择。快速排序期望枢纽能够把数组拆分成两个子数组，且这两个子数组的长度几乎相同。这样做能最优地平衡比较次数和交换次数。对于随机序列，简单地选择最右侧的数据项作为枢纽，这样就不会频繁出现左右子数组极度不平衡的情况。而对于逆序序列，几乎每次划分都会形成极度不平衡的两个子数组，最终使得较大侧的子数组需要被划分更多次。

优化枢纽选择算法

快速排序的最优划分结果是两个数组长度相等。为实现此目的，每次划分前需先找到子数组的中间数据项吗？显然不行，因为找中值的时间可能远大于排序时间。所以，我们只能选择一个既不过于复杂，又比“选择最右侧数据项作为枢纽”的算法更具普适性的方法。

上图所示的取枢纽的方法叫做“三数据项取中”。这种方法是从数组中选取第一个、最后一个以及中间的数据项，然后从这三个数据项中取出大小处于中间的项作为枢纽。在选择过程中，实际上我们对这三个数据项进行了排序，并且顺便将分别大于、小于枢纽的那两个数据项放置到正确的位置，也就是左侧小于枢纽，右侧大于枢纽。

该方法划分时需至少有三个数据项，若子数组项数不大于 3 个，就可结束递归划分。此时排序可通过其他排序算法实现，比如手动排序（待排序数据项不大于 3 个，手动排序能轻松搞定），也可用插入排序（若用插入排序，数据项不大于 10 时（此 10 无具体意义，可为 20、30 等）可用于收尾）。我们下面用该方法来选择枢纽，并且用插入排序来收尾，同时对代码进行修改。

代码演示

定义一个静态方法 medianOf3，该方法接收三个参数，分别是 left、right 和一个整数数组 array。此方法用于找出给定数组中指定范围内的三个元素的中位数。
    int center = (left+right)/2;
如果数组中的元素 array[left] 大于元素 array[center]，那么就执行以下操作：
      swap(left,center,array);
    }
    if(array[left]>array[right]){
      swap(left,right,array);
    }
如果数组中的中心元素大于右侧元素，那么就执行以下操作；如果数组中的中心元素不大于右侧元素，那么就执行其他操作。
      swap(center,right,array);
    }
    swap(center,right-1,array);
    return array[right-1];
  }
静态私有方法 insertSort 接受两个整数 left 和 right 以及一个整数数组 array 作为参数。它用于对数组 array 中从索引 left 到索引 right 的部分进行插入排序操作。在这个方法内部，会通过特定的算法逻辑来实现插入排序的过程，以将数组这一部分的元素按照升序排列。
    for (int i = left+1; i <= right; i++) {
      int temp = array[i];
      int cur = i;
      // 右移数字，实现cur下标的左侧都是有序的
      while (cur >将 temp 与 array[cur - 1]进行比较，比较结果为 0 。< 0) {
        copy(cur-1,cur,array);
        cur--;
      }
      // 如果cur==i则说明数据项已经在正确的位置了，不需要进行交换
      if (cur != i) {
        // 不满足temp0){
      }
      if(leftPtr>=rightPtr){
        break;
      }
      // 交换需要调整位置的两个数据项
      swap(leftPtr,rightPtr,array);
    }
    // 将枢纽挪到两侧中间
    swap(leftPtr,right-1,array);
    return leftPtr;
  }
  private static void recQuickSort(int left,int right,int[] array){
    int size = right-left+1;
    if(size <10){
      insertSort(left,right,array);
    }else{
      int median = medianOf3(left,right,array);
      int partition = partitionIt(left,right,median,array);
      recQuickSort(left,partition-1,array);
      recQuickSort(partition+1,right,array);
    }
  }
  public static void quickSort(int[] array){
    compareCount=0;
    swapCount=0;
    long start = new Date().getTime();
    recQuickSort(0,array.length-1,array);
    long end = new Date().getTime();
    printResult("快速排序","交换次数",start,end);
  }

运行结果

冒泡排序，其比较次数为 49995000，交换次数为 25138570，耗时 170 毫秒。

选择排序的比较次数为 49995000，交换次数为 9990，耗时 65 毫秒。

插入排序的比较次数为 25069178，复制次数为 25069176，耗时 34 毫秒。

归并排序的比较次数为 120483，复制次数为 267232，耗时 2 毫秒。

希尔排序的比较次数为 231598，复制次数为 235991，耗时 6 毫秒。

对随机序列进行排序，其中快速排序的比较次数为 154857，交换次数为 44570，耗时 3 毫秒。

对逆序序列进行排序，其中快速排序的比较次数为 188034 次，交换次数为 20067 次，耗时 1 毫秒。

从执行结果来看，枢纽选择算法经过优化后，在随机序列排序方面，排序速度很快；在逆序序列排序方面，排序速度也很快。

至此，本文结束

完整代码

package team.ngup.study;
import java.util.Arrays;
import java.util.Date;
导入用于并发操作的 ThreadLocalRandom 类。
/**
 * @author zww
 * @date 2022/8/4 10:35
 */
public class SortStudy {
静态的最终的整数 ARRAY_SIZE 的值为 10000。
  static int compareCount = 0;
  static int swapCount = 0;
  /**
   * 生成随机数数组
   *
   * @return
   */
创建一个方法用于构建随机数组。该方法返回一个整数类型的数组。在方法内部，通过随机数生成器来生成随机数组的元素。数组的长度可以根据需求进行设定。最后返回生成的随机数组。
定义了一个整数数组，数组名为 array，数组的大小为 ARRAY_SIZE，通过 new int[ARRAY_SIZE]的方式创建了这个数组。
    for (int i = 0; i < ARRAY_SIZE; i++) {
      int randomWithThreadLocalRandom = ThreadLocalRandom.current().nextInt(0, 1000000);
      array[i] = randomWithThreadLocalRandom;
    }
    return array;
  }
  /**
   * a和b位置的数据交换
   *
   * @param a
   * @param b
   * @param array
   */
  public static void swap(int a, int b, int[] array) {
    swapCount++;
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
  }
  /**
   * 复制 位置 a->b
   * @param a
   * @param b
   * @param array
   */
将整数 a 、整数 b 以及整数数组 array 进行复制操作 。
    swapCount++;
    array[b] = array[a];
  }
  /**
   * 复制 数值a->位置b
   * @param a
   * @param b
   * @param array
   */
它接收三个参数，一个整数 a，一个整数 b 以及一个整数数组 array。
    swapCount++;
    array[b]=a;
  }
  /**
   * dataa大于datab返回1，否则返回-1
   *
   * @param dataa
   * @param datab
   * @return
   */
如果 dataa 等于 datab，则返回 0。
    compareCount++;
    if (dataa >= datab) {
      return 1;
    }
    return -1;
  }
  /**
   * 输出排序结果
   *
   * @param name 排序方法名
   * @param operName 交换/复制
   * @param start 开始时间
   * @param end 结束时间
   */
静态私有方法 printResult 接收两个字符串参数 name 和 operName，以及两个长整型参数 start 和 end 。
    System.out.print(
        name
            + "——比较次数:"
            + compareCount
            + ","+operName+":"
            + swapCount
            + ",耗时:"
            + (end - start)
            + "毫秒");
  }
  /** 冒泡排序 */
    compareCount = 0;
    swapCount = 0;
    // 待排序序列长度，
    int length = array.length;
    long start = new Date().getTime();
    while (length > 0) {
      for (int a = 0; a < length - 1; a++) {
        if (compare(array[a], array[a + 1]) > 0) {
          // 交换位置
          swap(a, a + 1, array);
        }
      }
从头到尾进行一次遍历，找出了最右端的值也就是最大值，这样就能缩短第二次遍历的序列长度。
      length--;
    }
    long end = new Date().getTime();
    // 输出排序结果
打印结果("冒泡排序","交换次数",开始,结束)；
  }
  /** 选择排序 */
公共静态 void 从数组中进行选择(int[] 数组)；
    compareCount = 0;
    swapCount = 0;
    int length = 0;
    long start = new Date().getTime();
若长度不等于数组长度减 1 ，就 ；
      // 最小值位置
      int minPosition = -1;
      // 最小值
      int min = array[length];
      for (int i = length + 1; i < array.length; i++) {
        if (compare(array[i], min) < 0) {
          min = array[i];
          minPosition = i;
        }
      }
      // 存在比当前值还要小的值，则进行位置对换，否则无需对调位置
      if (minPosition != -1) {
        // 交换位置
        swap(length, minPosition, array);
      }
      length++;
    }
    long end = new Date().getTime();
    printResult("选择排序","交换次数", start, end);
  }
  /** 插入排序 */
  public static void charu(int[] array) {
    swapCount = 0;
    compareCount = 0;
    // 第一次排序无需比较，所以直接从1开始
    long start = new Date().getTime();
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      int cur = i;
      // 右移数字，实现cur下标的左侧都是有序的
      while (cur > 0 && compare(temp, array[cur - 1]) < 0) {
        copy(cur-1,cur,array);
        cur--;
      }
      // 如果cur==i则说明数据项已经在正确的位置了，不需要进行交换
      if (cur != i) {
        // 不满足temp0){
      for(outer=h;outer如果 h-1 并且比较(array[inner-h],temp)大于 0 ，那么
          copy(inner-h,inner,array);
          inner -= h;
        }
        copyData(temp,inner,array);
      }
      h=(h-1)/3;
    }
    long end = new Date().getTime();
打印结果为“希尔排序”，涉及“复制次数”，起始值为 start，结束值为 end。
  }
快速排序是一种排序算法。它通过选择一个基准元素，将数组分为两部分，一部分元素小于等于基准元素，另一部分元素大于基准元素。然后对这两部分分别进行排序，最终将整个数组排序。这种排序算法的时间复杂度为 O(nlogn)，在实际应用中效率较高。
  private static int medianOf3(int left,int right,int[] array){
    int center = (left+right)/2;
如果比较(array[left],array[center])的结果大于 0 ，那么
      swap(left,center,array);
    }
如果比较(array[left],array[right])的结果大于 0 ，则
      swap(left,right,array);
    }
如果比较(array[center]和 array[right])的结果大于 0 ，那么
      swap(center,right,array);
    }
    swap(center,right-1,array);
    return array[right-1];
  }
  private static void insertSort(int left,int right,int[] array){
    for (int i = left+1; i <= right; i++) {
      int temp = array[i];
      int cur = i;
      // 右移数字，实现cur下标的左侧都是有序的
      while (cur > 0 && compare(temp, array[cur - 1]) < 0) {
        copy(cur-1,cur,array);
        cur--;
      }
      // 如果cur==i则说明数据项已经在正确的位置了，不需要进行交换
      if (cur != i) {
        // 不满足temp0){
      }
      if(leftPtr>=rightPtr){
        break;
      }
      // 交换需要调整位置的两个数据项
      swap(leftPtr,rightPtr,array);
    }
    // 将枢纽挪到两侧中间
    swap(leftPtr,right-1,array);
    return leftPtr;
  }
  private static void recQuickSort(int left,int right,int[] array){
    int size = right-left+1;
    if(size <10){
      insertSort(left,right,array);
    }else{
      int median = medianOf3(left,right,array);
      int partition = partitionIt(left,right,median,array);
      recQuickSort(left,partition-1,array);
      recQuickSort(partition+1,right,array);
    }
  }
  public static void quickSort(int[] array){
    compareCount=0;
    swapCount=0;
    long start = new Date().getTime();
    recQuickSort(0,array.length-1,array);
    long end = new Date().getTime();
    printResult("快速排序","交换次数",start,end);
  }
  public static void main(String[] args) {
    int[] array = buildRandomArray();
    int[] array2 = Arrays.copyOf(array, ARRAY_SIZE);
    int[] array3 = Arrays.copyOf(array, ARRAY_SIZE);
    int[] array4 = Arrays.copyOf(array,ARRAY_SIZE);
    int[] array5 = Arrays.copyOf(array,ARRAY_SIZE);
    int[] array6 = Arrays.copyOf(array,ARRAY_SIZE);
    maopao(array);
    System.out.println();
    xuanze(array2);
    System.out.println();
    charu(array3);
    System.out.println();
    mergeSort(array4);
    System.out.println();
    xierSort(array5);
    System.out.println();
    // 随机数据项 进行快速排序
    System.out.print("对随机序列排序：");
    quickSort(array6);
    System.out.println();
    // 将array6逆序
    int[] array6a = new int[array6.length];
    for(int i=array6.length-1,j=0;i>=0;i--){
      array6a[j] = array6[i];
      j++;
    }
    // 对逆序的数组使用快速排序
    System.out.print("对逆序序列排序：");
    quickSort(array6a);
  }
}

高级排序算法中的快速排序|NGUP的个人技术博客