插入排序与希尔排序

个人主页：Lei宝啊

愿所有美好如期而遇

---

前言：

这两个排序在思路上有些相似，所以有人觉得插入排序和希尔排序差别不大，事实上，他们之间的差别不小，插入排序只是希尔排序的最后一步。

---

目录

前言：

插入排序：

思路：

图解：

代码：

希尔排序：

思路：

图解：

代码：

---

插入排序：

思路：

当我们有了一个有序的数组arr，假设为升序，现在向里面插入一个新数据。

我们假设这个数组有n个元素，最后一个元素的下标我们记作end，那么要插入的这个数下标为end+1,并用tmp记下这个数的大小。

接下来，如果tmp小于arr[end],那么arr[end+1] = arr[end];  end--,

              如果tmp大于等于arr[end],那么break;   arr[end+1] = tmp;  

重复上述操作，直到end < 0或者break跳出

---

那么面对一个无序的数组，我们可以将第一个元素当做有序，第二个元素为新插入元素，依次类推排序

图解：

代码：

void InsertSort(int* arr, int n)
{//i == n - 2时，temp = arr[n - 1];for (int i = 0; i < n - 1; i++){int end = i;int temp = arr[end + 1];//此处画个图，end小于0跳出循环while (end >= 0){if (temp < arr[end]){//插入的值比end小，end值向后移动一位arr[end + 1] = arr[end];end--;}else{break;}}//写在循环外的原因是如果while循环不是break出来的//会导致第一个元素值重复，插入的值最后未插入进去arr[end + 1] = temp;}}

---

希尔排序：

思路：

希尔排序比插入排序多的就是预排序，而预排序的目的就是让大的数据/小的数据更快的被排到后面去，因为越接近有序的数据，使用插入排序时时间复杂度越接近O(N),而我们的希尔排序最后一步等同于插入排序

图解：

以代码一为例：

代码：

两个代码没有什么差别，只是一个是一组一组排，一个是并排。

代码一：

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//多组预排序，最后接近有序时插入排序gap /= 2;//完成一趟预排序for (int j = 0; j < gap; j++){//完成一组预排序for (int i = j; i < n - gap; i += gap){//走一组中的一个位置的预排序int end = i;int temp = arr[end + gap];while (end >= 0){if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;}}}}

代码二：

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//多组预排序，最后接近有序时插入排序gap /= 2;//等同于上面的希尔排序,不是分组排了，而是并排for (int i = 0; i < n - gap; i++){//走一组中的一个位置的预排序int end = i;int temp = arr[end + gap];while (end >= 0){if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;}	}
}

---