echo编辑整理，欢迎转载，转载请声明文章来源。欢迎添加echo微信(微信号：t2421499075) 交流学习。

---

什么快速排序？

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

动图演示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lZHD27ic-1605754197370)(www.runoob.com/wp-content/uploads/2019/03/quickSort.gif)]

声明图片来源菜鸟教程

Java代码实现

public class Test {public static void main(String[] args) {int[] arr = {1, 3, 6, 9, 2, 5, 11, 4, 8};print("原数组: ", arr);quickSort(arr, 0, arr.length - 1);print("排序后的数组: ", arr);}private static int[] quickSort(int[] arr, int left, int right) {if (left < right) {int partitionIndex = partition(arr, left, right);quickSort(arr, left, partitionIndex - 1);quickSort(arr, partitionIndex + 1, right);}return arr;}private static int partition(int[] arr, int left, int right) {// 设定基准值（pivot）int pivot = left;int index = pivot + 1;for (int i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index);index++;}}swap(arr, pivot, index - 1);return index - 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}private static void print(String str, int[] arr) {for (int i = 0; i <= arr.length - 1; i++) {if (i == 0) {System.out.print(str + "[" + arr[i] + ", ");} else if (i == arr.length - 1) {System.out.print(arr[i] + "]");} else {System.out.print(arr[i] + ", ");}}System.out.println();}}

核心原理

从数列中挑出一个元素，称为 “基准”（pivot）找其正确索引位置的过程.;

算法过程如下

• 首先我们从数组的left位置取出该数（1）作为基准（base）参照物。
• 从数组的right位置向前找，一直找到比（base）小的数，
• 从数组的left位置向后找，一直找到比（base）大的数，
• 不算循环以上的动作

时间复杂度

O(nlogn) - O(n^2)

快速排序的优缺点

优点：平均性能好，O(nlog2n)，2为下标
缺点：不稳定，初始序列有序或基本有序时，时间复杂度降为O(n^2)。

适用场景

适用于随机分布的数据集