使用 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
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 +1	    
   
   while interval > 0 do:
      for outer = interval; outer < A.length; outer ++ do:
         /* select value to be inserted */
	     valueToInsert = A[outer]
         inner = outer;
         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner-1]
            inner = inner - interval
         end while
         /* insert the number at hole position */
         A[inner] = valueToInsert
      end for
      /* calculate interval*/
      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]
==================================================