十大经典排序算法
快速排序（Quicksort）的原理就是先把数组分成两部分，其中左边的任何一个元素都小于右边的任何一个元素，通俗一点就是左边的最大值小于右边的最小值。分成这样的两部分之后，然后继续对左边和右边进行同样的操作，实际上就是把一个大问题拆成两个小的问题，我们发现他就是个递归，那么递归的终止条件是什么呢，就是数组为空或者只剩下一个元素为止，因为这样就没法在分了。怎么分呢？这里有多种方式，一种是用待排序序列的第一个元素作为中枢值，把序列中小于中枢值的往前挪，最后在把中枢值放到合适的位置，如下图所示，他的步骤如下：
- 选择待排序序列的第一个元素作为中枢值，并使用两个指针 i 和 j，其中 j 指向待排序列的第一个元素，i 指向待排序列的第二个元素 。
- 如果 nums[i] 比中枢值大，i 往右移一步，j 不动。
- 如果 nums[i] 比中枢值小，j 先往右移一步，然后和 i 指向的值交换（目的就是把小的往前挪），接着 i 往右移，继续重复上面的步骤。
上面只是进行了第一轮的划分，划分为两部分之后左边的值都比右边的值小，接着在对左边和右边进行同样的划分，直到不能划分为止。
public void quickSort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
}
/**
* @param nums 待排序的数组。
* @param start 待排序开始的位置，闭区间。
* @param end 待排序结束的位置，闭区间。
*/
public void quickSort(int[] nums, int start, int end) {
if (start < end) {
// 划分，把数组分为两部分。
int j = partition(nums, start, end);
quickSort(nums, start, j - 1);// 递归左边部分。
quickSort(nums, j + 1, end); // 递归右边部分。
}
}
// 这个是快排的重点，使用数组中的第一个元素作为中枢值，把数组分为两部分。
private int partition(int[] nums, int start, int end) {
// 默认数组的第一个元素作为中枢值。
int pivotValue = nums[start];
int j = start;// 使用 i ，j 两个指针。
for (int i = start + 1; i <= end; i++) {
// 当前元素始终和中枢值进行比较，如果小于中枢值就往前挪。
if (nums[i] < pivotValue)
swap(nums, ++j, i); // 交换之前，j 需要先往后挪一步。
}
swap(nums, j, start);// 交换位置。
return j;// 返回中枢值的下标。
}
上面数组划分，最开始的时候中枢值位置始终保持不动，等划分为之后我们在把中枢值放到合适的位置，其实还有一种方式就是中枢值始终是变动的，如下图所示，他的实现原理如下。
- 使用数组的第一个元素作为中枢值，从后面往前查找小于中枢值的元素，然后交换。
- 交换完之后在从前往后查找大于中枢值的元素然后再交换。
- 继续上面的步骤
……。
第一轮结束之后就把数组分成了两部分，来看下代码，主要来看下数组划分的这个方法，其他都是一样的。
private int partition(int[] nums, int start, int end) {
// 默认数组的第一个元素作为中枢值。
int pivotValue = nums[start];
while (start < end) {
// 从后往前查找小于中枢值的元素。
while (start < end && nums[end] >= pivotValue)
--end;
swap(nums, start, end);// 将这个小的元素和中枢值。
// 从前往后查找大于中枢值的元素。
while (start < end && nums[start] <= pivotValue)
++start;
swap(nums, start, end);// 将这个大的元素和中枢值。
}
return start;// 返回中枢值所在的位置。
}
稳定性分析
快速排序的原理就是把小于中枢值的元素往前挪，挪的时候涉及到交换，就有可能打乱原来相同元素的相对顺序，比如数组 【2,3,3,1】 为了区分两个 3 ，我们用 third 来表示第二个 3 ，也就是 【2,3,third,1】 。刚开始的时候因为中枢值不变，并且 1 小于 3 ，所以就会和第一个 3 交换，变成了 【2,1,third,3】 ，然后在把中枢值放到合适的位置 【1,2,third,3】 ，其实我们发现在第一轮交换的时候两个 3 的相对位置就已经发生了变化，所以快速排序是不稳定的。可以把它看做是二叉树的前序遍历，就是先分割数组，然后递归左右两个子数组，时间复杂度是 O(n*log(n)) ，空间复杂度是 O(log(n)) 。
时间复杂度： O(n*log(n))
稳定性：不稳定
| 冒泡排序 ，选择排序 ，插入排序 ，快速排序 ，归并排序 ，堆排序 ，桶排序 ，基数排序 ，希尔排序 ，计数排序 ，位图排序 ，拓扑排序 ，二叉树排序 ，Bogo排序 ，睡眠排序 ，鸡尾酒排序 ，侏儒排序 ，臭皮匠排序 ，图书馆排序 ，珠排序 ，链表排序 ，鸽巢排序 ，奇偶排序 ，慢速排序 ，耐心排序 ，梳排序 ，煎饼排序 ，插值排序 |
