希尔排序算法
理解
希尔排序是对插入排序的一种优化,又叫做“缩小增量排序”。希尔排序是把序列中元素按照下标的一定增量值进行分组,对每个分组分别进行插入排序,并且不断缩小增量,直到增量为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]);}}}}
更多推荐
希尔
发布评论