非递归
大体思路是没变的，还是需要靠新的数组，不过非递归的细节会非常的复杂：
核心思路还是两两一组，只不过是从原数组中直接去找单个元素排序，然后形成新的一组，再将新的组进行排序。（其实和希尔排序有点类似，这里的gap是一组中的元素个数）。
我们先对于上面这组数进行代码实现：
#include <stdio.h> #include <stdlib.h> #include <string.h> void MergeSortNonR(int* a, int start, int n)//创建新数组 { int* tmp = (int*)malloc(sizeof(int) * (n)); if (tmp == NULL) { perror("malloc error"); exit(-1); } for (int gap = 1; gap < n; gap = 2 * gap)//一组多少个元素 { for (int j = 0; j < n; j += 2 * gap)//j是每组的开头 { int i = j;//新数组的下标 int left1 = j;//第一组开始 int right1 = j + gap - 1;//第一组结束 int left2 = j + gap;//第二组开始 int right2 = j + 2 * gap - 1;//第二组结束 while (left1 <= right1 && left2 <= right2)//尾插进新的数组 { if (a[left1] <= a[left2]) { tmp[i++] = a[left1++]; } else { tmp[i++] = a[left2++]; } } while (left1 <= right1)//哪组没走完继续走 { tmp[i++] = a[left1++]; } while (left2 <= right2) { tmp[i++] = a[left2++]; } memcpy(a + j, tmp + j, sizeof(int) * (right2 - j + 1));//将新数组的内容拷贝到原数组 } } free(tmp); tmp = NULL; } int main() { int arr[] = { 6,2,7,1,3,4,10,8 }; int n = sizeof(arr) / sizeof(arr[0]); MergeSortNonR(arr, 0, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
这组数非常顺利，但是我们发现，这组数是可以一直被平分成两组的，如果是奇数呢？或者是10个数呢？
这时候就会出现这种情况 ，只要不是2N就不能向上面那样解决了，肯定会有分不到的组。
那么我们可以让5和9组成的这组先等下，等前面四组排序组成新的一组时就可以变成两组排序了。
像这样就可以了，实现这个逻辑就去判断分组的时候是否下标越界。
我们也发现了一个规律，如果第一组的left1没有遇到任何数则不会有后面的数，只有left1遇到了一个数，比如这组的5（假设right1没遇到9），这才说明这组不能像之前的代码一样去解决问题，因为在第一次进行分组的时候5就不会被分配到任何一组。
分组不均匀的三种情况是：
第一组中右区间缺失
第一组无缺失，第二组全缺失
第二组右区间缺失
但是这里要注意一下，两组中只要有数据就会合成一组，并不是每组都一样的数量才会合成一组。
所以在判断第三组的右区间越界的时候不能直接跳出，需要修正区间。
代码实现：
#include <stdio.h> #include <stdlib.h> #include <string.h> void MergeSortNonR(int* a, int start, int n)//创建新数组 { int* tmp = (int*)malloc(sizeof(int) * (n)); if (tmp == NULL) { perror("malloc error"); exit(-1); } for (int gap = 1; gap < n; gap = 2 * gap)//一组多少个元素 { for (int j = 0; j < n; j += 2 * gap)//j是每组的开头 { int i = j;//新数组的下标 int left1 = j;//第一组开始 int right1 = j + gap - 1;//第一组结束 int left2 = j + gap;//第二组开始 int right2 = j + 2 * gap - 1;//第二组结束 if (right1 >= n)//第一组右区间越界 { break;//跳出去原来的组会被放在tmp数组中 } if (left2 >= n)//第二组全越界 { break; } if (right2 >= n)//第二组右区间越界 { right2 = n - 1;//修正 } while (left1 <= right1 && left2 <= right2)//尾插进新的数组 { if (a[left1] <= a[left2]) { tmp[i++] = a[left1++]; } else { tmp[i++] = a[left2++]; } } while (left1 <= right1)//哪组没走完继续走 { tmp[i++] = a[left1++]; } while (left2 <= right2) { tmp[i++] = a[left2++]; } memcpy(a + j, tmp + j, sizeof(int) * (right2 - j + 1));//将新数组的内容拷贝到原数组 } } free(tmp); tmp = NULL; } int main() { int arr[] = { 6,2,7,1,3,4,10,8,5,9 }; int n = sizeof(arr) / sizeof(arr[0]); MergeSortNonR(arr, 0, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
非比较排序
计数排序
基本思想：
就像哈希表一样，用一个数组来映射另一个数组。
先找原数组最小的值和最大的值，因为创建一个新数组要和原数组最小与最大的差值一样大。
创建好一个数组之后，我们将原数组映射到新数组下标对应的位置：
最小的映射在下标为0的位置，第二小的映射在减去最小值下标的位置。
最后在映射的地方进行++，映射几次就加几次：
最后我们利用新建数组进行排序，下标加上最小值，从下标为0的地方开始，没有就不放回原数组：
代码实现
#include <stdio.h> #include <stdlib.h> void countingsort(int* a,int n) { int max = a[0];//假设最大最和小值在下标为0的位置 int min = a[0]; for (int i = 0; i < n; i++)//在原数组中找最大的 { if (max < a[i]) { max = a[i]; } } for (int i = 0; i < n; i++)//在原数组中找最小的 { if (min > a[i]) { min = a[i]; } } int sum = abs(min) + abs(max) + 1;//新数组的长度 int* tmp = (int*)malloc(sum * sizeof(int));//开辟新数组 if (tmp == NULL) { perror("malloc error"); exit(-1); } for (int i = 0; i < sum; i++) { tmp[i] = 0;// 新数组的初始化 } for (int i = 0; i < n; i++)//映射到新数组 { if (a[i] == min) { tmp[0]++; } else if (a[i] > min) { int x = a[i] - min; tmp[x]++; } } int j = 0;//原数组下标 for (int i = 0; i < sum; i++) { while (tmp[i]--) { a[j] = i + min;//新建数组映射到原数组 j++; } } free(tmp); tmp == NULL; } int main() { int arr[] = { -1,-5,3,7,7,5,-1,3 }; int n = sizeof(arr) / sizeof(arr[0]); countingsort(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
时间复杂度：O(N+sum)
空间复杂度：O(sum)
稳定性：稳定
缺点：只能对整形排序
排序的复杂度与稳定性
什么是稳定性
上面除了计数排序，剩下的都是可以针对自定义类型进行排序的，我举个例子：
排序前红色的5在黑色的5前面，黑色的1在红色的1前面，排序后红黑颠倒了，这就是不稳定，如果是整数确实没什么，如果是自定义类型就麻烦了，红色的1中可能会有其他的成员变量，黑色的也有其他不同的成员变量。
比如高考的时候，全国有很多分数相同的同学，但是我想先看谁语文分数高，然后在进行总分的排序，如果用一个稳定的排序就不会打乱原来的排序。
直接插入排序
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：稳定
在排序的过程中遇到相同的数就会停下。
希尔排序
时间复杂度：O(N1.3)
空间复杂度：O(1)
稳定性：不稳定
分组的时候容易将相同的数据分到不同的组。
选择排序
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：不稳定
蓝色的5和黑色的5顺序没变，但是蓝色的8和黑色的8顺序变了。
堆排序
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
这个太不稳定了。
冒泡排序
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：稳定
快速排序
时间复杂度：O(N*logN) 优化后的
空间复杂度：O(logN) 取决于树的深度
稳定性：不稳定
归并排序
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
在排序的过程中是尾插进新数组的，遇到相同的就尾插到后面，非常稳定。
