算法-基本排序算法-06 快速排序详解

1. 要点

选取基础列表中一个元素为中点（也称之为 基准数，pivot,这里我们选择的是列表的最左边的第一个数字)将比这个中点小的数移动到左边，（自然大的数就到了右边，但是左边和右边的数字依旧是无序的）递归继续以左边的数和右边的数为基础列表继续移动，直到基础列表的元素个数为1

2.图展示

2.1 过程图解.

这是一个[5,1,9,3,7,4,8,6,2,10] 快速排序的例子

2.2 动图演示

3.算法步骤

选取列表中一个元素为中点（也称之为 基准数，pivot,这里我们选择的是列表的最左边的第一个数字)将比这个中点小的数移动到左边，（自然大的数就到了右边，但是左边和右边的数字依旧是无序的）递归继续以左边的数和右边的数为基础继续移动，直到基础列表的元素个数为1

重点：如何将比中点小的数移动到左边?

因为类似冒泡排序的依次移动会浪费大量的时间来移动，我们这里采用一种新的办法，比如上面的例子，数组为 [5,1,9,3,7,4,8,6,2,10],我们想办法移动到如图下 第二个数组的情况，在交换中值（5）和最后一个左值（2）即可

重点：如何移动到上图中第二行的效果？ 请参考代码，重点理解，【index】指针(下标)的作用

4.代码

java代码实现

public class QuickSort { /** * 调用递归快速排序 */ public int[] sort(int[] arrays) { return quickSort(arrays, 0, arrays.length - 1); } /** * 递归快速排序 */ private int[] quickSort(int[] array, int left, int right) { //如果数组的元素个数为1 完成退出递归. if (left < right) { //调用partition（）将小的值放到左边，并返回中间值的位置 int middle = partition(array, left, right); //递归继续排序中值左边的数组和右边的数组，直到数组的元素个数为1 quickSort(array, left, middle - 1); quickSort(array, middle + 1, right); } return array; } /** * partition 是划分的意思，这个方法是核心 * 将比中值小的值移动到右边并返回移动后中值的下标 */ private int partition(int[] array, int left, int right) { //这里举例以最左边的值作为中值. int middle = left; //重点理解，【index】指针(下标)的作用，（实现值的交换） int index = middle + 1; for (int i = index; i <= right; i++) { if (array[i] < array[middle]) { //如果比中值小就交换. swap(array, index, i); index++; } } //将中值放置到数组的中间 swap(array, middle, index - 1); return index - 1; } /** * 简单的交换2个下标的值. */ private void swap(int[] array, int index1, int index2) { int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } }

5.优缺点

快速排序的优点就是快，虽然他的最坏的情况的时间复杂度是O(n2)但是更多的时候这个算法比O(n 3/2)更快。但是快速排序无法保证相等的元素相对位置不变，因此它是不稳定的算法

6. 拓展链接