前言
插入排序一般分为两种，一种直接插入排序，另一种则是希尔排序。
一、直接插入排序
1.简介
直接插入排序是一种简单的排序方法，基本操作就是将需要排序的元素插入到已排好的有序表序列中，从而得到一个完整的序列。 时间复杂度为：O(n²) 空间复杂度：O(1) 稳定性：稳定 生活中最明显的例子就是，打扑克，把牌洗混，然后抓牌，以第一张为基础，然后将后面的牌依次插入，最后得到有顺序的牌面。
2.算法思路
- 将待排的序列看作成2个部分，一部分为有序，另一部分为无序。
- 我们将第一个元素看作有序序列，第二个到最后都是无序序列。
- 将无序序列的每一个元素依次插入到有序序列的合适位置。
讲解：有一个待排序序列：【2,5,8,3】
我们将第一个2看成已经排序好的序列，即有序序列，从第二个元素到最后一个元素看作是无序序列。
待排序元素比有序元素大，则插在有序元素后，反之，插在有序元素前
3.代码实现
#include<stdio.h> #define num 12 void insert_sort(int* a, int n) { for (int i = 0; i < n - 1; ++i) { // 将x插入[0, end]有序区间 int end = i; int x = a[end + 1]; while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; end--; } else break; } a[end + 1] = x; } } int main() { int arr[num] = { 3,1,4,5,2,7,9,0,8,10,11,6 }; printf("\n初始序列\n"); for (int i = 0; i < num; i++) { printf("%d ", arr[i]); } insert_sort(arr, num); printf("\n排序后序列\n"); for (int i = 0; i < num; i++) { printf("%d ", arr[i]); } }
运行结果：
二、希尔排序
1.简介
希尔排序是在直接插入排序的基础上做了较大的改进，是将整个无序序列分割成若干个的子序列分别进行插入排序。
简单而言：将数组预排序，接近有序。
元素为逆排序时，时间复杂度最差为O(n²） 空间最差复杂度: O(n)
平均时间复杂度为O(nlog2n) 平均空间复杂度（O(1)）
稳定性：差
2.算法思路
- 先取一个小于数组数的整数x作为第一个增量，把文件的全部记录分成x个组。
- 所有距离为x的倍数的值在同一组里，然后进行直接插入排序，变成有序序列。
- 取一个小于x的 x1 作为第二个增量，重复上述分组和排序，直到增量为1。
注：当增量为1时，相当于所有记录放在同一组里进行直接插入排序
假设有一组{70，30，40，10，80，20，90，100，75，60，45}无序序列
第一趟：增量gap为3时，即距离为3的元素放在一组，可以分成3组，分别是{70，10，90，60}，{30，80，100，45}，{40，20，75}，按照直接插入排序对每个组进行排序。
第二趟：gap变成了2，接着和第一趟一样，最后也是按照直接插入排序对每个组进行排序。
第三趟：gap为1，后续操作也是如此…
3.代码实现
代码如下：
#include<stdio.h> #define num 12 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < gap; i++) { for (int j = i; j < n - gap; j += gap) { int end = j; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = x; } } } } int main() { int arr[num] = { 3,1,4,5,2,7,9,0,8,10,11,6 }; printf("初始序列:\n"); for (int i = 0; i < num; i++) { printf("%d ", arr[i]); } ShellSort(arr, num); printf("\n排序后序列\n"); for (int i = 0; i < num; i++) { printf("%d ", arr[i]); } }
运行结果：
注：插入排序是排序的开始，各位努力学习的IT人员们，一起加油努力哦。祝各位学业有成，财源滚滚。
---------来自菜鸟TQ02的祝福语
