首页 > 代码库 > 希尔排序

希尔排序

2024-09-17 12:52:50   218人阅读

    希尔排序对插入排序进行了改进，传统的插入排序，每取一个数都要把前面平均一半的数往后移动一位以空出该数的位置，这样的复制次数太多，如果有很多很小的数靠近右端，几乎每次都要将左侧所有的数移动一位。
    以10个数为例，试想把数据先分组，先把第0、4、8个分为一组进行插入排序；再将第1、5、9位的数据进行插入排序，如此下去直至排完（称为4-增量排序）。这样一来，数据达到“基本有序”状态，再进行一次1-增量排序（也就是传统的插入排序），这次的插入排序速度就快很多。
    若数据量 n 更大，则一开始的增量排序 h也相应增大，具体公式为：
  1. 		while (h < n / 3) {
  2. 			h = 3 * h + 1;
  3. 		}

下面以10个数的希尔排序为例：
  1. // 希尔排序(从小到大)
  2. public class TestShellSort {
  3. 	@Test
  4. 	public void test() {
  5. 		// 赋初始值
  6. 		int[] arr = new int[10];
  7. 		for (int i = 0; i < 10; i++) {
  8. 			arr[i] = (int) (100 * Math.random());
  9. 		}
  10. 		System.out.println("排序之前：\n" + java.util.Arrays.toString(arr) + "\n");
  12. 		// 进行排序
  13. 		// 确定本次的增量
  14. 		int h = 1;
  15. 		while (h < arr.length / 3) {
  16. 			h = 3 * h + 1;
  17. 		}
  18. 		// 依次按增量进行排序
  19. 		while (h > 0) {
  20. 			for (int i = h; i < arr.length; i++) {
  21. 				// 储存i位置元素
  22. 				int temp = arr[i];
  23. 				// 判断当前元素是否需要排
  24. 				if (arr[i] < arr[i - h]) {
  25. 					int j = i - h;
  26. 					// 只要j位置元素大于当前元素 temp，指针就往左移1增量，且j位置元素右移1增量
  27. 					for (; j >= 0 && arr[j] > temp; j -= h) {
  28. 						arr[j + h] = arr[j];
  29. 					}
  30. 					// 找到第一个比 temp 小的元素或者遍历到了起始位置，把 temp 赋值给这个位置右1个增量位置的元素
  31. 					arr[j + h] = temp;
  32. 				}
  33. 			}
  34. 			// 下一次的增量
  35. 			h = (h - 1) / 3;
  36. 		}
  38. 		// 输出结果
  39. 		System.out.println("排序之后：\n" + java.util.Arrays.toString(arr));
  40. 	}
  41. }

希尔排序


联系
我们