C语言【数据结构】多种排序 实现
目录
1.插入排序
2.希尔排序
二.选择类型的排序
1.选择排序
2.堆排序
三.交换类型的排序
1.冒泡排序
2.快速排序
三数取中优化
①hoare法
②挖坑法
③前后指针法
（1）快速排序（递归版）
（2）快速排序（递归版）（优化：小区间直接插入排序）
（3）快速排序（非递归版）
（4）一种效率很高的快排
四.归并类型的排序
1.归并排序
五.非比较类型的排序
1.计数排序
前言：这里将会实现插入排序、希尔排序，选择排序、堆排序，冒泡排序、快速排序，归并排序和计数排序。
注意：这里的排序都为升序。
一.插入类型的排序 1.插入排序
插入排序主要是要用一个临时变量去记录当前值，并定义一个end遍历，然后和前面的值去比较，如果比前面值小，就让前面的值覆盖该值，然后--end，继续与前面的值比较，如果比前面值大，直接break，然后让这个位置插入这个值。
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];//单趟排序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
2.希尔排序
希尔排序是插入排序的优化版，又叫缩小增量法，采用了预排序进行优化。
先选定一个整数，把待排序文件中所以记录分成几个组，所有距离为gap的记录分在同一个组，并对每一组内的记录进行排序。这里首先让gap = n每次循环让gap = gap / 3 + 1，直到gap = 1的时候，就排好序了。
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此 希尔排序的时间复杂度并不固定，在O(N * logN)左右，大致区间为O(N^1.25)到O(1.6 * N ^ 1.25)
4. 稳定性：不稳定。
二.选择类型的排序 1.选择排序
选择排序就是每次选出一个最小（或最大）的元素，下面这个是最原始的选择排序。
void SelectSort(int* a, int n)
{for (int i = 0; i < n - 1; ++i){int min = i;for (int j = i + 1; j < n; ++j){if (a[j] < a[min]){min = j;}}if (i != min){swap(a[i], a[min]);}}
}下面这个是优化过的选择排序，同时选择最小和最大的元素，分别放在序列的始位置和末位置，循环直到全部排序结束。
void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int mini = left, maxi = left;for (int i = left; i <= right; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left], &a[mini]);if (maxi == left){maxi = mini;}Swap(&a[right], &a[maxi]);++left;--right;}
}直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.堆排序
堆排序我在上一篇有详细的说明：C语言 二叉树实现堆及堆排序_糖果雨滴a的博客-CSDN博客
这里简单说一下：堆排序就是用树这种结构设计出的排序，排升序建大堆，排降序用小堆。
