前言
生活中处处都有排序，
你去购物网站上筛选物品，有按时间排序，价格排序等等，
而排序也是面试中常考的一个知识点，
今天，我们从插入和希尔排序开始，探索经典排序的奥秘。
1. 插入排序
1.1 介绍
插入排序，顾名思义：
他就像我们平时打扑克牌的时候一样，
从前往后，将小的数拿起，插入到大的数前面（这里默认的是升序）
插入排序就是这样的道理，
我们废话不多说，来讲讲实现的思路：
1. 2 实现思路
想要实现一个排序，我们需要知道
待排序数组的首元素地址，以及该数组的大小。（最基本的）
如图是插排的思路：
遍历数组：
从第二个数开始，一直往前比较，
用tmp先将自己的值保存，
（核心思想）
如果比前面的数小，就将前面的数往后挪动，
直到比前面的数大，就霸占那个因为往后挪动而空出的位置。
1. 3 代码实现
注：a代表的是数组数组首元素地址，n代表的是数组的大小。
//插入排序 InsertSort(int* a, int n) { //遍历数组 for (int i = 1; i < n; i++) { //end位置表示要被比较的数 int end = i - 1; //tmp存放的是正在进行插入排序的数 int tmp = a[i]; while (end >= 0) { //如果tmp比end位置的数小 if (tmp < a[end]) { //就让end位置的数往后挪动 a[end + 1] = a[end]; //再跟前一个end位置的数比较 end--; } else { //如果tmp比end位置的数大，那就别动了 break; } } //将之前因为往后挪动而空出的位置霸占 a[end + 1] = tmp; } }
2. 希尔排序
2. 1 介绍
希尔排序是在插入排序的基础上的，这就是为什么我先讲了插入排序。
插入排序有个特点，就是当排序数组越接近有序，
插入排序的效率就越高，越接近O(N)，
希尔排序通过预排序的手段将数组变得不断接近有序，
最后再进行插入排序。
2. 2 实现思路
预排序就是通过将数组分成几个部分，对他们进行插入排序：
比如说：
我们用gap等于3，将数组分为三个部分：
（三种不同颜色表示那三个部分）
分别是：
9， 6， 3， 0
8， 5， 2
7， 4， 1
对他们分别进行插入排序，也就是预排序，
每次插入就能从一个个比较插入变成跳着比较插入，效率大大提升。
所以：（核心思想）
通过不断进行高效率的预排序，
最后对接近有序的数组进行插入排序，
以提高插入排序的效率，这就是希尔排序。
下面是实现：
2. 3 代码实现
//希尔排序 ShellSort(int* a, int n) { //将gap初始化成数组大小（之后再慢慢让它变小） int gap = n; //当gap == 1，证明已经完成最后一步：插入排序 while (gap > 1) { //不断/2，让gap不断变小进行预排，当gap == 1时进行插入排序 gap /= 2; //这个是将gap分成的每个部分进行插入排序，也就是预排序 for (int i = 0; i < gap; i++) { for (int j = i; j < n - gap; j += gap) { //end位置表示要被比较的数 int end = j; //tmp存放的是正在进行插入排序的数 int tmp = a[end + gap]; //插入排序 while (end >= 0) { //从跳过一个数，变成跳过gap个 if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } }
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
