本篇博文旨在介绍排序算法中的插入排序；介绍了直接插入排序和希尔排序，并通过时间复杂度和空间复杂度进行了分析；最后用代码实现了直接插入排序和希尔排序

直接插入排序

基本思想

1、将数组分成有序和无序的两块区间，有序区间开始只划分数组的第一个元素

2、从无序区间的第一个数，找到合适的位置插入到有序的数组中

图解

时间复杂度和空间复杂度

在最好的情况下，已经有序，只需要比较n-1次

在最坏的情况下，数组全为逆序，一共需要比较 (n-1)+(n-2)+...+1是一个等差数列；是一个N方级别的算法

时间复杂度为O(N* N)

所以直接插入排序不适合数据量比较大的排序算法，因为每次挪动元素的代价是很大的

直接插入排序只占用了有限个数据存储空间，时间复杂度为O(1)

直接插入排序的优缺点

优点：元素少的时候，效率很高；即使完全逆序，但在当今计算机速度的快速发展下，并不是问题

缺点：在元素多的时候，需要挪动狠多元素，并且在逆序或者接近逆序的情况下，效率很差

直接插入排序的代码实现

#pragma once #include<iostream> using namespace std; #include<assert.h> void Print(int* a,size_t n) { assert(a); for (size_t i = 0; i < n; ++i) { cout << a[i] << " "; } cout << endl; } //插入排序 //时间复杂度:O(N* N) //思想: //从数组的首元素开始，第一次排前两个数，第二次排前三个数...以此论推 //保证前面拍的元素有序的情况下，再拍后一个元素时，可以依次比较找到适合的插入位置 //最优情况下，插入排序的时间复杂度为O(N) //最坏情况下，也就是逆序的排序时间复杂度为O(N* N) // // [0,i] void InsertSort(int* a, size_t n) { assert(a); //第一次排前两个数，第二次排前三个... for (size_t i = 1; i < n; ++i) { int end = i - 1;//end表示最后一个数的前一个数 int tmp = a[i]; while (end >= 0) { //是否是合适的位置，不是的话覆盖 //是的话break跳出 if (tmp >= a[end]) break; a[end + 1] = a[end]; end--; } //可能是break跳出，在中部找到合适的位置 //也可能是end == -1，while循环结束，需要放在第一个元素 a[end + 1] = tmp; } } void TestInsertSort() { int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 }; InsertSort(a, sizeof(a) / sizeof(a[0])); Print(a, sizeof(a) / sizeof(a[0])); }

希尔排序

希尔排序是对插入排序的一种优化

由于插入排序在逆序或者接近逆序的情况下，需要挪动较多的次数才能将数组中小的元素挪到前面

希尔排序的是在直接插入排序之前先进行预排序，将较小的元素快速的诺到前面

基本思想

1、希尔排序是先把元素进行分组，每一组的每一个元素之间的间隙相等

2、对这些组分别进行直接插入排序

3、将间隙缩小

4、重复第2、第3步骤，直到间隙值为1时，进行最后一趟直接插入排序

图解

希尔排序的时间复杂度和空间复杂度

希尔排序在有序的情况下也要比较N-1次

在逆序或者接近逆序的情况下能比直接插入排序的效率高

所以 O(N)<希尔排序的时间复杂度<O(N*N)

我们认为希尔排序的时间复杂度在N^1.25~1.6N*1.25之间

由于其占用的也是有限的数组空间，空间复杂度为O(1)

希尔排序的优缺点

优点：解决了直接插入排序在元素较多、接近逆序的情况下需要挪动较多次数的尴尬

缺点：在元素多的时候，往往我们用快速排序等效率更高的排序；所以希尔排序还是处于一个非常尴尬的位置

希尔排序的代码实现

#pragma once #include<iostream> using namespace std; #include<assert.h> void Print(int* a,size_t n) { assert(a); for (size_t i = 0; i < n; ++i) { cout << a[i] << " "; } cout << endl; } //希尔排序 //时间复杂度：O(N* N) //思想: //将数组分成gap组，然后分组用插入排序 //当gap为1时，就是进行直接插入排序 //希尔排序在逆序或者接近逆序时，会提高插入排序的效率 //将大的元素移到前面的位置花费的次数大大减少 void ShellSort(int* a, size_t n) { assert(a); size_t gap = n; //while循环控制着多次插入排序 while (gap > 1) { //该公式可以保证最后一趟排序的gap为1 gap = gap / 3 + 1; //从第一组的第二个元素开始，多组循环进行直接插入排序 for (size_t i = gap; i < n; ++i) { int end = i - gap; int tmp = a[i]; //进行插入排序，每一组的差值为gap //从后向前，每组第一个元素的前一个值一定小于0 while (end >= 0) { //如果tmp不比前面大，则找到tmp的插入位置，break跳出 //否则，end元素进行单组的后移 if (a[end] <= tmp) break; a[end + gap] = a[end]; end -= gap; } //进行插入 a[end + gap] = tmp; } } } void TestShellSort() { int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 }; ShellSort(a, sizeof(a) / sizeof(a[0])); Print(a, sizeof(a) / sizeof(a[0])); }

小结

希尔排序在序列接近逆序会通过减少换移动的次数从而提高插入排序的效率

但是当元素少时，由于数据少，插入排序并不会比希尔排序多换几次位置

当元素很多时，很多情况用的是快排和堆排

所以希尔排序是一个不常用排序

而直接插入排序在元素少的时候非常的适用