c、c++排序的相关知识（归并排序、计数排序、稳定性等）

排序，是对给定的一组数，按照某种逻辑关系，进行位置上的移动。由于排序至少需要将所有数过一遍（正常情况下，非特殊数组），因此排序的时间复杂度一定不能小于O（N）。

归并排序：通过将一个大数据组分割成一个个小数据组，对小数据组排序，排好序后再整体排序。

时间复杂度为O（NlogN），空间复杂度为O（N），其算法最好、最坏情况下时间复杂度均为O（NlogN），是一种十分高效的排序算法，本质上是一种以空间换时间的算法。

void _merge(int* a, int* tmp, int left1, int right1, int left2, int right2)
{    int left = left1;int right = right2;int cur = left1;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){tmp[cur++] = a[left1++];}else{tmp[cur++] = a[left2++];}}while (left1 <= right1){tmp[cur++] = a[left1++];}while (left2 <= right2){tmp[cur++] = a[left2++];}while (left<= right){a[left] = tmp[left];left++;}}void merge(int* a, int* tmp, int left, int right)
{if (left >= right){return;}int mid=(left+right)/2;merge(a, tmp, left, mid);merge(a, tmp, mid + 1, right);_merge(a, tmp, left,mid,mid+1, right);}// 归并排序递归实现
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc");exit(-1);}merge(a, tmp, 0, n-1);free(tmp);}// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc");exit(-1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2*gap){int left1 = i;int right1 = i + gap - 1;int left2 = i + gap;int right2 = i + 2 * gap - 1;if (right1 >= n-1){break;}if (right2 >= n){right2 = n - 1;}_merge(a, tmp, left1, right1, left2, right2);}gap *= 2;}free(tmp);
}

对于递归的算法，就是单纯的不断分割直到只有一个数无法再分割，然后在往回不断归并，结构上类似二叉树的后序遍历。

对于非递归的算法，由于其在逻辑上需要不断进行归并、不断扩大每次归并的数据个数，因此很难通过栈的方式模拟实现，而是选择了用gap当做当前每次归并时一组数的个数，而这里最需要注意的就是数组越界问题，即除了begin1之外的数都有可能会越界，因此需要判断。当begin2>=n的时候，即第二个数不存在，因此不需要归并。当end2>=n的时候，即第二个存在，但大小无法到gap个，此时缩小end2的大小，使得第二组的数据个数为end2-begin2+1个，再与第一组数进行归并。

稳定性：

所谓稳定性，就是指原本相同的数据的相对位置关系，在排序后不发生变化。

常见的排序有冒泡排序、直接插入排序、希尔排序、堆排序、快速排序、归并排序、选择排序。

其中稳定的有冒泡排序、直接插入排序、归并排序

不稳定：

1.希尔排序：原因是在预排序的时候可能同样的数据在不同的组进行排序，导致相对位置变化

2.堆排序：原因是堆排序时要把根节点的元素与最后一个元素互换，导致数据之间的相对位置变化。

3：选择排序：原因是找到最大、最小的元素，将当前最左、最右测的元素与其互换的时候可能会使得位置发生改变。

4：快速排序：每次将最左侧的元素放到最终位置时，可能会导致相对位置改变。