轻松学习快速排序（一 ） - 基本的快速排序

快速排序（Quicksort），又称划分交换排序（partition-exchange sort），简称快排，最早由东尼·霍尔提出，是一种较快的排序算法。对n项进行排序平均要做O(nlogn)次比较，最差的情况下需要做O(n2)次比较。本文将介绍快速排序的基本思想及其实现。

基本思想

它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。排序的过程是一个不断挖坑、填坑的过程。

首先选取一个基准点（Base），此时基准点所在位置就是一个坑；

从右往左找到比基准点小的数字，在该位置挖出一个坑并将该数字放入左边的坑；

从左边的坑开始，从左往右找出比基准点大的数字，在该位置挖出一个坑并将该数字放入第二步中在右边的坑；

重复第二步和第三步，直到左右两边的坑重叠，将基准点放入该坑；

此时基准点已经将数组分成了两个区：左边的区、右边的区。然后在左右两边在执行1,2,3,4,5的操作，直到分区中只有一个数字。

假设我们要对10 22 78 6 1 12 14 45 进行排序，首先取第一个数（10）作为基准点：

初始状态：base = 10（红色的字体的数字表示基准点）

从右往左找比基准点（10）小的数字，发现位于数组中的序号为4的数字1比基准点（10）小，于是将数字1填入序号为0的基准点的坑中去。红色背景色的单元格表示刚被填充过的坑，灰色的背景色表示刚挖出来的坑，下面同理。

从左（从序号1开始）往右找比基准点（10）大的数字，发现序号为1的数字22比基准点大，于是将数字22填入序号为5的坑中

接下来不在累叙上面的步骤，只给出操作：

至此对基准点（10）不能再继续进行填坑操作，于是将基准点（10）填入最后的坑中，很显然，基准点（10）已经将该数组分成了两部分：

然后对基准点（10）的左右两边（红色背景色部分）再执行相同的操作

JAVA代码实现 static void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } int first = left, last = right; int base = arr[first]; while (first < last) { for (; first < last; last--) { if (arr[last] < base) { arr[first++] = arr[last]; break; } } for (; first < last; first++) { if (arr[first] > base) { arr[last--] = arr[first]; break; } } } arr[first] = base; quickSort(arr, left, first - 1); quickSort(arr, first + 1, right); } static void quickSort(int[] arr) { quickSort(arr, 0, arr.length - 1); }

如上的代码给出了快速排序的基本实现，主要运用到了中所阐述的实现思想，将上面的例子在代码中运行：

public static void main(String[] args) { int[] arr = new int[] {10, 22, 78, 6, 1, 12, 14, 45}; System.out.println("原始数组：" + Arrays.toString(arr)); quickSort(arr); System.out.println("排序后的数组：" + Arrays.toString(arr)); }

运行结果为：

原始数组：[10, 22, 78, 6, 1, 12, 14, 45] 排序后的数组：[1, 6, 10, 12, 14, 22, 45, 78] 总结

快速排序算法是一种比较常见的排序算法，其排序的过程是不断挖坑、填坑的过程，然后将待排序数组分区。思考一个问题：假如运气不好选择的基准点是整个数组中最大或者最小的数字，那么会怎么样呢？例如这样的一个数组：1 10 23 6 9 10，如果选择数字1作为基准点，那么或发生什么？