总览
参考：https://www.cnblogs.com/onepixel/articles/7674659.html
冒泡：每次将最小的放到前面
插入：构造有序序列，没排序的在排序好的序列中，从后往前扫描，插入
选择：每次把最大的放到后面
希尔：根据间隔将数组分成多部分，对每个部分进行插入排序；需要对增量间隔把控的很好
快速：随机选取数组中一个值作为基准，将比基准大的都放在右边，比基准小的放在左边，再分别对左、右序列迭代，不稳定，时间nlogn，可能n2，空间
归并：采用分治法，将有序的子序列合并，得到完全有序的序列，稳定，时间nlogn，空间n
计数：将数值当做为数组下标，数组的值是出现的次数
基数：低位0-9排到对应下标数组中，从低位到高位
桶：计数排序的升级，利用函数映射关系，根据值确定桶，在桶里排序
堆：利用堆结构进行排序，堆是接近完全二叉树的结构，子节点的总是小于（大于）父节点
稳定：冒泡、插入、归并
不稳定：希尔、快速、选择、堆排序
快速排序
解题思路
数组中随机选择一个值基准，将所有比基准小的值放在其左边，比基准大放在其右边
[ [比基准小的数据] 基准 [比基准大的数据] ]
分别对基准的左右部分迭代，得到有序数组。
基准左右分离
假设取数组最左边（arr[low]）为基准，保存为temp
- 从右边high下标开始，high–，找到比基准小的（说明其不该在右边）值，存放进arr[low]
- 再从左边low下标开始，low++，找到比基准大的（说明其不该在左边）值，存放进arr[high]
在1、2中循环，当 high 等于 low时，说明已经成功分离出比基准大的和比基准小的：
[ [比基准小的数据] 基准 [比基准大的数据] ]
将 temp存入 arr[low]即完成基准左右分离
迭代
每次[比基准小的数据]、[比基准大的数据]看成一个普通的数组，也采取基准左右分离的方法进行迭代，最终可获得递增的数组
随机基准
我们应当选择基准时是随机的，在low和high之间选择随机下标，使用new Random().nextInt(n)可以获取随机数，其范围为[0,n)
我们要获取的是[low, high]，则应当为low + new Random().nextInt(high - low + 1)
将获取到的基准与arr[low]交换，开始基准左右分离
坏情况2
每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。
代码
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int low, int high) {
if( low < high) {
int index = getIndex(nums, low, high);
quickSort(nums, low, index - 1);
quickSort(nums, index + 1, high);
}
}
public int getIndex(int[] nums, int low, int high) {
// low, high获取随机基准
int index = low + new Random().nextInt(high - low + 1);
// 把基准放到第一个
int temp = nums[index];
nums[index] = nums[low];
nums[low] = temp;
// 开始移动
while(low < high) {
// 比基准>=的，high一直左移
while(low < high && nums[high] >= temp) {
high--;
}
// 遇到小的了，把它移到前面
nums[low] = nums[high];
// 比基准<=的，low一直右移
while(low < high && nums[low] <= temp) {
low++;
}
nums[high] = nums[low];
}
// low 和 high 为分界
nums[low] = temp;
return low;
}
}归并排序
将数列递归拆分为两部分，再逐步合并成整体
public void sort(int[] nums, int low, int high) {
int mid = low + (high -low) /2;
if(low < high) {
sort(nums, low, mid);
sort(nums, mid +1, high);
merge(nums, low, high, mid);
}
}
public void merge(int[] nums, int low, int high, int mid) {
int[] tempRes = new int[high -low +1];
int lowIndex = low;
int highIndex = mid +1;
int resIndex = 0;
while(lowIndex <= mid && highIndex <= high) {
if(nums[lowIndex] <= nums[highIndex]) {
tempRes[resIndex++] = nums[lowIndex++];
} else {
tempRes[resIndex++] = nums[highIndex++];
}
}
while(lowIndex <= mid) {
tempRes[resIndex++] = nums[lowIndex++];
}
while(highIndex <= high) {
tempRes[resIndex++] = nums[highIndex++];
}
for (int i = 0; i < tempRes.length; i++) {
nums[i +low] = tempRes[i];
}
}希尔排序
public int[] shellSort(int[] nums) {
int len = nums.length;
// 间隔为一半
for(int gap = len /2; gap > 0; gap /= 2) {
for(int i = gap; i < len; i++) {
int current = nums[i];
int preIndex = i -gap;
while(preIndex >= 0 && current < nums[preIndex]) {
nums[preIndex +gap] = nums[preIndex];
preIndex -= gap;
}
nums[preIndex +gap] = current;
}
}
return nums;
}