如何高效实现快速排序算法？

本文共计486个文字，预计阅读时间需要2分钟。

快速排序是一种经典的排序算法，其排序速度非常快！平均时间复杂度可达到O(nlogn)。

排序过程：

1.首先选择数组中的一个数字A作为基准。

2.遍历数组，将比A小的数移到左侧，比A大的数移到右侧。

快速排序

快速排序是一种经典的排序算法，和它的名字一样，它的排序速度非常快！平均时间复杂度可以达到O(nlogn)。

排序过程

1. 首先选择数组中的一个数字A
2. 遍历数组，将比A小的数移动到A的左边，将比A大的数移动到A的右边，完成后数组被分成左右两个区域，左边全部比A小，右边全部比A大
3. 对元素数量大于1的区域，执行1、2、3三个操作

大致过程如下图：

快速排序的过程，虽然不难理解，但是这里也存在几个问题：

1. 数字A该如何选择？数字A的选择其实是一件非常重的事情，数字A选的好可以使算法的时间复杂度更接近平均时间复杂度O(nlogn)，其中缘由我就不赘述了，实际中我们只需要随机选择一个就可以了，随机选择效果已经足够好了，而且很简单。

2. 选好数字A后，如何将比A小的数移动到A的左边，将比A大的数移动到A的右边？过程如下图：

Java实现

public class Sort { // 排序数组中从索引from（包含）到索引to（不包含）范围内的数字 public static void quickSort(int[] arr, int from, int to) { if (from + 1 >= to) return; int less = from - 1; int large = to; int mid = arr[from + new Random().nextInt(to)]; int cur = from; while (cur < large) { if (arr[cur] < mid) { swap(arr, cur, less + 1); less++; } if (arr[cur] > mid) { swap(arr, cur, large - 1); large--; continue; } cur++; } quickSort(arr, from, less + 1); quickSort(arr, large, to); } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }