使用 Java 的 DSA - 希尔排序
概述
希尔排序是一种高效的排序算法,基于插入排序算法。如果较小的值非常靠右,则必须移到最左边,这种算法可以避免插入排序中的大位移。这种算法首先对分布较广的元素使用插入排序对它们进行排序,然后对分布较窄的元素进行排序。这种间距称为间隔。该间隔根据 Knuth 的公式计算为 (h=h*3 +1),其中 h 是间隔,初始值为 1。这种算法对于中等大小的数据集非常有效,因为其平均和最坏情况复杂度为 O(n),其中 n 是项目数。
伪代码
procedure shellSort( A : array of items ) int innerPosition, outerPosition int valueToInsert, interval = 1 /*计算间隔*/ while interval < A.length /3 do: interval = interval * 3 +1 while interval > 0 do: for outer = interval; outer < A.length; outer ++ do: /* 选择要插入的值 */ valueToInsert = A[outer] inner = outer; /*将元素向右移动*/ while inner > interval -1 && A[inner - interval] >= valueToInsert do: A[inner] = A[inner-1] inner = inner - interval end while /* 在洞的位置插入数字 */ A[inner] = valueToInsert end for /*计算间隔*/ interval = (interval -1) /3; end while end procedure
演示程序
package com.tutorialspoint.advancedsort; import java.util.Arrays; public class ShellSortDemo { public static void main(String[] args){ int[] sourceArray = {4,6,3,2,1,9,7}; System.out.println("Input Array: " +Arrays.toString(sourceArray)); printline(50); System.out.println("Output Array: " + Arrays.toString(shellSort(sourceArray))); printline(50); } public static void printline(int count){ for(int i=0;i <count-1;i++){ System.out.print("="); } System.out.println("="); } public static int[] shellSort(int[] intArray){ int inner, outer; int valueToInsert; int interval = 1; int elements = intArray.length; int i=0; while(interval <= elements/3){ interval = interval*3 +1; } while(interval > 0){ System.out.println("iteration "+(i) +"#: " +Arrays.toString(intArray)); for(outer = interval; outer < elements; outer++){ valueToInsert= intArray[outer]; inner = outer; while(inner > interval -1 && intArray[inner - interval] >= valueToInsert){ intArray[inner] = intArray[inner - interval]; inner -=interval; System.out.println(" item moved :" + intArray[inner]); } intArray[inner] = valueToInsert; System.out.println(" item inserted :" + valueToInsert +", at position :" + inner); } interval = (interval -1) /3; i++; } return intArray; } }
如果我们编译并运行上述程序,则会产生以下结果 −
Input Array: [4, 6, 3, 2, 1, 9, 7] ================================================== iteration 0#: [4, 6, 3, 2, 1, 9, 7] item moved :4 item inserted :1, at position :0 item inserted :9, at position :5 item inserted :7, at position :6 iteration 1#: [1, 6, 3, 2, 4, 9, 7] item inserted :6, at position :1 item moved :6 item inserted :3, at position :1 item moved :6 item moved :3 item inserted :2, at position :1 item moved :6 item inserted :4, at position :3 item inserted :9, at position :5 item moved :9 item inserted :7, at position :5 Output Array: [1, 2, 3, 4, 6, 7, 9] ==================================================