【本文版权归微信公众号"代码艺术"（ID：onblog）所有，若是转载请务必保留本段原创声明，违者必究。若是文章有不足之处，欢迎关注微信公众号私信与我进行交流！】
算法概述
快速排序（Quicksort），又称划分交换排序，简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要O(n log n)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。
事实上，快速排序O(n log n)通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。
算法流程
快速排序使用分治法策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：
-
挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
-
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
-
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。
选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
算法步骤
快速排序的算法步骤我给划分为5步：
- 递归终止条件
- 定义头尾指针与基准值
- 把小于基准数的移到左边，把大于基准数的移到右边
- 继续处理左边的
- 继续处理右边的
示例代码
public class QuickSort {
public static void qSort(int[] arr, int head, int tail) {
if (head >= tail || arr == null || arr.length <= 1) {
return;
}
//定义俩指针 用于移动
int left = head;
int right = tail;
int pivot = arr[head]; //基准值，也可以arr[(head + tail) / 2]
while (left <= right) {
while (arr[left] < pivot) { //左指针先走，找到大于等于基准数的停止
++left;
}
while (arr[right] > pivot) { //右指针后走，找到小于等于基准数的停止
--right;
}
if (left < right) {
//交换arr[left]和arr[right]的位置
int t = arr[left];
arr[left] = arr[right];
arr[right] = t;
//继续遍历
++left;
--right;
} else if (left == right) {
//遍历完，错开两指针
++left;
//break;
}
}
qSort(arr, head, right);
qSort(arr, left, tail);
}
public static void main(String[] args) {
int[] arr = new int[]{6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
qSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
打印输出：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
在程序运行中，可以通过打印排序前和排序后的数列观察运行流程
对数组 [6 1 2 7 9 3 4 5 10 8 ] 排序， 排序后 [5 1 2 4 3 9 7 (6) 10 8 ]
对数组 [5 1 2 4 3 ] 排序， 排序后 [3 1 2 4 (5) 9 7 6 10 8 ]
对数组 [3 1 2 4 ] 排序， 排序后 [2 1 (3) 4 5 9 7 6 10 8 ]
对数组 [2 1 ] 排序， 排序后 [1 (2) 3 4 5 9 7 6 10 8 ]
对数组 [3 4 ] 排序， 排序后 [1 2 (3) 4 5 9 7 6 10 8 ]
对数组 [9 7 6 10 8 ] 排序， 排序后 [1 2 3 4 5 8 7 6 10 (9) ]
对数组 [8 7 6 ] 排序， 排序后 [1 2 3 4 5 6 7 (8) 10 9 ]
对数组 [6 7 ] 排序， 排序后 [1 2 3 4 5 (6) 7 8 10 9 ]
对数组 [10 9 ] 排序， 排序后 [1 2 3 4 5 6 7 8 9 (10) ]
复杂度分析
【本文版权归微信公众号"代码艺术"（ID：onblog）所有，若是转载请务必保留本段原创声明，违者必究。若是文章有不足之处，欢迎关注微信公众号私信与我进行交流！】
时间复杂度
数组有n个元素，因为要递归运算，算出支点pivot的位置，然后递归调用左半部分和有半部分，这个时候理解上是若第一层的话就是n/2、n/2，若是第二层就是n/4、n/4、n/4、n/4这四部分，即n个元素理解上是一共有几层2^k=n，k=log2(n)，然后每层都是n的复杂度，那么平均就是O(nlog2 n)的时间复杂度。但这种肯定是平均情况，如果你是标准排序的情况下，如果已经是升序的顺序，那么递归只存在右半部分了，左半部分都被淘汰了。(n-1)(n-2)....*1，这个复杂度肯定就是O(n^2)。
空间复杂度
快排的实现是递归调用的， 而且每次函数调用中只使用了常数的空间，因此空间复杂度等于递归深度。
最好的情况最多需要O(log2 n)次的嵌套递归调用，所以它需要O(log2 n)的空间。最坏情况下需要O(n)次嵌套递归调用，因此需要O(n)的空间。
时间复杂度引用自知乎
版权声明
【本文版权归微信公众号"代码艺术"（ID：onblog）所有，若是转载请务必保留本段原创声明，违者必究。若是文章有不足之处，欢迎关注微信公众号私信与我进行交流！】
