快速排序java（快速排序空间复杂度）

0. 说明

在计算机中，算法是很重要的一部分，前几天遇到一个面试题，快速排序的问题，今天我们就来简单的讲讲快速排序的问题。

其实算法在计算机中的位置举足轻重，几乎是每一个CSer都知道的，但是个人理解的就是，所有的算法，真的是逃不出最基本的算法，那就是查找和排序。而其他所有的业务中或者是实际应用中的算法，基本上都是这些基本算法的变形或者是结合，所以我们学习算法的时候，要学会最基本的算法，并融会贯通，那么后面在实际开发中，你懂的...

1. 四个思想

分区：即将比较大的问题，分解成为比较小的问题，再对这些比较小的问题进行求解，然后再将小问题的结果合并在一起，成为最终的结果。这也是快速排序的核心思想。

归并：归并是将比较小的已有结果的问题按照一定的规则结合在一起得到一个比较大的问题的结果，这其中有多路归并的概念，二路归并是其中一种多路归并，这里的多就是二，在快速排序中，算做是三路归并。

递归：递归的思想，是将数据量比较大的问题，一层一层的拨开，知道体量小到很容易得到结果的时候，然后再回归知道最终的结果，在快速排序中递归不能算作是核心的思想，但是代码中一般会用到。

2. 快速排序的原理

我们先大概的讲下快速排序的原理，然后再利用图示的方法，具体讲一下快速排序的排序过程。本文中的待排序集合暂时记为数组类型。

原理：

1. 首先是在待排序数组中选择一个基准数据，一般就是选择第一个数据；
2. 然后将数组中比基准数据小的数据移动到基准数据的左边（这里是从小到大排序，从大到小的排序正好相反），比基准数据大的数据移动到基准数据的右边；（分区）
3. 然后将基准数据左边的数据看作一个新的数组，将基准数据右边的数据看作是一个新的数组。分别对这两个数据进行快速排序（递归）
4. 直到所有的子数组都是有序的，那么就可以保证整个数组是有序的。
5. 也就是基准数据的左边都比基准数据小，右边都比基准数据大，且都是有序的，所以合并起来就是有序的（归并）

为了解释的比较方便，下面的图示示例和后面的代码是相互呼应的。

给定数组：[10,9,19,8,18,7,17,6,16,5,15,4,14,3,13,2,12]。如图所示：

然后首先是选择基准数据为第一个数据，即tmp = 10，也就是是10，然后将第二个数据的坐标设置为low，把最后一个数据的坐标设置为high。如图：

下面开始从右边开始，也就是high开始遍历， 如果high对应的数据大于tmp，则high指针往前移动一次，否则将low位的数据设置为high位的数据，然后变换位移动low指针，low开始增加，直到遇到一个数值大于基准数据tmp的时候。

刚开始high位的值是12，比基准数据10大，所以high--,这个时候，high位的值是2，如图：

这个时候开始，将low位的数据修改为high位的值，然后移动low指针，low++ 判断low==high?，如果low<high，那么比较新的low位的值，如图：

这时，low位的数据是9，比基准数据小，所继续low++, 有，如图：

low位的数据是19，比基准数据大，那么将high位的数据改为low位的数据，也就是19，然后high--，如图：

high位的数据是13，比基准数据大，所以继续high--，然后是3，比基准数据小，所以low位的数据改为3，并将low++， 这时low位是8，还是比基准数据小，所以继续low++，如图：

类似的依次操作下去，直到low==high-1的时候，如图：

此时是变更了high位的值，随意应该有high--，此时有high==low了，如图：

此时将low位（也就是high位）的数据修改位基准数据。如图：

这个时候，就可以递归的进行基准数据前的部分数据，和基准数据后的部分数据，直到子问题只有一个或者0个的时候，结束递归。

3. java实现

个人主要语言是java，所以这里就是java做一个实现，请看代码：

public class FastSort {
 public static Integer[] sort(Integer[] arr, int low, int high) {
 if (low >= high) {
 return arr;
 }
 int head = low;
 int tail = high;
 int tmp = arr[low];
 while (low < high) {
 while (high > low && arr[high] > tmp) {
 high--;
 }
 arr[low] = arr[high];
 while (high > low && arr[low] < tmp) {
 low++;
 }
 arr[high] = arr[low];
 }
 arr[low] = tmp;
 sort(arr, head, low - 1);
 sort(arr, low + 1, tail);
 return arr;
 }
}

test代码：

@Test
public void test_fast_sort() {
 Integer[] arr = new Integer[]{10,9,19,8,18,7,17,6,16,5,15,4,14,3,13,2,12};
 System.out.println(Arrays.toString(arr));
 arr = FastSort.sort(arr, 0, arr.length - 1);
 System.out.println(Arrays.toString(arr));
}

运行结果：

[10, 9, 19, 8, 18, 7, 17, 6, 16, 5, 15, 4, 14, 3, 13, 2, 12]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19]
Process finished with exit code 0

第一行是初始化的数据，第二行是排序后的数据，从大到小。

4. 总结

快速排序主要用到的思想是分区，分治，和归并的思想，其算法复杂度是O(nlogn)，但是不是稳定的，上面的实现方式还保证了是本地排序算法，对于这些不理解的概念，大家可以自行百度或者google。

希望本文能对您理解快速排序有所帮助。

求评论、点赞、关注+转发。

限于笔者知识有限，如果不足之处请帮忙指正，不喜勿喷！

您的支持是我不懈努力的动力，请读者多支持下！

更多文章，请关注微信公众号 CS_Toper之路，或者头条号 CSToper。