目录

一.插入排序

1.实现

2.时间复杂度

二.希尔排序

2.预排序

(1).单次预排序的实现

(2).相对有序

2.代码

一.插入排序

1.实现

正如其名，是将第n+1个数据插入到前面的n的升序（降序）数据中，形成一个n+1大小的升序（降序）序列。

由于前面的n个数据为升序，那么我们只需要将第n+1个数据依次与前n个进行比较，当比他小时便可以停止比较进行插入，无须继续与前面的数据比较。

void Swap(int* m, int* n)
{int mid = *m;*m = *n;*n = mid;
}

for (int j = n; j > 0; j--)
{if (a[j] < a[j - 1])Swap(&a[j], &a[j - 1]);elsebreak;
}

那么，若是想要完成一段无序数组的排序，我们只需要从第二个元素开始进行插入即可（第一个元素本身就是有序的）。

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){for (int j = i; j > 0; j--){if (a[j + 1] < a[j])Swap(&a[j], &a[j + 1]);elsebreak;}}
}

2.时间复杂度

当每一次排序都需要末尾元素与前面每一个元素进行比较时，时间复杂度最大，精确为2+3+4+5+...+n，所以最差时间复杂度为O(N^2)。

但当这个数组本身就为有序，那么这时时间复杂度最佳为O(N)（因为即使有序，我们也要遍历一遍来比较一次）。

同时，我们也可以得知，当数组接近有序时，时间复杂度会降低。

二.希尔排序

希尔排序，便是由希尔这个人提出来的，其实是插入排序的一种优化。

在上面，我们得知，当数组接近有序时，时间复杂度会降低。而这种排序，是在进行插入排序之前，通过预排序将数组变得接近有序。

2.预排序

那么什么是预排序呢？

预排序是将间隔为gap的元素分为gap组，分别进行插入排序，从而使整个数组变得相对有序。

(1).单次预排序的实现

例如我们令gap=3

 这样，我们便将这组数据分为了三组

其中每一组的排序和插入排序类似

for (int i = 0; i < n - gap; i += gap)
{for (int j = i; j >= 0; j -= gap){if (a[j + gap] < a[j])Swap(&a[j], &a[j + gap]);elsebreak;}
}

之后我们队每一组数据来进行排序

第一组

第二组

第三组

for(int k = 0; k < gap; k++)
{for (int i = k; i < n-gap; i+=gap){for (int j = i; j >= 0; j-=gap){if (a[j + gap] < a[j])Swap(&a[j], &a[j + gap]);elsebreak;}}   
}

 当然，我们没有必要真的在代码中将其分为三部分来排序，我们只需要将每一个数据与前面间隔gap的一些数据比较即可

for (int i = 0; i < n - gap; i++)
{for (int j = i; j >= 0; j-=gap){if (a[j + gap] < a[j])Swap(&a[j], &a[j + gap]);elsebreak;}
}   

如此，我们便能实现一次预排序。

(2).相对有序

在预排序过后，整个数组会变得相对有序

那么gap为多少时更加有序呢？

这个很容易得知，gap越大，更加相对无序，而gap越小，就更加相对有序，当gap为1时，便直接成为插入排序

因此，我们可以进行多次预排序（gap由大到小），最后进行插入排序（gap=1）

而这个gap的值，我们可以定为 n / 2，而为了进行多次预排序，我们可以每次使 gap/=2（gap/=3+1）,这样也会使得最终gap为1，从而进行插入排序。

2.代码

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap /= 2;for (int i = 0; i < n - gap; i++){for (int j = i; j >= 0; j-=gap){if (a[j + gap] < a[j])Swap(&a[j], &a[j + gap]);elsebreak;}}   }
}