希尔排序 Java 示例

Question

谁能举个关于希尔排序的例子吗？我是这里的新人，必须学习希尔排序，但首先我必须找到一个 Java 希尔排序示例。我在谷歌上找到了一个例子，但是太难了。

Answer 1

在这里，这段代码非常简单：

/**
   * Shellsort, using Shell’s (poor) increments.
   * @param a an array of Comparable items.
   */
  public static <T extends Comparable<? super T>>
  void shellsort( T [ ] a )
  {
    int j;
    for( int gap = a.length / 2; gap > 0; gap /= 2 )
    {
      for( int i = gap; i < a.length; i++ )
      {
         T tmp = a[ i ];
         for( j = i; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
         {
           a[ j ] = a[ j - gap ];
         }
         a[ j ] = tmp;
      }
    }
  }

我从一本名为 Data Structures and Algorithm Analysis in Java。是一本很容易理解的好书。我建议你读一下。

Answer 2

也许，这个java代码会对您有所帮助。

 public class ShellSort {
       private long[] data;

      private int len;

      public ShellSort(int max) {
        data = new long[max];
        len = 0;
      }

      public void insert(long value){
        data[len] = value; 
        len++;
      }

      public void display() {
        System.out.print("Data:");
        for (int j = 0; j < len; j++)
          System.out.print(data[j] + " ");
        System.out.println("");
      }

      public void shellSort() {
        int inner, outer;
        long temp;
        //find initial value of h
        int h = 1;
        while (h <= len / 3)
          h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)

        while (h > 0) // decreasing h, until h=1
        {
          // h-sort the file
          for (outer = h; outer < len; outer++) {
            temp = data[outer];
            inner = outer;
            // one subpass (eg 0, 4, 8)
            while (inner > h - 1 && data[inner - h] >= temp) {
              data[inner] = data[inner - h];
              inner -= h;
            }
            data[inner] = temp;
          }
          h = (h - 1) / 3; // decrease h
        }
      }

      public static void main(String[] args) {
        int maxSize = 10;
        ShellSort arr = new ShellSort(maxSize);

        for (int j = 0; j < maxSize; j++) {
          long n = (int) (java.lang.Math.random() * 99);
          arr.insert(n);
        }
        arr.display();
        arr.shellSort();
        arr.display();
      }
    }

Answer 3

希尔排序通过比较由多个位置间隔分隔的元素来改进插入排序。

这可以让元素向其预期位置迈出“更大的一步”。以越来越小的间隙尺寸对数据进行多次传递。希尔排序的最后一步是普通的插入排序，但到那时，数据数组就保证几乎已排序。

这段代码可能会帮助您更好地理解逻辑。

package Sorts;
public class ShellSort extends Sorter{

@Override
public <T extends Comparable<? super T>> void sort(T[] a) {
    int h = 1;
    while((h*3+1) < a.length)
        h = 3*h+1;
    while(h > 0){
        for(int i = h-1; i < a.length; i++){
            T s = a[i];
            int j = i;
            for(j = i; (j>=h) && (a[j-h].compareTo(s) > 0); j-=h)
                a[j] = a[j-h];
            a[j] = s;
        }
        h /= 3;
    }
}
}

Answer 4

以下是 Python 实现的 shell 排序的可视化：

def exch(a,i,j):
  t = a[i]
  a[i] = a[j]
  a[j] = t

def shellsort(string):
  print string
  a = list(string)
  N = len(a)
  h = 1
  i = 0
  j = 0
  k = 0
  #determine starting stride length
  while ( h < N/3 ):
    h = 3*h + 1
  print "STRIDE LENGTH: " + str(h)
  while (h >=1):
    i = h
    while i < N:
      j = i
      k = j - h
      while j >= h and a[j] < a[j-h]:
        k = j - h
        exch(a,j,k)
        j -= h
      i += 1
    h = h/3
    print "STRIDE LENGTH: " + str(h)
  print ''.join(a)·


if __name__ == '__main__':
    shellsort("astringtosortwithshellsort")

Answer 5

这是一个例子：

public static void shellsort( Comparable [ ] a )
    {
        for( int gap = a.length / 2; gap > 0;
                     gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )
            for( int i = gap; i < a.length; i++ )
            {
                Comparable tmp = a[ i ];
                int j = i;

                for( ; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
                    a[ j ] = a[ j - gap ];
                a[ j ] = tmp;
            }
    }

Answer 6

我发现理解希尔排序的最简单方法是将其分成几段：

private static void shellsort() {
    int[] theArray = {44,5,33,22,765,43,53,12,57,97};

    //first section gets the Knuth's interval sequence (very efficient)
    int h=1;
    while(h<= theArray.length/3){
        h = 3*h + 1;   //h is equal to highest sequence of h<=length/3 (1,4,13,40...)
    }

    //next section
    while(h>0){    //for array of length 10, h=4

       //similar to insertion sort below
       for(int i=0; i<theArray.length; i++){ 

            int temp = theArray[i]; 
            int j;              

            for(j=i; j>h-1 && theArray[j-h] >= temp; j=j-h){
                a[j] = a[j-h];                  
            }
            a[j] = temp;
        }
        h = (h-1)/3; 
    }
}

Output: 5, 12, 22, 33, 43, 44, 53, 57, 97, 765

Answer 7

经典原始类型实现：

package math;

import java.util.Arrays;

public class Sorter{

    public static void main(String []args){
        int[] a = {9,8,7,6,5,4,3,2,1};//plz use sophisticated random number generator
        System.out.println( Arrays.toString(a) );
        System.out.println( Arrays.toString(shellSort(a)) );
    }

    //Performs a shell sort on an array of ints.
    public static int[] shellSort(int[] array){
        int h = 1;
        while (h < array.length) h = 3*h + 1;
        while (h > 0){
            h = h/3;
            for (int k = 0; k < h; k++){
                for (int i = h+k; i < array.length; i+=h){
                    int key = array[i];
                    int j = i-h;
                    while (j>=0 && array[j] > key){
                        array[j+h] = array[j];
                        j-=h;
                    }
                    array[j+h] = key;
                    //-> invariant: array[0,h,2*h..j] is sorted
                }
            }
            //->invariant: each h-sub-array is sorted
        }
        return array;
    };
}

PS：检查 此链接用于其他排序算法（尽管它们是用 C++ 编写的，但可以轻松移植到 Java）。

Answer 8

package sort_tester;

public class ShellSorter extends Sorter {

private final int[] gapArray = {1750,701,301,132,57,23,10,4,1};

@Override
public void makeSort (boolean trace) {

    int size = list.length;
    int i,j, temp;

    for ( int gap : gapArray ) {

        i = gap;

        while ( i < size ) {
            temp = list[i];
            j = i-gap;
            while ( j >= 0 && list[j] > temp ) {
                list[j + gap] = list[j];
                j -= gap;
            }
            list[j + gap] = temp;
            i ++;
        }
    }
}
}

列表 - 是 int[]；
GapArray 取自 Marcin Ciura 的文章
http://sun.aei.polsl.pl/~mciura/publikacje/shellsort .pdf

Answer 9

以下是视频链接：https://youtu.be/SCBf7aqKQEY
这家伙制作了一个很好的 shell sort 视频！

和一个简单的代码：

int sort(int arr[])
{
    int n = arr.length;
    int gap = n/2;
    int i,j;

    while(gap>0)
     {  for (i=0,j=i+gap; j<n; i++,++j)
        {     
           if(arr[i]>arr[j])                   //swap
              { int temp = arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
              } 

        }
        gap=gap/2;
     }
    return 0;
}

Answer 10

使用这个

 public void shellSort(Integer[] arr) {

    int interval = arr.length / 2;

    while (interval != 0) {

        for (int i = 0; i < interval; i++) {

            for (int p = i + interval; p < arr.length; p += interval) {

                int key = arr[p];
                int j = p - interval;
                while (j >= 0) {

                    if (key < arr[j]) {
                        arr[j + interval] = arr[j];
                    } else 
                        break;
                    j -= interval;
                } 

                arr[j + interval] = key;

            } 
        }

        interval /= 2;

    }
}

Answer 11

具有 3k+1 间隙的片段。

public void shellSort(Comparable arr[], int size, int h, int x) {
        while (h >= 1) {
            for (int i = 0; i <= size - h; i++) {
                for (int j = i; j < size-h && (arr[j].compareTo(arr[j+h]) > 0); j += h)
                    swap(arr, j, j+h);      
            }
            h = 3*(--x) + 1;
        }
    }