当前位置:   article > 正文

常见排序算法——希尔排序

常见排序算法——希尔排序

基本原理

希尔排序在插入排序的基础之上,将待排序序列分成组,分成 gap 个组,组的数量通过 length /  2 获得,比如6个元素的序列,那么就是 3 个组,每个组两个元素,然后将每个组的元素进行插入排序即可,此时分组完成之后,将3个组再分,得到1,进行常规插入排序即可。

 每次插入排序,不是和前一个元素进行比较,而是和前面第 gap 个元素进行比较。

举例

1. 原始序列

2. 此时序列的长度是 8 ,那么就是分为 4 组,每两个元素一组,而每组成员之间下标相差 4 。

3. 每组之间进行插入排序,例如 8 和 6 作比较,降序,要交换,2 和 7 作比较,不交换;5 和 10 作比较,不交换,9 和 1 作比较,交换

4. 再次分组,gap / 2 ,得到 2 ,也就是说分为2组,每个元素下标相差 2

5. 同样在组内进行插入排序

6. 再次分组 gap / 2 ,得到 1, 即最后一次常规插入排序即可。

7. 希尔排序相较于直接插入排序,减少了交换次数,每次分组内的排序就能将元素锁定在某个区域内,最后常规插入排序就不需要交换太多次就能直接排序完成,举个例子,假如最后一个元素是最小的数,它理应放在第一个元素,那么他就需要从头到尾和每个元素进行交换,而如果一开始进行分组,那么他一下就能交换到序列的中间,直接少了一半的交换量。

代码实现

  1. /**
  2. * 希尔排序
  3. */
  4. public class test {
  5. public static void main(String[] args) {
  6. int[] nums = {6, 7, 1, 1, 3, 2, 8, 9, 4};
  7. int gap = nums.length / 2;
  8. //gap 为0 即为排序完成
  9. while (gap >0){
  10. for (int i = gap; i < nums.length; i++) {
  11. int current = nums[i];
  12. int preIndex = i-gap;
  13. //组内进行插入循环,当前元素比前一元素小时,做交换,然后将前一元素的下标记录下来再用它和前一元素作比较。
  14. while(preIndex >= 0 && current < nums[preIndex]){
  15. swap(nums,preIndex + gap,preIndex);
  16. preIndex -= gap;
  17. }
  18. }
  19. gap /= 2;
  20. }
  21. System.out.println(Arrays.toString(nums));
  22. }
  23. //元素交换方法
  24. public static void swap(int[] nums, int a, int b) {
  25. int swap = nums[a];
  26. nums[a] = nums[b];
  27. nums[b] = swap;
  28. }
  29. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/920641
推荐阅读