数据结构-排序-希尔排序

    科技2024-11-20  20

    希尔排序实现原理:

    选定一个增长量h,按照增长量 h 作为数据分组的依据,对数据进行分组;对分好组的每一组数据完成插入排序;减小增长量,最小减为 1,重复第二步操作。如图,颜色相同的进行比较:

    希尔排序算法实现:(不稳定排序)

    public static void main(String[] args) { // 测试 int[] arr = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5}; sort(arr); for (int i : arr) { System.out.print(i+"\t"); } } public static void sort(int[] a) { // 根据数组长度,确定增长量h的初始值 int h = 1; while (h < a.length / 2) { h = 2 * h + 1; } // 进行希尔排序 while (h >= 1) { // 找到待插入的元素 for (int i = h; i < a.length; i++) { // 把待插入的元素插入到有序数列中 for (int j = i; j >= h; j -= h) { // 待插入元素是a[j], 比较a[j]和a[j-h] if (greater(a[j - h], a[j])) { exc(a, j - h, j); } else { break; } } } // 减小h的值 h /= 2; } } /* * 比较两个数的大小 */ public static boolean greater(int v, int w) { return v > w; } /* * 交换两个位置的值 */ public static void exc(int[] a, int i, int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }

    程序执行结果:

    Processed: 0.010, SQL: 8