归并排序
归并过程如下：
代码实现（递归）
//时间复杂度：O(N*logN) //空间复杂度：O(N) 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); }
分析：因为是使用递归实现，开始时需要创建一个新的数组，且递归需要一个区间，因此我们要另外定义一个函数来实现递归。递归的过程跟二叉树的后序遍历类似，应当注意递归的取值范围和结束条件。归并时，我们把左右两个区间的数从头开始比较，小的就放到tmp数组中。第一个while循环的结束条件是直到某一边的数全部放到tmp就结束。然后就把另一个区间的数，全部依次放入tmp数组中，最后再把tmp的数复制给原数组。
代码实现（非递归）
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; //[begin1,end1][begin2,end2]归并 if (end1 >= n || begin2 >= n) { break; } if (end2 >= n) { end2 = n - 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) * (end2 - i + 1)); } gap *= 2; } free(tmp); }
分析：gap表示每组数的个数。非递归的实现是，开始每组一个数，两两合一，后面比较的过程和递归一样。不过需要注意越界的问题，当end1或者begin2>=n时，就已经越界，这时候就结束循环。当只是end2>=n时，前面数据没有越界，只需要把end2改成n-1即可。一趟归并结束后，gap变为2倍，进行后面的归并，直到gap>=n就停止。
计数排序（非比较排序）
代码实现
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) { perror("calloc fail"); return; } //统计次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } //排序 int i = 0; for (int j = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min; } } }
分析：计数排序主要有两步：
1.统计相同元素出现的次数
2.根据统计的结果将序列回收到原来的序列中
计数排序需要我们新创建一个统计数组，按理来说，数组下标就可以用来当作统计的数，该位置就来存放该数出现的次数。但是，如果要排序的数是从一千多开始的，这样前面的空间就全部浪费了。所以我们采用相对映射的方法。即用待排序的数中，最大的数-最小的数+1就可以得到范围，从而减少空间浪费。接着用原数组的数减去最小值，将该值作为count数组的下标，即相对映射。最后进行排序，记得加回最小值min，这样数据才不会被改变。
排序算法的复杂度及稳定性
稳定性：指的是相同的数，在排序之后的相对位置没有改变。
分析：
时间 空间
直接插入：明显的等差数列 无新空间开辟
希尔：前面文章已分析 无
选择：参考动图 无
堆排序：前面文章已分析 无
冒泡：等差数列 无
快排：二分的思维 看递归深度
归并：二分的思维 开辟新的数组
稳定性通过假设来确定，只要有特例是不稳定的，那就是不稳定的。
