1.计数排序
计数排序是一种非比较排序算法，其核心思想是通过统计每个元素出现的次数，然后根据统计结果将元素按照顺序放置在输出数组中。
以下是计数排序的逻辑思想（C语言版）：
1. 首先，遍历待排序的数组，找到数组中的最大值max，确定计数数组的大小为max+1。
2. 创建一个大小为max+1的计数数组count，并初始化为0。
3. 遍历待排序的数组，将每个元素的值作为计数数组count的索引，并将对应索引位置的值
加1，表示该元素出现的次数。
4. 对计数数组count进行累加操作，使得每个索引位置的值表示小于等于该索引的元素个数。
5. 统计完次数之后就往原数组内覆盖回写
计数排序是一种就地排序算法，这意味着它不需要任何额外的空间来对数据进行排序。它也是一个稳定的排序算法，这意味着输入中相等元素的顺序在输出中得以保留。
计数排序是一种十分高效的排序，时间复杂度为O(n + k)，其中n是列表中元素的数量，k是列表中任何元素的最大值。计数排序的空间复杂度为O(k)。
计数排序是不适合分散的数据，更适合集中的数据；不适合浮点数，字符串，结构体数据排序，只适合整数。
eg：如果有一组数据是从1000开始的连续的数据，那么是不是就意味着前面1000个空间就浪费了，如何解决？
我是数据是多少就映射到哪个位置上，这种映射叫做绝对映射，这可能会导致大量空间的浪费，大多情况下我们都是使用相对映射的方法。（相对最小值）我们在使用计数排序前，可以先找到改组数据的最小值和最大值，这就是该组数据的范围，这样就可以有效的节省空间了。
代码：
// 计数排序 // 时间：O(N+range) // 空间：O(range) void CountSort(int* a, int n) { int min = a[0], max = a[0]; //确定范围 for (int i = 1; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } int range = max - min + 1; int* count = (int*)calloc(range, sizeof(int)); if (count == NULL) { printf("calloc fail\n"); return; } // 统计次数 for (int i = 0; i < n; i++) { count[a[i] - min]++;//使得下标从0开始 } // 排序 int i = 0; for (int j = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min;//回到原数组范围 } } }
2.归并排序
递归版本基本思想：归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：它将待排序的数组递归地分成两个子数组，然后对这两个子数组分别进行排序，最后将两个有序的子数组合并成一个有序的数组。
递归版本的归并排序的具体步骤如下：
1. 将待排序的数组分成两个子数组，每个子数组的大小为 n/2。
2. 对这两个子数组分别进行递归排序。
3. 将两个有序的子数组合并成一个有序的数组。
合并两个有序的子数组可以通过以下步骤实现：
1. 创建一个新的数组，用于存储合并后的结果。
2. 将两个子数组中的元素依次比较，将较小的元素放入新的数组中。
3. 重复步骤 2，直到两个子数组中的所有元素都被放入新的数组中。
下面是归并排序的递归版本的算法步骤：
1. **分解**：将待排序的数组分成两个子数组，通过计算数组的中间位置来实现。可以使用递归将左右两个子数组继续分解，直到子数组的大小为1。
2. **排序**：对分解得到的子数组进行排序，可以通过递归调用归并排序函数来实现。
3. **合并**：将排序好的两个子数组合并成一个有序的数组。比较两个子数组的第一个元素，将较小的元素放入结果数组中，并将相应子数组的指针向后移动，重复这个过程直到其中一个子数组为空，然后将另一个子数组中剩余的元素直接放入结果数组中。
递归版本的归并排序的关键在于递归地将数组分解为较小的子数组，并在合并阶段将它们逐步合并成一个有序的数组。这个过程会一直递归下去，直到子数组的大小为1，即只有一个元素，此时可以认为它已经是有序的。
下面归并排序递归版本的实现代码：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 2; // [begin, mid][mid+1, end] _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid+1, end, tmp); // [begin, mid][mid+1, end]归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while(begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } _MergeSort(a, 0, n - 1, tmp); free(tmp); }
非递归版本
递归的思想是把数组分到一个数据认为它有序，然后才开始归并。非递归的思想就是可以一开始就是认为单个数据有序，开分组归并。
这里我们引出gap变量，gap表示每组的数据个数
我们还是通过划分区间的方法来理清逻辑，[begin1,end1] [begin2,end2]两组一归并。
end1为什么是i+gap-1？因为我们访问的是下标，所有我们要减去1
int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1;该如何控制gap？
gap的变化趋势是每次扩大2倍，gap*=2。只要gap<n，那么循环就继续。
该怎么去控制归并循环？
首先i+=2*gap，因为每次要跳过两组数据，那么i的结束条件就可以是i<n
注意：没归并完一组就将这组的数据拷贝回原数组，而不是将所有组归并完后，再将整个数组拷贝回原数组。（稍后解释原因）。初步代码：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { for (int i= 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; int j = begin1; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } memcpy(a + i, tmp + i, sizeof(int) * 2*gap); } printf("\n"); gap *= 2; } free(tmp); } int main() { int a[8] = { 8,7,6,5,4,3,2,1 }; MergeSortNonR(a, 8); for (int i = 0; i < 8; i++) { printf("%d ", a[i] ); } }运行结果：
但我们的数组个数不是2^n时，排序就出现错误了，这是为什么呢？
我们通过打印每组gap的分组情况发现gap为2，4，8时，都出现了越界情况，我们并没有那么多数据，因为我们都是按整数倍去算的，每次都会为我你们补齐，如何解决？
我们先看begin1，begin1是i，它不可能越界，其它的都可能越界。
如果end1越界， 那么证明后面就没有数据，就不需要越界了，接直接break。
如果begin2越界了，end2，那也可以证明后面没有数据了，直接break。
如果end2越界了，那么证明前面都是好的，end2是补齐到了整数倍所以导致越界了，那么只要将end2修正到n就好了。
这里的拷贝也是要进行修改的，因为拷贝也是按照整数倍去拷贝的，要改成（end2-i+1）左闭右闭，减完后要加1。
修改后的代码：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { //printf("gap:%2d->", gap); for (size_t i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // [begin1, end1][begin2, end2] 归并 //printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2); // 边界的处理 if (end1 >= n || begin2 >= n) { break; } if (end2 >= n) { end2 = n - 1; } //printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2); int j = begin1; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1)); } printf("\n"); gap *= 2; } free(tmp); }运行结果：
填前面的坑：为什么要归并一组拷贝一组，而不是等拷贝完了，拷贝整个数组？
因为会出现越界的情况，当遇到越界的情况，因为只有一组已经是有序的了，直接break就好了，就不需要进入tmp数组了，如果break了，却又整组的进行迭代数据，那么在最后一组的位置进入tmp数组就有可能出现随机值，再拷贝回原数组那么就会把最后一组正确的数据给覆盖掉了。
