沙坪坝网站建设,dw创建网页,page怎么转换wordpress,高端网页游戏1 原理
希尔排序可以看作是对直接插入排序的优化. 直接插入是从前到后遍历数组, 每一个元素都往前移动到最合适的位置. 而希尔排序是利用间隔对数组进行分组, 然后再对每个小组进行子排序, 直到间隔为1.
2 具体步骤
首先要介绍一下间隔是什么.
间隔: 间隔是确定子分组的依据…1 原理
希尔排序可以看作是对直接插入排序的优化. 直接插入是从前到后遍历数组, 每一个元素都往前移动到最合适的位置. 而希尔排序是利用间隔对数组进行分组, 然后再对每个小组进行子排序, 直到间隔为1.
2 具体步骤
首先要介绍一下间隔是什么.
间隔: 间隔是确定子分组的依据, 间隔是多少, 就有多少个子分组, 例如:
数组为: 7,3,2,5,8,1,6,9,0,4, 如果此时间隔为3, 那么如果两个数的间隔为三, 那么二者就为一组, 因为间隔多少就有多少组, 也就是说此时应该有三组, 其索引是:
0, 3, 6, 91, 4, 72, 5, 8
对应的元素为:
7, 5, 6, 43, 8, 92, 1, 0
了解了间隔之后, 下面就是希尔排序的具体步骤了(还是以上面的数组为例子).
1. 初始间隔为数组长度的一半(例子中数组长度为10, 初始间隔为5)
2. 把数组按照间隔进行分组, 组数为间隔大小(例中此时间隔为5, 那也就是第0, 5 一组, 1,6一组, 2, 7一组, 3, 8一组, 4, 9一组)
3. 对每个小组进行插入排序
4. 间隔除以2, 如果0, 重复第二步.
代码:
vectorint sortArray(vectorint nums) {int n nums.size();int gap n / 2;while (gap) {for (int i 0; i gap; i ) {for (int cur_i i gap; cur_i n; cur_i gap) {for (int ii cur_i; ii gap nums[ii] nums[ii - gap]; ii - gap) {swap(nums[ii], nums[ii - gap]);}}}gap / 2;}return nums;
}
