快速排序思想及实现

思想(从小到大排序)

总体

对数组进行分区，选定一个元素作为基准，然后将小于基准的元素放在基准的左边，将大于基准的元素放在基准右边，分区完成之后再对左边的元素和右边的元素分别进行分区，直到左右区间不可再分。这采用了分治的思想，使排序速度加快。

分区(分治)

首先，将基准元素放在数组左端；
接着，使用两个指针(此处的指针其实是数组元素的索引)，右指针从数组尾部向数组头部寻找小于基准的元素，左指针从数组头部向数组尾部寻找大于的基准的元素，在寻找的过程中，左指针不能超过右指针。找到这两个指针后，交换其指向的元素；
最后，将基准与小于基准元素的最后一个元素进行交换，从而实现这样的效果：[小于基准的元素们, 基准, 大于基准的元素们]。

寻找基准

实际上，寻找基准也不是一个简单的事，以下有两种策略：

策略一

将待排序区间的左端点作为基准。但这样简单的实现有一个缺点：如果数组的值为从大到小排列，则每次分区都左区间都是空区间，右区间是除已有的基准元素们外的所有剩余元素，这样就会使快速排序降级为冒泡排序。

策略二

找到待排序区间中左端点值、右端点值和中间端点值的中位数。这样就避免了基准元素极度不均衡的问题，就算这三个数分别是最大值、第二大值、第三大值，也能选出一个第二大值来，从而左区间就不可能是空区间了。寻找中位数的原理可以看这篇文章：寻找中位数。

代码实现

C

// 寻找中位数
int medianThree(int arr[], int left, int mid, int right) {int a = arr[left], b = arr[mid], c = arr[right];if ((a < b) ^ (a < c)) {return left;} else if ((b < a) ^ (b < c)) {return mid;} else {return right;}
}
// 交换元素
void swap(int arr[], int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;
}
// 分区
void partition(int arr[], int left, int right) {if (left >= right) { // 如果子区间长度为0或为负数，则退出递归return;}int p = medianThree(arr, left, (left + right) >> 1, right); // 寻找基准的索引swap(arr, left, p); // 让基准成为区间左端点int i = left + 1, j = right;while (i < j) {while (arr[j] >= arr[left] && i < j) { // 寻找小于基准的元素j--;}while (arr[i] <= arr[left] && i < j) { // 寻找大于基准的元素i++;}swap(arr, i, j); // 交换这两个元素}swap(arr, left, i); // 让基准成为区间的分界线，i指向最后一个小于基准的元素partition(arr, left, i - 1); // 对左子区间进行分区partition(arr, i + 1, right); // 对右子区间进行分区
}
// 快速排序
void quickSort(int arr[], int len) {partition(arr, 0, len - 1);
}

Java

java">class Sort {public static void sort(int[] arr) {partition(arr, 0, arr.length - 1);}private static void partition(int[] arr, int left, int right) {if (left >= right) { // 如果子区间长度为0或为负数，则退出递归return;}int p = medianThree(arr, left, (left + right) >> 1, right); // 寻找基准的索引swap(arr, left, p); // 让基准成为区间左端点int i = left + 1, j = right;while (i < j) {while (arr[j] >= arr[left] && i < j) { // 寻找小于基准的元素j--;}while (arr[i] <= arr[left] && i < j) { // 寻找大于基准的元素i++;}swap(arr, i, j); // 交换这两个元素}swap(arr, left, i); // 让基准成为区间的分界线，i指向最后一个小于基准的元素partition(arr, left, i - 1); // 对左子区间进行分区partition(arr, i + 1, right); // 对右子区间进行分区}private static void swap(int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}private static int medianThree(int[] arr, int left, int mid, int right) {int a = arr[left], b = arr[mid], c = arr[right];if ((a < b) ^ (a < c)) {return left;} else if ((b < a) ^ (b < c)) {return mid;} else {return right;}}
}