简介

快速排序算法首先会在序列中随机选择一个**基准值（pivot），然后将除了这个基准值以外的元素分为两组：“比基准值小的元素”和“比基准值大的元素”**这两个类别，然后再将其排列成有序的元素。

• 特征
  • 首先随机挑选一个基准值，通过该基准值将数组分成左右两部分。
  • 将小的元素都放到基准值的左边，大的元素都放在右边。
  • 对于小于和大于基准值的两组元素，还可以各自取一个基准值，同理也是将最小元素放到基准值的最左边。最大元素放到基准值的最右边。依次循环。

图解

给出下面一组数字：[ 3, 5, 8, 1, 2, 9, 4, 7, 6 ]

下面第一个步骤就是在这些数字中选择一个基准值

在列表中随机选择了而4作为基准值。

• 然后将其它数字与这个基准值进行比较，比它小的放在左边，大的放在右边。

  首先3和4基准值进行比较

由于3 < 4 所以将3往左边移动

接下来再由5 和 基准值4比较。

5 > 4基准值，所以往右边移动

然后再由8和4基准值进行比较。

8 依然 > 4号基准值，所以往右边移动，如下图
:::tips 对于1，2，9, 7，6数字也进行以上同样的操作。最终结果如下图所示。 :::

以上已经根据4号基准值将元素分为了两个部分，一部分是比基准值小的元素**，一部分是比它大的元素值。然而下一步必须对左右两边的值进行排序才能完成整体的一个排序结果**。否则是乱序的。

• **首先先对右边的值进行排序

  随机挑选一个6号元素作为基准值。

然后下面再根据小于基准值的元素放左边，大于放右边的原理进行排序操作。结果如下图。

• 此时右边的元素已经完成了排序，但是左边只有一个元素5，所以是已排序完成的状态，而右边分别还有三个8,9,7没有排序，如同上述步骤一样，下面继续选出基准值，小的放左边，大的放右边。

选择了8作为基准值，然后分别将9和7与基准值比较后，基准值8的两边都只有一个数据，所以不需要任何的排序操作了。结果图如下

• 至此右边比基准值4大的元素就排序完成了，效果如下图。
  • **
• 以4为基准值，右边的元素排序完成后（此时左边还未排序）
  • 

接下来就剩左边3，1, 2三个比4基准值小的元素未排序，操作与右边相同，也是首先随机挑出一个基准值，然后将最小的放左边，最大的放在右边，最后完成排序。

• 至此整个快速排序原理图解就介绍完毕。

代码实现（Java）

public static void main(String[] args) {
    int[] arrays = { 3, 5, 8, 1, 2, 9, 4, 7, 6 };
    quickSort(arrays,0, arrays.length - 1);
    System.out.println(Arrays.toString(arrays));
}
public static void quickSort(int[] arrays,int left,int right) {
    int pivot = arrays[left]; // 以最左元素为基准值。
    int i = left; // 表示最左边元素
    int j = right; // 表示最右边元素
    while (i < j) { // 如果左边元素小于右边元素。再进行下面的循环
        while (arrays[j] > pivot) { // 寻找比基准值小的数
            j--;
        }
        while (arrays[i] < pivot) { // 寻找比基准值大的数
            i++;
        }
        // 比基准值小或大的值再进行下面数值的交换操作。
        int count = arrays[i];
        arrays[i] = arrays[j];
        arrays[j] = count;
    }
    if (i > left){ // 如果i > 最左侧元素则进行下面的递归操作。
        quickSort(arrays,left,i-1);
    }
    if (j < right){ // 如果 j < 最右侧元素则进行下面的递归操作
        quickSort(arrays,j+1,right);
    }
}