插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个 已经排好序的有序序列 中，直到所有的记录插入完为止，得到一个新的有序序列 。

void insertsort(int* arr,int n) {for (int i = 0; i < n - 1; i++){//单趟排序int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end+1] = arr[end];end--;}else break;}arr[end+1] = tmp;}
}

插入排序的最坏的情况为，数组与我们需要排序的目标相悖。比如我们需要排升序，但是原始序列为降序 。为最坏情况，为 O ( N^2 ) 如果目的是升序，序列也正好是升序的话，为最好情况，这时时间复杂度为 O ( N )

取其最坏，最终时间复杂度：O ( N ^2 )

插入排序并没有开辟额外空间，所以 空间复杂度：O ( 1 )

希尔排序

取一个整数，作为 间距gap ，对于每个元素，与其间隔为gap 的元素分成一个组，对每组排序 。不断调整 gap ，对每组进行不断排序，在gap 调整到 1 后进行插入排序，就可以将数据排成有序。而按照间距 gap 分组并排序被称为 预排序 。

数据被分为 gap 组，每组有 N / g a p N / gapN/gap 个数据。那么对于那么对于单组，最坏的挪动次数就是1 + 2 + 3 + . . . + N / g a p − 1 \\color{blue}1 + 2 + 3 + … + N/gap - 11+2+3+…+N/gap−1 ，是公差为 1 11 的等差数列。

一共有 gap 组，那么对于一次预排序的总次数就为 ( 1 + 2 + 3 + . . . + N / g a p − 1 ) × g a p \\color{blue}(1 + 2 + 3 + … + N/gap - 1) \\times gap(1+2+3+…+N/gap−1)×gap ，但是这里 gap 是不确定的，是不好算的。

既然这样，我们就换个角度来看，对于每次预排序的时间复杂度，该怎么计算：

假设 g a p gapgap 每次除以 3 33 ，一开始 N NN 很大，g a p = N / 3 + 1 gap = N / 3 + 1gap=N/3+1 ，将当前 gap 的取值带入上方对于一次预排序的次数的公式中， ( 1 + 2 + 3 + . . . + N N / 3 + 1 − 1 ) × ( N / 3 + 1 ) ≈ N \\color{blue}(1 + 2 + 3 + … + \\frac{N}{N / 3 + 1} - 1) \\times (N/3 + 1) \\approx N(1+2+3+…+
N/3+1
N
​
−1)×(N/3+1)≈N ，那么起始处， 预排总次数约为 N 。

… … …

快结束时，gap 很小，这时次数也约为 N ，因为此刻由于预排序的作用 ，数组几乎有序，几乎不需要排序，遍历一遍大约就可以求出！！！

而中间的结果我们先忽略，就看起始两次，我们将其认为对于每次预排序，时间复杂度为O(N) 。

法一：

void shellsort(int* arr, int n) {int gap=3;for (int a = 0; a < gap; a++){for (int i = 0; i < n - gap; i += gap){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else break;}arr[end + gap] = tmp;}}for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else break;}arr[end + 1] = tmp;}
}

法二：

while (gap > 1)
{gap = gap / 3 + 1; // 或 gap /= 2;// gap 组并排for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}