本文中排序结果默认为升序。

要排序的为上面10个0-9范围内的整数。

一、插入排序

单趟插入排序内部

int tmp;
int end;
while (end >= 0)
{
if (tmp < arr[end])
{
//插入的数较小，end位置的数据往后移动
arr[end + 1] = arr[end];
–end;//继续比较，下标为0的也要比
}
else
{
break;
}
}
//此时有2种情况，1、tmp比arr[end]大 2、[0,end]的数据都比tmp大，此时end变为-1
//都满足tmp的位置应该是0或者end+1
//这种代码逻辑便于后续希尔排序的实现
arr[end + 1] = tmp;

tmp为要插入的那个数，end为要比较数组的最后一个元素的下标.

void InsertSort(int* arr, int n)
{
for (int i=1;i<n;++i)//从下标为1的第二个数据开始，直到最后一个下标为n-1的数
{ //单个数据插入排序
int tmp = arr[i];//要插入的数据,i控制tmp的位置
int end = i – 1;//要插入的区间范围是[0,end],end是最后一个数的下标
while (end >= 0)
{
if (tmp < arr[end])
{
//插入的数较小，end位置的数据往后移动
arr[end + 1] = arr[end];
–end;//继续比较，下标为0的也要比
}
else
{
break;
}
}
//此时有2种情况，1、tmp比arr[end]大 2、[0,end]的数据都比tmp大，此时end变为-1
//都满足tmp的位置应该是0或者end+1
//这种代码逻辑便于后续希尔排序的实现
arr[end + 1] = tmp;
}

}

对于n个元素的数据，第一元素（下标为0的）不用排序，因此从第二个元素开始，下标为1，到最后一个，下标为n-1进行逐个插入。插入的下标范围是0到当前位置的前一个。

最好情况：要排升序，数组内就为升序，遍历一遍数组，发现没有需要调整的，O(N)

最坏情况：要排升序，数组内为降序，第一次要移动1次，第二次2,……最后移动n-1次，为等差数列求和，O(N^2).

我们可以发现一个结论：原数据越有序，插入排序的效率越高，越无序，效率就越低。这个结论有助于我们理解希尔排序对于插入排序的优化点。

二、希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序数组中，所有距离为gap的数据分在同一组内，总共可得到gap个组。

例如10个数据，gap = 3时，三组下标分别为 0369 147 258

然后对每一组内的数据进行排序。对比上面的插入排序，由于定义了gap，此时数据比较时的步长为gap，较小的数据跳到数组前部的速度加快了，从这一点上有效提高了效率。

同时，由于gap的原因，只进行这样的排序只能将每个组的内部进行排序，产生预排序的效果，借助预排序来提高效率，并不能最终的排序。

一组希尔排序内部：

//一个数据的希尔排序

int gap;
int tmp；
int end；
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];//因为分成了组，每次对组内数据排序，步长为gap
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;

当gap为3时，分为了3组，上述代码可认为是3组中任意一组内部的一个数据的插入。

代码逻辑上与插入排序相同，只不过增加了gap，增加了步长，提高了效率。

void ShellSort(int* arr, int n)
{
//因为 有10个数 3 1 9 8 6 0 4 2 5 7，我们暂时分为3组 A B C
// A组：下标为 0 3 6 9
// B组，下标为 1 4 7
// C组，下标为 2 5 8

//预排序，让数跳得快，借此提高效率
//对于gap的取值
//gap越大，跳的越快，越不接近有序
//gap越小，跳的越慢，就越接近有序
int gap = n;//既是组数，也是数据每次的步长

while (gap > 1)
{
gap /= 2;//任何一个数/2一定能得到1，而gap==1的时候，就相当于是前面的插入Insert排序了，最终得到升序结果
//gap开始时较大，能够提高效率，每次/2，逐渐提高精度
//gap/3 + 1，预排序次数减少，最后+1，防止gap=2时，gap=0，无法得到最终升序结果
// gap>1 预排序
// gap==1得到结果
for (int i = gap; i < n; ++i)//从gap的位置开始排，每组的第一个位置不用排，排完A组第一个后排B/C的第一个，然后A的第二个，最后排完
{
//单个数据的希尔排序
int tmp = arr[i];//tmp为i位置的数据
int end = i – gap;//end为tmp往前跳gap的位置，即某一组的前一个数
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];//因为分成了组，每次对组内数据排序，步长为gap
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
PrintArr(arr, n);
}
}

上面for循环中的递增条件为++i，如果换成i+=gap，则为gap组中任意一组的排序。

为++i，使得让这gap个组，各自先排好一个数据，然后各自再排，直到排完，相当于gap个组并行排序，而不是一组内部的连续完成。

gap本身的取值是有争议的，最好能够根据要排序的数据总数n来进行调整，可以每次取n/2级别或n/3级别，但是要保证最好一次排序时gap==1，即一次插入排序，这样就能保证最终结果是升序。

gap的产生使得我们对于原数组进行预排序，步长的增加提高了效率。

同时，每次预排序都会使数组整体上变得更加有序，这也有利于下一次排序效率的提升（插入排序结论），直到最后gap==1时（本来应该是O(N^2)），现在由于预排序，变为O（N），插入排序的效率也会有很大提高。

下面是一些扩展知识，了解一下。

随着数据越来越有序，每次调整的次数也会减少。

这组数据前面为正后面为负，第一次预排序直接将正负颠倒了过来，后续的预排序也使得整个数组更加有序。

希尔排序的时间复杂度可认为是O(NlogN)，实际上可能比这个稍大一些，但是数学证明非常复杂，这里不详细解释。

三、选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，与数组的第一个元素交换，直到全部待排序的数据元素排完 。

每次都是通过遍历的方式寻找最值，没有最好最坏的情况，因此时间复杂度为O(N^2)。

当然，也可以稍加优化，一次遍历同时找出最大和最小，分别放在最左端和最右端，能够提高一点效率，但时间复杂度不变。

//选择排序
void SelectSort(int* arr, int n)
{
int left = 0;
int right = n – 1;
//每次遍历一遍数据，选出最大的和最小的，分别放到数组的首尾
while (left < right)
{
int maxi = left;
int mini = left;//分别为最大值、最小值的下标
for (int i = left+1; i <= right; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
Swap(&arr[mini], &arr[left]);
if (left == maxi)
{
maxi = mini;
}
Swap(&arr[maxi], &arr[right]);
++left;
–right;
}
}

用maxi和mini分别标记遍历数据中的最大值和最小值的下标，每次进入时更新，一开始我将它们初始化为left，即第一个数据（这里初始化的范围只要是遍历范围内即可）

[left,right]为遍历寻找max、min的范围。只要满足left<right即可进入寻找。

然后判断arr[i]与arr[maxi]/arr[mini]的关系，如果满足，就可以改变maxi和mini的下标。

更新下标后将max/min与最左/右端进行Swap交换。

交换完，相当于将最大最小值分别找到并放在两端，随后left++，right–，缩小范围，重复上述过程

要注意一种特殊情况：即第一次下标为mini与left交换后，不能对第二次maxi和right的交换产生影响，当第一次arr[left]就是arr[maxi]时，maxi指向的数据会被修改，使得第二次交换时发生错误。

因此这种情况需要加个if修正一下，第一次交换后mini指向的就是maxi了。

目录

一、插入排序

二、希尔排序

三、选择排序