目录
一、计数排序
二、快速排序
三、归并排序
四、八大排序时间复杂度及其稳定性
一、计数排序
计数排序是一个非基于比较的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。是一种以空间换时间的行为。
其是实现过程可用以下动图来展示：
实现思路：
1. 该排序适用于该数组极值相差不大的情景，所以，我们可求得其范围进行创建数组辅助排序。
2. 我们可求得该数组的最大和最小值，我们可采取映射思想，进行遍历明白各个数在新数组的相对位置。
3. 将待排序集合每一个元素移动到计算得出的正确位置上。
代码实现：
void CountSort(int* a, int n)
{int max = a[0];int min = a[0];for (int i = 1; i < n; i++){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}//求范围int range = max - min + 1;int* tmp = (int*)calloc(range,sizeof(int));if (tmp == NULL){perror("calloc fail");return;}//映射位置for (int i = 0; i < n; i++){tmp[a[i] - min]++;}//进行排序int j = 0;for (int i = 0; i < range; i++){while (tmp[i]--){a[j++] = i + min;}}free(tmp);tmp = NULL;
}易错点：
再最后排序时，一定要加的是 + min，如果加的为 tmp[i] 会导致出现问题，其原因为：tmp[i]，在不断的变化，会导致排序出错。
局限性：
- 该排序排序极值不能过大，否则会导致资源浪费。
- 只能排整数。
二、快速排序
快排的具体实现前文已经详细讲述，详情可见：深入理解并实现——快排【C语言版】-CSDN博客此处便不在赘述，以下为hoare版本实现：
int Hoare(int* a, int left,int right)
{int k = left;int begin = left;int end = right;while (begin < end){while (begin < end && a[k] < a[end]) //这里等号可加可不加{end--;}while (begin < end && a[k] > a[begin]) {begin++;}swap(&a[begin], &a[end]);}swap(&a[begin], &a[k]);return begin;
}void QuickSort(int* a, int left,int right)
{if (left >= right) //递归结束条件判断{ //当左边与右边相等时，不用进行任何处理return;}int k = Hoare(a, left, right);QuickSort(a, left, k - 1);QuickSort(a, k + 1, right); //区间为：左闭右开
}三、归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
具体讲解可见：深入理解并实现——归并排序【C语言】-CSDN博客
以下为代码实现：
void _MergeSort(int* a, int* tmp, int left, int right)
{if (left >= right){return;}int mid = (left + right) / 2;// 如果[begin, mid][mid+1, end]有序就可以进行归并了_MergeSort(a, tmp, left, mid);_MergeSort(a, tmp, mid + 1, right);//归并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left;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 + left, tmp + left, sizeof(int) * (right - left + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}四、八大排序时间复杂度及其稳定性
一图以蔽之：
排序稳定性：
在排序算法中，如果有两个相等元素的顺序在排序之前是一样的，那么排序之后它们的顺序是否保持不变。一个稳定的排序算法会保持相等元素的相对顺序不变，而一个不稳定的排序算法则可能会改变相等元素的相对顺序。
对于稳定性，大家可结合以下口诀进行记忆：
考研很辛苦，心情不稳定。快（快排）些（希尔）选（选择）一堆（堆排）朋友去干饭（干啥都行）。
时间复杂度：
对于时间复杂度可结合一下口诀进行记忆：
快 些(希) 以（O(nlog2)） 归 队，最坏情况下 快 些（希） 退化成O(n2)。
排序上链接：数据结构——排序【上】-CSDN博客
完！