1.插入排序

1.1. 直接插入排序

直接插入排序是一种简单的插入排序；
**主要思想：**将待排序的数据，就一个一个的数据插入到一个有序的序列中，并保持插入之后还是有序的。
【第一步：将一个数据插入到一个有序的序列中】

	int end;//有序序列最后一个数据的位置int tmp=a[end+1];//保存要插入的数据,将end后面的一个数据插入while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];//将数据后移end--;}else{break;}}a[end + 1] = tmp;//找要从插入数据的位置，将数据插入到end后一个位置

【第二步：将数组的第一个元素看成是一个有序的序列，将剩下的一个一个元素插入这个有序序列中。用循环即可实现】

void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end=i-1;//有序序列最后一个数据的位置int tmp = a[end + 1];//保存要插入的数据,将end后面的一个数据插入while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];//将数据后移end--;}else{break;}}a[end + 1] = tmp;//找要从插入数据的位置，将数据插入到end后一个位置}
}

【代码实现】

void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end=i-1;//有序序列最后一个数据的位置int tmp = a[end + 1];//保存要插入的数据,将end后面的一个数据插入while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];//将数据后移end--;}else{break;}}a[end + 1] = tmp;//找要从插入数据的位置，将数据插入到end后一个位置}
}

1.2.希尔排序（缩小量排序）

主要思想：
1.预排序：先将一个序列变成一个接近有序的序列。（分组排序）
2.直接插入排序。
总的来说：选择一个整数gap，将一个序列分成gap个组，所有数据间距为gap进到一个组。并对这gap个组分别进行排序。然后减小gap的取值，重复上述的操作，当gap等于1的时候，进行直接插入排序。
【步骤1：对一个有序的组，插入一个数据】

	int gap = 3;//两个数据之间的间隔int end;//一组有序数据中，最后一个数据的位置int tmp = a[end + gap];//表示待插入到这组有序数据的下一个值while (end >= 0){if (tmp < a[end]){//待插入数据小于最后一个数据a[end + gap] = a[end];//将最后一个数据往后覆盖end = end - gap;//更新end的位置}else{break;}}a[end + gap] = tmp;//插入数据

【步骤2：将一个组进行排序】

int gap = 3;//两个数据之间的间隔for (int i = 0; i < n - gap; i=i+gap)//i每次跳动gap个距离，对一个组进行排序{int end=i;//一组有序数据中，最后一个数据的位置int tmp = a[end + gap];//表示待插入到这组有序数据的下一个值while (end >= 0){if (tmp < a[end]){//待插入数据小于最后一个数据a[end + gap] = a[end];//将最后一个数据往后覆盖end = end - gap;//更新end的位置}else{break;}}a[end + gap] = tmp;//插入数据}

【步骤3：将所有的组进行一次排序】

int gap = 3;//两个数据之间的间隔for (int j = 0; j < gap; j++)//j为每一个组的第一个元素的位置{for (int i = j; i < n - gap; i = i + gap)//i每次跳动gap个距离，对一个组进行排序{int end = i;//一组有序数据中，最后一个数据的位置int tmp = a[end + gap];//表示待插入到这组有序数据的下一个值while (end >= 0){if (tmp < a[end]){//待插入数据小于最后一个数据a[end + gap] = a[end];//将最后一个数据往后覆盖end = end - gap;//更新end的位置}else{break;}}a[end + gap] = tmp;//插入数据}}

【步骤4：重复定义gap的值进行对序列进行排序】
考虑gap的取值？
gap的取值越大，跳的越快，序列越不有序；
gap的取值越小，跳的越慢，序列越有序。
当gap==1的时候，进行排序之后就是有序的了。

void ShellSort(int* a, int n)
{int gap = n;//两个数据之间的间隔while (gap > 1){gap /= 2;for (int j = 0; j < gap; j++)//j为每一个组的第一个元素的位置{for (int i = j; i < n - gap; i = i + gap)//i每次跳动gap个距离，对一个组进行排序{int end = i;//一组有序数据中，最后一个数据的位置int tmp = a[end + gap];//表示待插入到这组有序数据的下一个值while (end >= 0){if (tmp < a[end]){//待插入数据小于最后一个数据a[end + gap] = a[end];//将最后一个数据往后覆盖end = end - gap;//更新end的位置}else{break;}}a[end + gap] = tmp;//插入数据}}}
}

【算法的最终实现】

void ShellSort(int* a, int n)
{int gap = n;//两个数据之间的间隔while (gap > 1){gap /= 2;for (int j = 0; j < gap; j++)//j为每一个组的第一个元素的位置{for (int i = j; i < n - gap; i = i + gap)//i每次跳动gap个距离，对一个组进行排序{int end = i;//一组有序数据中，最后一个数据的位置int tmp = a[end + gap];//表示待插入到这组有序数据的下一个值while (end >= 0){if (tmp < a[end]){//待插入数据小于最后一个数据a[end + gap] = a[end];//将最后一个数据往后覆盖end = end - gap;//更新end的位置}else{break;}}a[end + gap] = tmp;//插入数据}//end_for(i)}//end_for(j)}//end_while (gap > 1)
}

**希尔排序的底层逻辑：**将较大的值快速的往后移动。