算法描述

快速排序，是我们之前学习的冒泡排序的升级，他们都属于交换类排序，都是采用不断的比较和移动来实现排序的。
快速排序是一种非常高效的排序算法，它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动次数。
同时采用“分而治之”的思想，把大的拆分为小的，小的拆分为更小的，其原理如下：对于给定的一组记录，选择一个基准元素，通常选择第一个元素或者最后一个元素，通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素，此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分，直到序列中的所有记录均有序为止。

动图展示

交换排序_快速排序 - 图1

代码实现

以数组 {49,38,65,97,76,13,27,49} 为例，选择第一个元素49为基准，存入temp变量中，从数组的左右两边界向中间进行遍历，定义两个指针 i 和 j，i 最开始指向数组的第一个元素，j 最开始指向数组的最后一个元素。指针 i 从左向右移动，指针 j 从右向左移动。先移动 j 指针（从右忘左移），当 j 指向的数大于基准数时，略过，j 继续往左移动，直到遇到小于等于基准数的数arr[j]，将arr[j]填入arr[i]中；再移动 i 指针，当 i 指向的数小于等于基准数时，略过，i 继续往右移动，直到遇到不比基准数小的数arr[i]，将arr[i]填入arr[j]中；再移动 i 指针，再移动 j 指针…(轮换移动)，直到 i 和 j 指针相遇，此时将temp（基准数）填入arr[i]中即完成算法的第2个步骤。接下来分别将基准数左边和右边的数组按照以上方法进行聚合，直到每个子集只有一个元素，即排序完成。

初始化关键字： [49,38,65,97,76,13,27,49]
交换排序_快速排序 - 图2

  1. public class 快速排序 {
  2.     public static void main(String[] args) {
  3.         int[] ints = {49, 38, 65, 97, 76, 13, 27, 49};
  4.         int[] quickSort = quickSort(ints);
  5.         System.out.println(Arrays.toString(quickSort));
  6.     }
  8.     public static int[] quickSort(int[] ints) {
  9.         return sort(ints, 0, ints.length - 1);
  10.     }
  12.     public static int[] sort(int[] ints, int start, int end) {
  13.         int i, j, index;
  14.         // 数组非空判断
  15.         if (start > end) return null;
  17.         i = start;
  18.         j = end;
  19.         // 以第一位数为基准
  20.         index = ints[i];
  21.         while (i < j) {
  22.             // 从右往左比，如果右边的数大，则回退一位
  23.             while (i < j && ints[j] >= index) j--;
  24.             // 如果右边出现比基准小的数，进行换位
  25.             if (ints[j] < index) ints[i++] = ints[j];// ints[0] = 27,i = 1
  26.             // 从左往比右，如果左边的数小，则进一位
  27.             while (i < j && ints[i] <= index) i++;
  28.             // 如果左边出现比基准大的数，进行换位
  29.             if (ints[i] > index) ints[j--] = ints[i];
  30.         }
  31.         // 将基准数值替换回 a[i]，
  32.         // 此时的index在不一定在数组的最中间，
  33.         // 但是它将数组分为两块
  34.         // 它比低子表的数都大，比高子表的数都小
  35.         ints[i] = index;
  36.         // 对低子表进行递归排序，同理
  37.         sort(ints, start, i - 1);
  38.         // 对高子表进行递归排序，同理
  39.         sort(ints, i+1, end);
  40.         return ints;
  41.     }
  42. }

算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

参考：https://blog.csdn.net/weixin_37817685/article/details/79969349