前言
此次的排序均按照升序为例
排序大家都不陌生，生活中处处有排序。什么排名，评分，分数等。这其中最简单的应该就是冒泡排序了，在这里就不多说了。
提示：以下是本篇文章正文内容，下面案例可供参考
一、排序的概念？
排序还有概念？！对的。所谓排序就是给一串数据，按照其中的一个，或多个关键信息的大小，按照递增或递减的方法排列的操作。
二、实现排序
1.插入排序
以升序为例：我们将一个数组里的前两个当作一个区间，每完成一次区间的排序，右区间增大一位。
将一串数组当作区间，从前两个元素开始，当作一个区间，同后面一位的元素进行比较，如果比后面元素大，则进行交互元素，如果小不交换，元素区间向后走一位，直到整个数组成为它的区间，代表排序完成。
排序有两种情况，都在图片中表现出来了 。
// 升序
void insert_sort(int* m, int n)
{for (int i = 1; i < n; i++){
// tmp表示区间的后一个元素，0 - end是排序的区间，所以end的下标要永远比tmp的下标小1int tmp = m[i], end = i - 1;// 将tmp插入到 0~end 区间内while (end >= 0) //这里一定是小于等于，有一种可能是有一位比前面一位都要小{// 上面画的有图，结合一块观看可以有助于理解代码逻辑if (tmp < m[end]){m[end + 1] = m[end];--end;}else{break;}}m[end + 1] = tmp;}for (int i = 0; i < n; i++){printf("%d ", m[i]);}
}
优点：插入排序在元素越接近有序时间越快。
时间复杂度：最好O(N)，最坏：O(N^2)。它比较稳定
2.希尔排序
希尔排序(缩小增量排序)是插入排序的升级版。它由于插入排序元素越是接近有序时间越快。所以先进行gap个间隔的排序。将相对较小的跑前面，相对较大的跑到后面，让它接近有序，最后进行上述的插入排序使它的排序时间变得更快。
希尔排序的基本思想是将待排序的数组元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。对于不同规模的数据，希尔排序都能保持较好的性能。此外在希尔排序中gap的次数没有确定的答案。
我这里采用的是 gap / 2的方式进行递减半的方式按组排序，同时gap > 1 且 gap /= 2在循环里面，那么当gap = 1的时候是最后一轮循环，排序完成。
希尔排序的时间复杂度根据gap来判定通常导致的时间复杂度在O(n^2)和O(nlogn)之间，但更接近于O(n^1.3)到O(n^1.5)之间。
void shell_sort(int* m, int n) //希尔排序
{int gap = n;while (gap > 1){gap /= 2;// gap是多少，就需要排列几组for (int i = 0; i < gap; i++){// 一次gap所以范围内的数进行排序for (int j = i; j < n - gap; j += gap)// for (int j = 0; j < n - gap; j++){int end = j, tmp = m[j + gap];// int end = j, tmp = m[j + gap];// 一次区间进行交互while (end >= 0){if (tmp < m[end]){m[end + gap] = m[end];end -= gap;}else{break;}}m[end + gap] = tmp;}}}for (int i = 0; i < n; i++){printf("%d ", m[i]);}
}
