1、快速排序介绍

快速排序也是一种分治法的典型应用，它本质上可以认为是建立在冒泡排序基础上的递归分治法。

2、快速排序的步骤

首先，在所有序列元素中随机找出一个，作为“基准值”，然后把整个序列基于基准值进行重新排列，小于基准值的放在它左边，大于基准值的放在它的右边，重新排列完，这个基准值元素的位置就是排序后的位置了，同时，也产生了两个子序列，然后对两个子序列再用同样的方式，找一个基准值，对子序列重新排列…，直到最后子序列只有一个元素或0个元素（递归最底层的情形），这时，序列就排完序了。

以图为例，假设初始无序序列为：

第一步，我们先找一个基准值，因为这是随机找的，所以，我们就把最左边的元素，也就是第一个元素4当做基准，如下：

然后开始重建序列，重建的原则就是，最后让基准值左边的都比它本身小，它右边的都比它本身大。我们首先设定两个指针，一个快指针，用来挨个遍历基准值后边的元素，一个慢指针，用来标记比基准值小的元素的位置。这两个指针起始位置都是基准值后边的元素，即元素值为5的元素，如下：

比较快指针指向元素的值是否比基准值小，因为5>4，慢指针不动，仍然指向5，快指针移动一步指向8，如下：

比较快指针指向元素的值是否比基准值小，因为8>4，慢指针不动，仍然指向5，快指针移动一步指向2，如下：

比较快指针指向元素的值是否比基准值小，因为2<4，交换快慢指针元素的位置，然后快慢指针都指向下一个元素，如下：

比较快指针指向元素的值是否比基准值小，因为3<4，交换快慢指针元素的位置，然后快慢指针都指向下一个元素，如下：

比较快指针指向元素的值是否比基准值小，因为7>4，慢指针不动，仍然指向5，快指针移动一步指向9，如下：

比较快指针指向元素的值是否比基准值小，因为9>4，慢指针不动，仍然指向5，快指针移动一步指向1，如下：

比较快指针指向元素的值是否比基准值小，因为1<4，交换快慢指针元素的位置，然后快慢指针都指向下一个元素，如下：

这时，快指针已经到头了，所以说，已经没有比基准值小的值了，这时，我们把基准值元素和慢指针的前一个元素进行交换，因为慢指针左边的永远小于基准值，而且基准值在序列最左边，交换之后，就可以满足基准值左边的元素都小于它，如下：

这就保证了不管接下来如何排序，这个基准值4，最后的位置一定是这里。接下来，按照上边的逻辑，分别对基准值4两边的序列进行同样的操作，结果如下：

接着对元素1右边的子序列、元素8两边的序列进行同样的操作，结果如下：

最后对元素2右边的序列、元素5右边的序列进行同样的操作，即完成排序，如下：

3、代码实现（java版本）

public class QuickSort {	public static void quickSort(int[] arr) {		if (arr == null || arr.length < 2) {			return;		}		quickSort(arr, 0, arr.length - 1);	}	private static void 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);		}	}	private static int partition(int[] arr, int left, int right) {		// 选定一个基准值，基准值可以随机取任何一个值，我们这里选择最左边的元素作为基准值，直接用left表示就可以		// index永远指向基准值位置的下一个位置，或者说，index左边的 都是比基准值小的元素		int index = left + 1;		// 开始遍历序列，基准值选择了序列最左边的元素，所以从第二个开始往后，挨个和基准值比较		for (int i = index; i <= right; i++) {			// i是从前往后的一个快指针			if (arr[i] < arr[left]) {				// 如果比基准值小，说明它应该在基准值的左边，交换i和index位置的元素位置，保证index左边都是比它小的元素				swap(arr, i, index);				index++;			}		}		// 最后，把index左边的元素和基准值交换，因为index左边的元素本来就是比基准值小的，所以换完对排序没影响		swap(arr, left, index - 1);		// 最后基准值的位置就是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;	}}

4、复杂度分析

对于快排而言，基准的选择，对排序效率有很大的影响，如果根据基准值，每次划分的两个子序列其中一个总是只包含一个元素（如示例中产生过的情况），那么快排的时间复杂度为O( $n^2$ )，如果根据基准值，每次划分的两个子序列包含的元素数量是一致的，那么快排的时间复杂度为O( $n l o g n$ )。但是，最坏的情况发生的概率是很低的，因为在每一次划分的时候，都让一边只包含一个元素的情况是几乎不可能发生的，所以快排的平均时间复杂度是O( $n l o g n$ )。

转载地址：http://zayin.baihongyu.com/

你可能感兴趣的文章