简单插入排序存在的问题

　　我们看简单的插入排序可能存在的问题. 数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：

{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}

　　结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.

　　　　希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

　　　　希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

　　

　　

　　请使用希尔排序对 {8,9,1,7,2,3,5,4,6,0} 实现从小到大的排序。

  1.  1 　　// 使用逐步推导的方式来编写希尔排序
  2.  2     public static void shellSort(int[] arr) {
  3.  3         
  4.  4         int temp = 0;
  5.  5         //希尔排序第1轮
  6.  6         //第一轮排序，将10个数据分成了5组
  7.  7         for (int i = 5; i < arr.length; i++) {
  8.  8             //遍历各组中所有元素（供5组，每组2个元素），步长5
  9.  9             for (int j = i-5; j >= 0; j-=5) {
  10. 10                 //如果当前元素大于加上步长后的那个元素，说明交换
  11. 11                 if (arr[j] > arr[j+5]) {
  12. 12                     temp = arr[j];
  13. 13                     arr[j] = arr[j+5];
  14. 14                     arr[j+5] = temp;
  15. 15                 }
  16. 16             }
  17. 17         }
  18. 18         System.out.println("第1轮：" + Arrays.toString(arr));
  19. 19         
  20. 20         //第2轮排序，将10个数据分成了5/2=2组
  21. 21         for (int i = 2; i < arr.length; i++) {
  22. 22             
  23. 23             for (int j = i-2; j >= 0; j-=2) {
  24. 24                 if (arr[j] > arr[j+2]) {
  25. 25                     temp = arr[j];
  26. 26                     arr[j] = arr[j+2];
  27. 27                     arr[j+2] = temp;
  28. 28                 }
  29. 29             }
  30. 30         }
  31. 31         System.out.println("第2轮：" + Arrays.toString(arr));
  32. 32         
  33. 33         //第3轮排序，将10个数据分成了2/2=1组
  34. 34         for (int i = 1; i < arr.length; i++) {
  35. 35             
  36. 36             for (int j = i-1; j >= 0; j-=1) {
  37. 37                 if (arr[j] > arr[j+1]) {
  38. 38                     temp = arr[j];
  39. 39                     arr[j] = arr[j+1];
  40. 40                     arr[j+1] = temp;
  41. 41                 }
  42. 42             }
  43. 43         }
  44. 44         System.out.println("第3轮：" + Arrays.toString(arr));
  45. 45         
  46. 46         
  47. 47     }

 

  1.  1 　　// 希尔排序，对有序序列在插入时采用交换法
  2.  2     public static void shellSort2(int[] arr) {
  3.  3         int temp = 0;
  4.  4         int count = 0;
  5.  5         // 根据前面的逐步分析，使用循环处理
  6.  6         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  7.  7             for (int i = gap; i < arr.length; i++) {
  8.  8                 // 遍历各组中所有的元素（供gap组），步长gap
  9.  9                 for (int j = i - gap; j >= 0; j -= gap) {
  10. 10                     // 如果当前元素大于加上步长后的那个元素，说明交换
  11. 11                     if (arr[j] > arr[j + gap]) {
  12. 12                         temp = arr[j];
  13. 13                         arr[j] = arr[j + gap];
  14. 14                         arr[j + gap] = temp;
  15. 15                     }
  16. 16                 }
  17. 17             }
  18. 18             System.out.println("第"+(++count)+"轮：" + Arrays.toString(arr));
  19. 19         }
  20. 20     }

 

  1.  1 public static void main(String[] args) {
  2.  2         // 创建80000个随机的数组
  3.  3         int[] arr2 = new int[80000];
  4.  4         for (int i = 0; i < 80000; i++) {
  5.  5             arr2[i] = (int) (Math.random() * 800000);
  6.  6         }
  7.  7 
  8.  8         Date date1 = new Date();
  9.  9         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
  10. 10         String start = simpleDateFormat.format(date1);
  11. 11         System.out.println("排序前：" + start);
  12. 12 
  13. 13         // 测试交换法
  14. 14         shellSort2(arr2);
  15. 15 
  16. 16         Date date2 = new Date();
  17. 17         String end = simpleDateFormat.format(date1);
  18. 18         System.out.println("排序后：" + end);
  19. 19 
  20. 20     }

 

　　

 　　可以发现采用希尔排序——交换法对8万个数据排序大概需要10秒左右的时间，比原来的插入排序更加耗时，因为它内部一直在不停的交换，所以导致比较浪费时间。

 

　　　　不会频繁的交换位置，而是找到最小值的位置然后进行插入。

  1.  1 　　// 对交换式的希尔排序进行优化->移位法
  2.  2     public static void shellSort3(int[] arr) {
  3.  3         int count = 0;
  4.  4 
  5.  5         // 根据前面的逐步分析，使用循环处理
  6.  6         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  7.  7             // 从第gap个元素，逐个对其所在的组进行直接插入排序
  8.  8             for (int i = gap; i < arr.length; i++) {
  9.  9                 int j = i;
  10. 10                 int temp = arr[j];
  11. 11                 if (arr[j] < arr[j - gap]) {
  12. 12                     while (j - gap >= 0 && temp < arr[j - gap]) {
  13. 13                         // 移动
  14. 14                         arr[j] = arr[j - gap];
  15. 15                         j -= gap;
  16. 16                     }
  17. 17                     // 当退出while后，就给temp找到插入的位置
  18. 18                     arr[j] = temp;
  19. 19                 }
  20. 20             }
  21. 21             // System.out.println("第"+(++count)+"轮：" + Arrays.toString(arr));
  22. 22 
  23. 23         }
  24. 24     }

 

  1.  1 public static void main(String[] args) {
  2.  2         // 创建80000个随机的数组
  3.  3         int[] arr2 = new int[80000];
  4.  4         for (int i = 0; i < 80000; i++) {
  5.  5             arr2[i] = (int) (Math.random() * 800000);
  6.  6         }
  7.  7 
  8.  8         Date date1 = new Date();
  9.  9         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
  10. 10         String start = simpleDateFormat.format(date1);
  11. 11         System.out.println("排序前：" + start);
  12. 12 
  13. 13         // 测试移位法
  14. 14         shellSort3(arr2);
  15. 15 
  16. 16         Date date2 = new Date();
  17. 17         String end = simpleDateFormat.format(date2);
  18. 18         System.out.println("排序后：" + end);
  19. 19 
  20. 20     }

 

　　

 　　可以看到优化后的希尔排序，对8万个数据排序仅用了1秒左右，非常的快速。

　　　　交换法：易于理解，效率较低。

　　　　移位法：效率较高。

 

版权声明：本文为niujifei原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/niujifei/archive/2004/01/13/13277967.html