3.常见8种排序算法分析笔记之-时间性能突破O(n^2)的原地排序法-希尔排序法

时间性能突破 O ( n 2 ) O(n^2) O(n2)的原地排序法-希尔排序法

参考慕课网算法与数据结构体系课程

1.基本代码实现思想

• 是插入排序法的一种优化，解决插入排序法逆序对较多，循环交换次数多的问题

  • 插入排序法由于只交换相邻元素，每次逆序数量只能减1
  • 希尔排序通过交换不相邻的元素，每次可以将逆序数量减少量大于1
    • 例如，321，3个逆序对，3与2交换，还有两个逆序对，减少了1个，3与1交换后，直接可以减少掉3个逆序对

• 希尔排序通过将不相邻的数据分成一组，每组进行插入法排序，分成h组，每组间隔h，不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

• 图解：

  • 先按照二分法进行分组：

    

  • 对每组元素进行排序（使用插入排序这种原地排序法）

    

  • 继续二分法进行分组，缩小每组的间隔

    

  • 最后使分组间隔为1，即原有数组大小，最后进行排序结果就是整个数组有序

  

2.基本代码实现

public class ShellSort {
	private ShellSort() {}
	
	public static <E extends Comparable <E>> void sort(E[] arr) {
        if(arr == null || arr.length <= 2) return;
        
		// 为减少逆序对，分组跨数据进行插入排序，最终保证小的均往前排，大的往后排
		// 先用二分法分成h组，每组间隔为h
		int h = arr.length / 2;
		while (h >= 1) { // 最后每组间隔为1，即只有一组，原有数组进行排序
			// 此层是循环处理每一组，有多少组，就要循环多少轮
			for (int start = 0; start < h; start++) {
				// 此层是处理每一组的数据，即每组的插入排序法，区别是每次指针移动h步
				for (int i = start + h; i < arr.length; i += h) {
					E target = arr[i];
					int j;
					for (j = i; j - h >= 0 && target.compareTo(arr[j - h]) < 0; j -= h) {
						arr[j] = arr[j - h];
					}
					arr[j] = target;
				}
			}

			h = h / 2; // 注意对每组大小h的维护，二分法依次减少
		}
    }
}

3.复杂度分析

• 时间复杂度：介于 O ( n 2 ) O( n ^2) O(n2)和 O ( n l o g n ) O(nlogn) O(nlogn)之间，一般比 O ( n l o g n ) O(nlogn) O(nlogn)的排序法慢2倍左右视它的最好最坏以及平均复杂度具体分析

• 空间复杂度： O ( 1 ) O(1) O(1)，即需要常数级的变量空间，无需开辟新的空间

• 稳定性：指的是相同元素保存相对位置不变的特性，与插入法类似，改变了元素的前后位置，是不稳定的
  

• 上述只是近视推倒，表明性能是优于 O ( n 2 ) O(n^2) O(n2),其实，h细分后，每轮的逆序对减少，分子已经不是 n 2 n^2 n2，故性能要比推导的更加优

4.代码测试

public static void main(String[] args) {
		int n = 100000;
		System.out.println("Random Array:");
		Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
		Integer[] arr1 = Arrays.copyOf(arr, arr.length);
		Integer[] arr2 = Arrays.copyOf(arr, arr.length);
		Integer[] arr3 = Arrays.copyOf(arr, arr.length);
		Integer[] arr4 = Arrays.copyOf(arr, arr.length);

		SortingHelper.sortTime("ShellSort", arr);
		SortingHelper.sortTime("BubbleSort", arr1);
		SortingHelper.sortTime("MergeSort", arr2);
		SortingHelper.sortTime("QuickSort2Way", arr3);
		SortingHelper.sortTime("HeapSort", arr4);
	}

ShellSort, n = 100000 : 0.073768 s
BubbleSort, n = 100000 : 44.182490 s	// 与O(N^2)算法相比，性能明显有优势
MergeSort, n = 100000 : 0.040897 s		// 与O(nlogn)算法相比，一般慢2倍左右
QuickSort2Way, n = 100000 : 0.043742 s
HeapSort, n = 100000 : 0.058197 s

5.代码优化1-代码简化

• 其实，可以将上述代码的四重循环精简成三层循环
• 第一层，h轮，第二层，n/h轮分别操作，实质上还是在原有数组上进行操作，因此可以合并为一层循环
• 只是，逻辑上每个数都要找它相隔h步对应的逻辑分组内的元素进行比较
• 只是代码上的优化，性能上复杂度没有变化

public class ShellSort {
	private ShellSort() {}
	
	public static <E extends Comparable <E>> void sort1(E[] arr) {
        if(arr == null || arr.length <= 2) return;
        
		// 为减少逆序对，分组跨数据进行插入排序，最终保证小的均往前排，大的往后排
		// 先用二分法分成h组，每组间隔为h
		int h = arr.length / 2;
		while (h >= 1) { // 最后每组间隔为1，即只有一组，原有数组进行排序
			// 此层是循环处理逻辑分组内的每一个数据，可以依次访问，只是处理时找对应相隔h的同组数比较
			for (int i = h; i < arr.length; i ++) {	// i = h，即先找第一组的第二个元素
				// 此层是处理每一组的数据，即每组的插入排序法，区别是每次指针移动h步				
				E target = arr[i];
				int j;
				for (j = i; j - h >= 0 && target.compareTo(arr[j - h]) < 0; j -= h) {
					arr[j] = arr[j - h];
				}
				arr[j] = target;
			}

			h = h / 2; // 注意对每组大小h的维护，二分法依次减少
		}
    }
}

• 代码测试：

public static void main(String[] args) {
		int[] nums = { 100000, 1000000 };
		for (int n : nums) {
			System.out.println("Random Array:");
			Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
//			Integer[] arr1 = Arrays.copyOf(arr, arr.length);
			Integer[] arr2 = Arrays.copyOf(arr, arr.length);
			Integer[] arr3 = Arrays.copyOf(arr, arr.length);
			Integer[] arr4 = Arrays.copyOf(arr, arr.length);

			SortingHelper.sortTime("ShellSort", arr);
//			SortingHelper.sortTime("BubbleSort", arr1);
			SortingHelper.sortTime("MergeSort", arr2);
			SortingHelper.sortTime("QuickSort2Way", arr3);
			SortingHelper.sortTime("HeapSort", arr4);
		}
	}

Random Array:
ShellSort, n = 100000 : 0.064826 s
MergeSort, n = 100000 : 0.039064 s
QuickSort2Way, n = 100000 : 0.043521 s
HeapSort, n = 100000 : 0.056122 s

Random Array:
ShellSort, n = 1000000 : 1.196194 s
MergeSort, n = 1000000 : 0.379766 s
QuickSort2Way, n = 1000000 : 0.254596 s
HeapSort, n = 1000000 : 0.676940 s

5.代码优化2-改变步长序列

• 之前代码分组每次二分法，实际步长序列为2倍关系
• 可以改变步长序列，即自定义的步长序列，测试对希尔排序性能的影响
• 以经典的3*n+1步长序列为例

public class ShellSort {
	private ShellSort() {}
	
	public static <E extends Comparable <E>> void sort2(E[] arr) {
        if(arr == null || arr.length <= 2) return;
        
		// 为减少逆序对，分组跨数据进行插入排序，最终保证小的均往前排，大的往后排
		// 自定义积分步长序列,找出能分的最大间隔h，再依次减少
        int h = 1;
        while(h < arr.length) {	// 终止条件也可以是arr.length / 3
            h = h * 3 + 1; // 1, 4, 13, 40...
        }
		while (h >= 1) { // 最后每组间隔为1，即只有一组，原有数组进行排序
			// 此层是循环处理逻辑分组内的每一个数据，可以依次访问，只是处理时找对应相隔h的同组数比较
			for (int i = h; i < arr.length; i ++) {	// i = h，即先找第一组的第二个元素
				// 此层是处理每一组的数据，即每组的插入排序法，区别是每次指针移动h步				
				E target = arr[i];
				int j;
				for (j = i; j - h >= 0 && target.compareTo(arr[j - h]) < 0; j -= h) {
					arr[j] = arr[j - h];
				}
				arr[j] = target;
			}

			h = h / 3; // 注意对每组大小h的维护，依次减少间隔
		}
    }
}

• 代码测试：

public static void main(String[] args) {
		int[] nums = { 100000, 1000000, 5000000};
		for (int n : nums) {
			System.out.println("Random Array:");
			Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
//			Integer[] arr1 = Arrays.copyOf(arr, arr.length);
			Integer[] arr2 = Arrays.copyOf(arr, arr.length);
			Integer[] arr3 = Arrays.copyOf(arr, arr.length);
			Integer[] arr4 = Arrays.copyOf(arr, arr.length);
			Integer[] arr5 = Arrays.copyOf(arr, arr.length);
			
			SortingHelper.sortTime("ShellSort", arr);
			SortingHelper.sortTime("ShellSort2", arr5);
//			SortingHelper.sortTime("BubbleSort", arr1);
			SortingHelper.sortTime("MergeSort", arr2);
			SortingHelper.sortTime("QuickSort2Way", arr3);
			SortingHelper.sortTime("HeapSort", arr4);
			System.out.println();
		}
	}

Random Array:
ShellSort, n = 100000 : 0.076540 s
ShellSort2, n = 100000 : 0.066286 s
MergeSort, n = 100000 : 0.038956 s
QuickSort2Way, n = 100000 : 0.049006 s
HeapSort, n = 100000 : 0.039469 s

Random Array:
ShellSort, n = 1000000 : 1.188562 s
ShellSort2, n = 1000000 : 0.995533 s
MergeSort, n = 1000000 : 0.425528 s
QuickSort2Way, n = 1000000 : 0.316169 s
HeapSort, n = 1000000 : 0.694640 s

Random Array:
ShellSort, n = 5000000 : 10.056582 s
ShellSort2, n = 5000000 : 8.711196 s	// 数据越大，性能优化越明显
MergeSort, n = 5000000 : 2.240890 s
QuickSort2Way, n = 5000000 : 1.778173 s
HeapSort, n = 5000000 : 5.439436 s

• 小结：
  • h，步长序列是影响性能的超参数，目前研究，还没有最优的步长序列
  • 希尔排序，只是用了循环，性能也很好，空间开销小，底层开发可以考虑