目录

前言

1. 插入排序

1.1 介绍

1. 2 实现思路

1. 3 代码实现

2. 希尔排序

2. 1 介绍

2. 2 实现思路

2. 3 代码实现

写在最后：

前言

生活中处处都有排序，

你去购物网站上筛选物品，有按时间排序，价格排序等等，

而排序也是面试中常考的一个知识点，

今天，我们从插入和希尔排序开始，探索经典排序的奥秘。

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;}}}
}

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。