希尔排序
2021-03-18 15:26
标签：代码 思想 gap 位置 while shell 退出 缩小 方式 插入排序可能存在的问题是数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是： 结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。 希尔排序 是希尔（Donald Shell）于1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止 希尔排序法的示意图 希尔排序 标签：代码 思想 gap 位置 while shell 退出 缩小 方式 原文地址：https://www.cnblogs.com/bairentianshi/p/13914620.html引入：简单插入排序存在的问题
希尔排序法介绍
是经过改进之后的一个更高效的版本，也称为缩小增量排序。 希尔排序法基本思想
代码实现
1. public class shellsort {
2. public static void main(String[] args) {
3. int[] arr1 = {3, 9, -1, 10, -2};
4. System.out.println("原数组为：" + Arrays.toString(arr1));
5. shellSort1(arr1);
6. System.out.println("排序后数组为：" + Arrays.toString(arr1));
7.
8. System.out.println("*************************************");
9.
10. int[] arr2 = {3, 9, -1, 10, -2};
11. System.out.println("原数组为：" + Arrays.toString(arr2));
12. shellSort2(arr2);
13. System.out.println("排序后数组为：" + Arrays.toString(arr2));
14. }
15.
16. //交换式
17. private static void shellSort1(int [] arr) {
18. int temp;
19. for (int gap = arr.length / 2; gap > 0; gap /= 2) {
20. // 遍历各组中所有的元素, 注意：步长gap
21. for (int i = gap; i ) {
22. for (int j = i - gap; j >= 0; j -= gap) {
23. // 如果当前元素大于加上步长后的那个元素，说明交换
24. if (arr[j] > arr[j + gap]) {
25. temp = arr[j];
26. arr[j] = arr[j + gap];
27. arr[j + gap] = temp;
28. }
29. }
30. }
31. }
32. }
33.
34. //对交换式的希尔排序进行优化->移位方式
35. private static void shellSort2(int[] arr) {
36. // 增量 gap, 并逐步的缩小增量
37. for (int gap = arr.length / 2; gap > 0; gap /= 2) {
38. // 从第 gap 个元素，逐个对其所在的组进行直接插入排序
39. for (int i = gap; i ) {
40. int insertValue = arr[i];
41. int insertIndex = i - gap;
42. while (insertIndex >= 0 && insertValue arr[insertIndex]) {
43. arr[insertIndex + gap] = arr[insertIndex]; //移动
44. insertIndex -= gap;
45. }
46. //当退出 while 后，就给 temp 找到插入的位置
47. arr[insertIndex + gap] = insertValue;
48. }
49. }
50. }
51. }
上一篇：JAVA常量
下一篇：Go语言创建Web服务器