希尔排序c/c++

希尔排序算法

理解

希尔排序是对插入排序的一种优化，又叫做“缩小增量排序”。希尔排序是把序列中元素按照下标的一定增量值进行分组，对每个分组分别进行插入排序，并且不断缩小增量，直到增量为1.

思路

一共三层循环：

增量我们取元素个数的二分之一，并一直以/=2迭代，直到增量为1。（最外层）

和插入排序一样，从后往前比较，初始从下标为增量的那个数开始。（中间层）

从后往前比较但不一定是相邻两个，比较的数位置相差一个增量，并且这个数必须大于等于增量。（三层循环）

代码实现

// 外层循环控制增量for (int gap = len / 2;gap >0; gap/=2){// 从下标为增量的那个数开始for (int i = len/2; i < len; i++){// 向前进行比较，相差一个增量的数为一组for (int j = i; j >= gap; j-=gap){if (q[j]<q[j-gap]){swap(q[j],q[j-gap]);}}}}