插入排序

将一元素插入到已排序完毕的数组中

可以将无序数组的第一个元素看作只有一个元素的有序数组

后将数组中的元素一一插入到有序数组中的合适位置

所有元素被插入到有序数组中时，便已将此数组置为有序

动图演示

在这里插入图片描述

代码逻辑如下：

以升序为例

将插入的元素通过 tmp保存

假设此时有序数组中有 i+1 个元素

将有序数组的最后元素（最大的元素）的下标，记为end

通过end遍历数组，寻出元素插入的合适位置

		int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;

将 tmp 与 a[end]进行比较，

当 a[end] > tmp 时，将 a[end]后移一位，后 end--

接着与tmp进行比较，直至找到合适位置

合适位置的两种情况

1. tmp > end

2.tmp小于数组中所有元素

找到合适位置后，循环便结束，将数据存入合适位置（end + 1）

此为一个元素插入到有序数组中的步骤

对 n 个元素的数组进行插入排序可以理解为

含有一个元素的有序数组中插入 n-1个元素

转化成代码即为

// 插入排序
void InsertSort(int* a, int n)
{int i = 0;for(i=0;i<n-1;i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

时间复杂度为 O(N^2)

希尔排序

希尔排序是插入排序的进阶排序，大大优化了插入排序的算法效率

基本思想与代码分析实现

假设数组中共有N个元素

取一小于N的正整数gap

将数组中相距为gap的元素分为一组

注意：各组间元素并不重合，在取元素时，第一组以下标为0的元素为第一个元素

第二种以下标为1的元素为第二个元素

......

将各组元素进行插入排序

        int j = 0;//对每组元素进行排序for (j = 0; j < gap; j++){int i = 0;//对一组元素进行排序for (i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}

后将 gap减小重复上述步骤

以升序为例子

当 gap > 1时

此过程称之为预排序，为了方便更好更快的进行插入排序

gap越大，大的元素就更快到后方，小的元素就更快到前方

gap越小，数据便越接近有序

当gap == 1时

便为插入排序

综上所述

void ShellSort(int* a, int n)
{//按照gap 进行插排int gap = n;while (gap > 1){gap = gap / 3 + 1;int j = 0;for (j = 0; j < gap; j++){int i = j;for (i = 0; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}}