JavaDS —— 排序
排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
就例如上图所示：排序前，红色的5 在黑色的 5 之后，如果在排序后 红色的 5 在黑色的 5 之后就是稳定的，否则就是不稳定的。
稳定的排序算法可以变成不稳定的，但是不稳定的排序算法就不可能变成稳定的排序算法。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
插入排序
直接插入排序
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
直接插入排序
直接插入排序会让前面的元素有序，然后不断向后遍历将待排序的元素往前插入即可，直到所有的元素排序完成。
算法思想，首先使用一个大循环，从第二个元素开始遍历数组，因为我们设定第一个元素只用一个本身有序，所以从第二个元素开始排列。
然后接着一个小循环，就是从 i - 1 开始向前遍历，也就是从待排序的元素的前一个已排好的元素开始向前遍历，arr[j+1] = arr[j] ，直到找到恰当的位置将待排序的元素放好（arr[j+1] = tmp）
我们要提前将待排列的元素保存起来。
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= 0; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
} else {
array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
在 j 循环结束后还需要 array[j+1] = tmp; 是因为可能数组首元素的位置就是待排列的元素的位置，因此我们需要加上这一行代码。
还有 j 的结束条件应该为 j >= 0
时间复杂度分析：
i 从 下标 1 开始循环遍历，j 循环执行 1 次
i 从 下标 2 开始循环遍历，j 循环执行 2 次
i 从 下标 3 开始循环遍历，j 循环执行 3 次
… …
i 从 下标 n-1 开始循环遍历，j 循环执行 n-1 次
这是一个等差数列，使用求和公式可得 （1+（n-1））* （n - 1 ) / 2 ，即时间复杂度为 O(N^2)
由于只是使用了一个临时变量的空间，所以空间复杂度为 O(1)
稳定性： 这是一个稳定的排序算法
如果将条件给改为array[j] >= tmp 的话，那么就变成不稳定的排序算法，但是如果不改这个判断条件，那该算法就是稳定的，总体来看：直接插入算法是稳定的。
最好情况的时间复杂度就是当本身就是有序的话，那么最好的时间复杂度为 O(N)
当数据越有序，直接插入排序效率越快
所以使用场景一般用在相对有序的数据排列可以使用直接插入排序算法
希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
我们以 gap 为增量对数组进行划分，对不同的小组进行直接插入排序，最后增量 一定会为 1 ，直接进行直接插入排序，得到的一定是有序的数据。
public static void shellSort(int[] array){
int gap = array.length;
while(gap > 1) {
gap /= 2;
shell(array,gap);
}
}
private static void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i - gap;
for (; j >= 0; j-=gap) {
if(array[j] > tmp) {
array[j+gap] = array[j];
} else {
array[j+gap] = tmp;
break;
}
}
array[j+gap] = tmp;
}
}
这里讲解一下这个算法：for (int i = gap; i < array.length; i++) 这个大家应该很好理解，第一个元素当作是有序的，从 gap 开始遍历数组，即使是不同的组别， i ++ 也能进行排序，只是每次对不同组别进行直接插入排序
这里要注意 j + gap ，因为希尔排序是对不同组别进行直接插入排序的，所以我们要找到对应的组别的成员
希尔排序的特性总结：
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很
快。这样整体而言，可以达到优化的效果。
3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排
序的时间复杂度都不固定：
《数据结构(C语言版)》— 严蔚敏：
《数据结构-用面向对象方法与C++描述》— 殷人昆：
这里我们将希尔排序的时间复杂度记为 n^1.3 到 n^1.5 之间
空间复杂度为 O(1)
希尔排序是不稳定的排序算法
选择排序
直接选择排序
如果是升序排序，首先从第一个元素开始排列，那么就会先从后面的待排序元素中找到最小的，和第一个元素进行交换；降序也是同理。
直接选择排序
以升序为例，我们可以先定义一个临时变量，来保存最小数据的下标，直到遍历完成，下标交换即可。
public static void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int mixIndex = i;
for (int j = i + 1; j < array.length; j++) {
if(array[j] < array[mixIndex]) {
mixIndex = j;
}
}
swap(array,mixIndex,i);
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
很明显可以看出这是一个等差数列，所以时间复杂度为 O(N^2)
并且无论数据原本是有序的还是无序的，时间复杂度依旧还是 O(N^2)，所以直接选择排序算法的效率很低，应用面很小，一般我们不使用该算法进行排序
空间复杂度为 O(1)
是不稳定的算法，如下图所示：
优化的直接选择排序算法：
我们使用双指针法，在遍历的过程中同时找到最大值和最小值，然后放在数据的两端，这样的算法效率就提高了一半。
我们以 left 为基准，发现 left 自己就是最大值，下标 5 对应的 3 是最小值，开始交换，首先最小值换到 0 下标，然后最大值换到 5 下标，但是要注意了第一次交换的过程中发生了最大值已经换到了 5 下标，所以写代码的时候要注意，如果最大值就是 left 的话，在最小值交换完就要堆此时最大值的下标继续处理。
public static void selectSort2(int[] array) {
int left = 0;
int right = array.length - 1;
while(left < right) {
int minIndex = left;
int maxIndex = left;
for (int i = left + 1; i <= right; i++) {
if(array[i] < array[minIndex]) {
minIndex = i;
}
if(array[i] > array[maxIndex]) {
maxIndex = i;
}
}
swap(array,left,minIndex);
//如果maxIndex就是left所对应的数值，那么由于上面left已经和minIndex交换了，所以maxIndex要发生改变
if(maxIndex == left) {
maxIndex = minIndex;
}
swap(array,maxIndex,right);
left++;
right--;
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
堆排序
堆排序在上一篇文章中已经提过，如果不了解的，可以阅读JavaDS —— 优先级队列（堆）PriorityQueue
这里直接上代码，以升序为例：
public static void heapSort(int[] array) {
if(array == null || array.length == 0) {
return;
}
//建立大根堆
creatHeap(array);
//升序排列
int end = array.length - 1;
while(end > 0) {
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private static void creatHeap(int[] array) {
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array, int parent, int size) {
int child = 2*parent + 1;
while(child < size) {
if(child + 1 < size && array[child+1] > array[child]) {
child++;
}
if(array[parent] < array[child]) {
swap(array,parent,child);
parent = child;
child = 2*parent + 1;
} else {
break;
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
时间复杂度为 O(N*log2(N))
空间复杂度为 O(1)
不稳定
交换排序
冒泡排序
冒泡排序
冒泡排序比较简单，这里就不赘述了，直接上优化过的冒泡排序代码：
//冒泡排序
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
boolean flag = false;
for (int j = 0; j < array.length - 1 - i; j++) {
if(array[j] > array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flag = true;
}
}
if(!flag) {
break;
}
}
}
我们讨论冒泡排序的时间复杂度一般从未优化的出发，那么冒泡排序的时间复杂度为 O(N^2)
冒泡排序最好情况下的时间复杂度为O(N)，也就是排列的数据本身就是有序的，但是一般情况下，我们认为冒泡排序的时间复杂度为 O(N^2)
空间复杂度为 O(1)
冒泡排序是稳定的排序算法
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
Hoare版
首先右指针向前遍历，遇到比 Key 大的数值停下，然后左指针开始向后遍历，遇到比 Key 小的数值停下，然后开始交换两个指针所对应的数值，直到两个指针相遇，则此轮排序结束，开始递归左边的子序列。
快速排序Hoare版——第一轮排序
重复之前的操作，直到两个下标相遇~~
快速排序Hoare版——第二轮排序
快速排序Hoare版——第三轮排序
这里就展示这么多，剩下的序列还是和之前的操作一样，左递归完了就开始右边的递归，直到快速排序完成。
从上面的视频中，我们可以了解为什么快速排序是一种二叉树结构的交换排序算法，将一个数组不断地拆分，就类似一颗二叉树。
这里以升序为例：
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if(left >= right) {
return;
}
int pivot = partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static int partition(int[] array, int left, int right) {
int tmp = array[left];
int tmpLeft = left;
while(left < right) {
while(left < right && array[right] >= tmp) {
right--;
}
while(left < right && array[left] <= tmp) {
left++;
}
swap(array,left,right);
}
swap(array,tmpLeft,left);
return left;
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
为什么右指针要先走？
答：这里以升序为例：在最后左右指针一定会相遇，然后将 key 的数值于它们对应的数值进行交换，最后要保证 key 左边的数值都要比它小，右边的都要比它大，如果是左指针先走，那就意味着在后面左指针会停下来等右指针过来一起相遇，左指针制作以会停下来是因为它所在的数值大于 key，如果发生交换就无法实现 key 的左边的所有的数值都小于 key .
因此我们要右指针先走，这样在后面，右指针先停下来，并且右指针所对应的数值要小于 key 符合和 key 交换的条件，然后等左指针过来发生相遇即可。
为什么在 while 循环中写这个限制条件？
while(left < right && array[right] >= tmp)
while(left < right && array[left] <= tmp)
答：虽然我们在大循环中加了 left < right ，但是在内部指针自己的循环还是要加上，避免出现 left >= righ
为什么要加等号，是为了避免发生死循环，如下图所示：
没有加等号的循环，在这种情况下就会发生死循环
递归的结束条件是什么？
答：当双指针相遇就结束递归，这是第一个条件，比较容易想到
第二个条件就是左指针大于右指针的时候，也要停止递归，为什么会发生这种情况，因为当进行右边部分的递归的时候，可能会发生左指针大于右指针的情况。
快速排序算法分析
时间复杂度：在最坏的情况下，快速排序递归时是一颗只有右子树或左子树的一颗二叉树，也就是说快速排序排列的数据要么是逆序要么是顺序的情况下就会类似下图的两颗二叉树：
那么此时有n个数据，每次递归双指针需要走 n-2，n - 3 , n - 4 … 可知这是一个等差数列，那么最坏情况下的时间复杂度为O(N^2)
在最好的情况下快速排序的递归应该可以类似一颗满二叉树，树的高度为 log2(N)，每一层双指针大概需要遍历 n 步，最好的情况下的时间复杂度为 O(N*log2(N))
空间复杂度，在最好的情况下为log2(N) 【因为在递归中，先左边递归开辟空间，等左边的递归结束，空间会被回收，然后才会开始右边的递归，所以空间复杂度为二叉树的高度也是递归的深度，而不是二叉树的所有结点！！！】
在最坏的情况下为 O(N)
稳定性：不稳定
挖坑法
我们先将基准值挖走，然后左指针对应的就是一个坑，右指针开始运动，直到遇到比基准值小的数据就将数据覆盖到左指针对应的坑，然后右指针下方局形成一个坑，然后就轮到左指针运动，直到左指针遇到比基准值大数据就会停下，然后将数据覆盖到右指针对应的坑，然后轮到右指针运动，以此类推，最后双指针相遇将基准值覆盖到此就完成了此轮的排序。
下面给大家提供第一轮挖坑法的排序视频，剩下的都是一样的操作，使用递归写代码即可。
快速排序之挖坑法
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
public static void quick(int[] array,int left,int right) {
if(left >= right) {
return;
}
int pivot = partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static int partition(int[] array, int left, int right) {
int key = array[left];
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[left] = array[right];
while(left < right && array[left] <= key) {
left++;
}
array[right] = array[left];
}
array[left] = key;
return left;
}
这里采用的是直接赋值，相比于 Hoare版 ，少使用了交换的代码，在一定程度上提高了代码的效率
一般情况下，我们使用的是挖坑法做题
前后指针法
首先 cur 指针一直都是往前走，现在要思考 prev 什么时候才能往前走
我们先考虑结果，当 prev 走到比 key 大的数值，并且 cur 走到 比 key 小的数值，二者进行交换。
开始时，当 cur 对应的数值小于 key 的时候，prev 也要跟着走，这样可以消除 不符合条件的数值，然后如果 cur 对应的数值大于 key 的话，prev 不需要走，那么这时候prev 前面就是比 key大的数值，这时候要等到cur 运动到比 key 小的数值才能发生交换，cur 还要继续运动，如果有一时刻当 cur 对应的数值小于 key 的时候，prev 就要往前走一步，也就是走到比基准值大的位置，然后进行交换。
本质上，prev 所对应的数值要始终小于 key ，cur 负责遍历完整个数组。
所以最后 prev 所在的位置就是 key 要坐的位置。
快速排序之前后指针法
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if(left >= right) {
return;
}
int pivot = partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static int partition(int[] array, int left, int right) {
int prev = left;
int cur = left + 1;
int key = array[left];
while(cur <= right) {
if(array[cur] < key && array[++prev] != array[cur]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
优化
快速排序的缺点就是一旦数据量过大，递归的深度就会越大，开辟的空间也就越大，很有可能会发生栈溢出，所以要想优化快速排序算法，那么我们应该要想办法减少递归的深度，这时候就有了 三数取中法 和 后面的序列采用直接插入法。
三数取中法
三数取中法就是取三个元素，分别是 left 、right 、(left + right) / 2 所对应的三个元素，进行计较取出它们的中位数作为基准值来开始快速排序
原因：从快速排序的空间复杂度中，我们得知最坏的空间复杂度为 O(N)，是因为这是一颗只有一颗子树的二叉树，最好的空间复杂度为 O(log2(N))，这是一颗满二叉树，也就是要想减少递归的深度，就尽量让快速排序呈现的是一颗饱满的二叉树，所以我们取中位数，也就是让数组切分地更加均匀一些。
此外，取基准值除了上述的三数取中法，还有随机数法，也就是随机取一个数据作为基准值，但是我们一般使用三数取中法，毕竟我们直到三数取中法可以尽量地切分数据，而随机数法具有很多不可空因素和偶然性，所以我们不使用随机数法。
这里要注意分情况讨论：
if 当left 的数值大于 right 的数值的时候
剩下的直接 else
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if(left >= right) {
return;
}
int pivot = partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static int partition(int[] array, int left, int right) {
//三数取中法
getMiddleIndex(array,left,right);
int key = array[left];
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[left] = array[right];
while(left < right && array[left] <= key) {
left++;
}
array[right] = array[left];
}
array[left] = key;
return left;
}
private static void getMiddleIndex(int[] array, int left, int right) {
int leftValue = array[left];
int rightValue = array[right];
int middleIndex = (left + right) / 2;
int middleValue = array[middleIndex];
if(leftValue < rightValue) {
if(middleValue > rightValue) {
swap(array,left,right);
} else if(middleValue < leftValue) {
return;
} else {
swap(array,left,middleIndex);
}
} else {
if(middleValue < rightValue) {
swap(array,left,right);
} else if(middleValue > leftValue) {
return;
} else {
swap(array,left,middleIndex);
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
后面的序列采用直接插入法
直接插入排序的有点是越有序的数据就会排地越快，而快速排序是越排序越有序，我们可以将二者结合起来，就是在快速排序切分为比较小量的数组的时候，可以不用递归了，直接使用直接插入排序以此来减少递归开辟的空间。
下面就是 快速排序优化后的代码，不仅使用三数取中法来是快速排序尽量切分均匀，减少递归深度，最后切分还剩下20个数据的时候使用直接插入法，进一步减少递归的深度！！！
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if(right - left <= 20) {
insertSort(array,left,right);
return;
}
int pivot = partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static void insertSort(int[] array, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = array[i];
int j = i-1;
for (; j >= 0; j--) {
if(array[j] > key) {
array[j+1] = array[j];
} else {
array[j+1] = key;
break;
}
}
array[j+1] = key;
}
}
private static int partition(int[] array, int left, int right) {
//三数取中法
getMiddleIndex(array,left,right);
int key = array[left];
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[left] = array[right];
while(left < right && array[left] <= key) {
left++;
}
array[right] = array[left];
}
array[left] = key;
return left;
}
private static void getMiddleIndex(int[] array, int left, int right) {
int leftValue = array[left];
int rightValue = array[right];
int middleIndex = (left + right) / 2;
int middleValue = array[middleIndex];
if(leftValue < rightValue) {
if(middleValue > rightValue) {
swap(array,left,right);
} else if(middleValue < leftValue) {
return;
} else {
swap(array,left,middleIndex);
}
} else {
if(middleValue < rightValue) {
swap(array,left,right);
} else if(middleValue > leftValue) {
return;
} else {
swap(array,left,middleIndex);
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
非递归
我们可以使用队列或者栈来保存本来要递归的起点与终点，这样就可以通过队列或者栈来模拟递归的过程，做到非递归。
public static void quickSort(int[] array) {
quickNor(array,0,array.length - 1);
}
private static void quickNor(int[] array, int left, int right) {
Queue<Integer> queue = new LinkedList<>();
int pivot = partition(array,left,right);
if(left < pivot-1) {
queue.offer(left);
queue.offer(pivot-1);
}
if(right > pivot+1) {
queue.offer(pivot + 1);
queue.offer(right);
}
while(!queue.isEmpty()) {
int start = queue.poll();
int end = queue.poll();
pivot = partition(array,start,end);
if(start < pivot-1) {
queue.offer(start);
queue.offer(pivot-1);
}
if(end > pivot+1) {
queue.offer(pivot + 1);
queue.offer(end);
}
}
}
private static int partition(int[] array, int left, int right) {
int key = array[left];
while(left < right) {
while (left < right && array[right] >= key) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= key) {
left++;
}
array[right] = array[left];
}
array[left] = key;
return left;
}
经过上面的不断优化，我们可以认为快速排序的时间复杂度为 O(N*log2(N))
归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使
子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
下面是归并排序的视频：
归并排序
递归
先分解后合并，在合并里面是两个有序数组的合并，我们需要
public static void mergeSort(int[] array) {
merge(array,0,array.length-1);
}
private static void merge(int[] array, int start, int end) {
if(start == end) {
return;
}
int mid = (start + end) / 2;
//分解
merge(array,start,mid);
merge(array,mid+1,end);
//合并
merge_sort(array,start,mid,end);
}
private static void merge_sort(int[] array, int start, int mid, int end) {
int[] tmp = new int[end - start +1];
int k = 0;
int s1 = start;
int s2 = mid+1;
int e1 = mid;
int e2 = end;
while(s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
} else {
tmp[k++] = array[s2++];
}
}
while(s1 <= e1) {
tmp[k++] = array[s1++];
}
while(s2 <= e2) {
tmp[k++] = array[s2++];
}
//放回原数组
for (int i = 0; i < k; i++) {
array[i+start] = tmp[i];
}
}
归并排序算法分析
时间复杂度：递归的深度为 log2(N)，二叉树每层需要 遍历一次数组也就是 N ，则 时间复杂度为 O(N*log2(N))
无论数据是有序还是无序的，归并排序都会将其划分为二叉树，因此时间复杂度永远都是 O(N*log2(N))
空间复杂度为 O(N)
归并排序的空间复杂度是这样理解的，首先会在调用合并函数之前就会申请一个大小为 n 的辅助数组，然后才进入归并函数，也就是说在归并排序递归中会申请 log2(N) 的空间，然后有一个辅助数组，所以一共额外开辟了 N + log2(N) 的空间，空间复杂度为O(N) ，这样才是归并排序空间复杂度正确的理解，而上面我的代码是在递归中开辟辅组数组空间所以不好推导，大家按合并函数外的开辟辅组数组空间理解空间复杂度即可。
稳定性：稳定
非递归
归并排序在空间消耗上很大，那我们能不能使用迭代的方法来实现归并排序呢？以此来减少递归产生的空间的消耗。
我们先来看一下递归的函数主体：
我们通过递归将数组划分，然后再调用我们的合并函数，如果要改成非递归的话，就要思考如何通过迭代划分数据，再将 start,mid 与 end 三个下标值传递给合并函数？
分组在第一层，第二层，第三层的递归中，分别是 4个一组，2个一组，1个一组，我们可以在原数组上进行分割，使用 gap 确定间距：
我们的 gap 是 2 倍 2 倍的增长，gap 从 1 开始，也就是两两分组，因为一个一组本身就是有序的，所以从两个两个为一组开始排序，这样才有意义。
gap 从一开始增长，那么合并函数的三个下标的参数应该这样表示 起始下标 start 从 0 开始，mid 等于 start + gap -1， 终止下标 end 等于 mid + gap，这个表示可以以两两一组为例子：
start 下标如何循环？
我们让 start 从 0 开始 循环，然后 start 每次 += gap * 2
循环的终止条件：
gap 要小于数组的长度，因为我们的 end 等于 mid + gap ，所以如果gap 等于数组的长度的话，那么一定会越界！！！
start 也要小于数组的长度，这个好理解，这里不赘述
特殊情况：
上面划分的时候，我们都是均匀的，但是如果数组内部的数据是奇数个的话，那划分就不会均匀：
那么这时候我们在使用 mid = start + gap -1 ,end = mid + gap 的时候就会发生越界
所以这时我们要加上两个判断条件，如果 mid ，end 越界，就将其赋值为 array.length - 1
public static void mergeSortNor(int[] array) {
int gap = 1;
while(gap < array.length) {
for (int i = 0; i < array.length; i += gap * 2) {
int start = i;
int mid = i+gap-1;
if(mid >= array.length) {
mid = array.length-1;
}
int end = mid+gap;
if(end >= array.length) {
end = array.length-1;
}
merge_sort(array,start,mid,end);
}
gap *= 2;
}
}
private static void merge_sort(int[] array, int start, int mid, int end) {
int[] tmp = new int[end - start +1];
int k = 0;
int s1 = start;
int s2 = mid+1;
int e1 = mid;
int e2 = end;
while(s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
} else {
tmp[k++] = array[s2++];
}
}
while(s1 <= e1) {
tmp[k++] = array[s1++];
}
while(s2 <= e2) {
tmp[k++] = array[s2++];
}
//放回原数组
for (int i = 0; i < k; i++) {
array[i+start] = tmp[i];
}
}
这个非递归使用的额外的空间主要是 合并函数使用了辅助数组这一个额外的空间进行排序。
七大排序的总结
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 直接插入排序 | O(N^2) | O(1) | 稳定 |
| 希尔排序 | O(N^ 1.3 ~ N^1.5) | O(1) | 不稳定 |
| 直接选择排序 | O(N^2) | O(1) | 不稳定 |
| 堆排序 | O(N * log(N)) | O(1) | 不稳定 |
| 冒泡排序 | O(N^2) | O(1) | 稳定 |
| 快速排序 | O(N * log(N)) | O(log(N)) | 不稳定 |
| 归并排序 | O(N * log(N) | O(N) | 稳定 |
计数排序
计数排序是非基于比较的排序，计数排序是利用下标来表示原数组的具体的数据，而下标对应是数值则是这个数据会出现多少次。
然后我们使用计数数组将数据一一放回原数组，这样原数组就是有序的~~
开辟多少空间？
我们先在待排序的数组找到最大值和最小值，这样我们就等于找到了数组的数据的范围，我们按照 max - min +1 这个大小来开辟计数数组即可。
从这里也告诉我们计数排序使用的场景是：待排序的数据集中在某一个范围里，数据的取值范围不大且比输入数据的数量小得多。
如何将原始数据一一映射到计数数组中？
原始数据减去在前面获取的最小值就等于计数数组的下标，例如待排序的数组中的最小值为 11 ，然后 其中一个数据为 13 ，那对应的计数数组的下标为 13 - 11 = 2.
如何从计数数组中还原已经排列好的数据？
计数数组的下标 + 最小值 = 真实的数据
public static void countSort(int[] array) {
//找到最大值和最小值然后开辟的数组
int min = array[0];
int max = array[0];
for (int i = 1; i < array.length; i++) {
if(array[i] < min) {
min = array[i];
}
if(array[i] > max) {
max = array[i];
}
}
int[] count = new int[max - min + 1];
//遍历原数组，制作计数数组
for (int i = 0; i < array.length; i++) {
count[array[i] - min]++;
}
int k = 0;
//利用计数数组给原数组进行计数排序
for (int i = 0; i < count.length; i++) {
while(count[i] != 0) {
array[k++] = i + min;
count[i]--;
}
}
}
时间复杂度：O(N + k)
在代码前两个循环中都是遍历数组，所以可以认为是 O(N + N)
k 是计数数组的大小，也就是待排序的数据的取值范围，第三个循环中是遍历计数数组，也就是计数数组的大小 k, 然后由于计数数组有些空间存放的可能是 2 、3等超过 1 的数据，说明这个真实数据出现次数超过 1 次，要等到 所有该真实数据获取之后才能进行计数数组下一个下标的遍历
空间复杂度：O(k)
k 是计数数组的大小。
稳定性：稳定
感谢你的阅读，这里只是介绍了常见的排序算法，还有两个非比较的排序算法没有提到，分别是基数排序和桶排序，大家有兴趣可以自行了解，本文章排序内容到此结束。
原文地址：https://blog.csdn.net/liwuqianhzc/article/details/140588356
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！