● 稳定性：在排序过程中，如果有两个元素的值相等，那么它们在排序前后的相对位置不会发生改变。
4、希尔排序：是插入排序的改进版，又称缩小增量(gap)排序。
基本思想：根据这个增量来划分组，每一组进行插入排序，所有组排序后称为一趟希尔排序。本质是对数组的局部进行排序。
重复此过程：gap = len/2；gap = gap/2 => 直到gap = 1，做最后一次排序。（排序可以是任意一种）
5、归并： 稳定，时间：O(nlogn)，树高度为O(logn)，每层的时间复杂度为O(n)。空间：O(n)
C++
void merge(int a[], int b,int m, int e){
int i = b;
int j = m + 1;
// 必须从0开始，因为申请的新空间是从索引0开始的，复制的只是值。
int k = 0;
// 新数据可能会存在覆盖旧数据的情况，所以必须重新开辟一个数组
vector<int> v(a, a + sizeof(a)/sizeof(int));
while(i <= m && j <= e){
if(a[i] <= a[j]) v[k++] = a[i++];
else v[k++] = a[j++];
}
while(i <= m) v[k++] = a[i++];
while(j <= e) v[k++] = a[j++];
for(int t = b;t <= e;t++){
a[t] = v[t - b];
}
}
void mergeSort(int a[], int b, int e){
if(b >= e) return;
int m = (b + e)/2;
mergeSort(a, b, m);
mergeSort(a, m + 1, e);
merge(a, b, m, e);
}
⭕ 另：涉及到跟磁盘打交道（外部排序），则需要特殊的考虑。归并排序是天然适合外部排序的算法，可以将分割后的子数组写到单个文件中，归并时将小文件合并为更大的文件【利用双指针合并】。
6、快排：不稳定，时间：O(nlogn)，空间：O(logn)
C++
//快排
int findPartition(int a[], int b, int e){
int base = a[b];
int i = b;
int j = e;
while(i < j){
while(i < j && base <= a[j]) j--;
a[i] = a[j];
while(i < j && base >= a[i]) i++;
a[j] = a[i];
}
a[i] = base;
return i;
}
void quickSort(int a[], int b, int e){
if(b >= e) return;
int index = findPartition(a, b, e);
quickSort(a, b, index - 1);
quickSort(a, index + 1, e);
}
快排优化
① Tail Call（尾调用）：尽量使得函数调用发生在最后，此时父函数无需保存自身变量等等，从而节省了空间。
普通快排选择最左元素为基准值，在数组元素完全倒序时，会导致递归栈深度到达N（即最差空间复杂度O(N)）。
优化策略：不再对左右两个数组都进行递归，而是将较短的子数组递归，可以将最差的递归深度控制在O(logN)。
● 理解：当数组完全倒序时，下一个递归方法压栈时，栈是空的（因为已经处理好上一个递归方法了），这种尾调用可使得递归深度更小。
只需修改quickSort函数：
void quickSort(int[] nums, int l, int r) {
// 子数组长度为 1 时终止递归
while (l < r) { 【注意！】
// 哨兵划分操作
int i = partition(nums, l, r);
// 仅递归至较短子数组，控制递归深度
if (i - l < r - i) {
quickSort(nums, l, i - 1);
l = i + 1; 【注意！】
} else {
quickSort(nums, i + 1, r);
r = i - 1; 【注意！】
}
}
}
⭕另外：当数据量比较大的时候先用的快排，当数据量小的时候可以考虑用【直接插入】，因为当数据量变小时，快排中的每个部分基本有序，接近直接插入的最好情况的时间复杂度O(n)，就比快排要好一点了。
② 随机基准数：不是总选最左元素，而是随机选择一个元素作为基准数（选择完毕后，可跟最左元素交换位置）
只需修改partition函数：
int partition(int[] nums, int l, int r) {
// 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
int ra = (int)(l + Math.random() * (r - l + 1));
swap(nums, l, ra);
……
}
⭕另外：中枢选择除了随机，还可以使用【三数取中】策略。即知道数列的首尾后，我们便可以求出中间位置的数，我们只需要在首，中，尾这三个数据中，选择一个排在中间的数据作为基准值。
7、堆排序: 不稳定，时间：O(nlogn)，空间：O(1)
C++
void heapAdjust(int a[], int len, int t){
int target = a[t];
for(int i = t * 2 + 1; i < len; i = t * 2 + 1){
if(i + 1 < len && a[i] < a[i + 1]) i++;
if(a[i] <= target) break;
else{
a[t] = a[i];
t = i;
}
}
a[t] = target;
}
void heapSort(int a[], int len){
// 构建大根堆
for(int i = len/2 - 1; i >= 0; i--){
heapAdjust(a, len, i);
}
// 堆排序
for(int i = len - 1; i > 0; i--){
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapAdjust(a, i, 0);
}
}
8、计数排序——不基于比较的排序
基本思想：找到数组种最小和最大的元素，得到他们的差值范围，申请额外空间。然后遍历数组，在额外的空间中统计对应位置的数量。根据额外空间中的统计信息，根据数量打印数据。
优势：在对一定范围内的整数排序时，他的复杂度为O(n+k)(其中k是整数的范围)，快于任何比较的排序算法。
劣势：它是一种牺牲空间，换取时间的做法。如果O(k)>O(nlogn)时，它的效率反而不如基于比较的排序算法。
9、桶排序（箱排序）——不基于比较的排序
基本思想：将数组分到有限数量的桶子(划分数据范围)里。将数组中的元素分配到这些桶中，对桶中的元素进行排序(有可能是再使用别的排序算法，或者是以递归的方式继续使用桶排序)。将每个桶中排好序的元素，按照桶的顺序依次输出。
10、基数排序：桶排序的扩展，是一种效率高的稳定排序法——不基于比较的排序
基本思想：根据数值的个位、十位、百位……来将数据装入桶中。确定数组中最大元素的位数(并将其他数通过高位补0的操作，达到位数对齐的目的)，这决定了装桶操作的轮数。每一轮装桶(从最低位个位开始)，需要判断元素当前位，存入对应的桶中(共有0~9，10个桶)。完成这一轮后，出队(按照入桶顺序)，存入原数组。重复操作，直至完成最大轮次。
● 如果是按照：个位→十位→百位→……，那么就是不断迭代，将数按顺序重复几轮（数位决定了轮次）装入0-9的桶中；
● 如果是按照：……→百位→十位→个位，那么就是演变成桶排序，需要在各自的桶中继续进行排序。
