Shell排序Java示例

Question

任何人都可以给我一个关于shell排序的例子吗？我是一个在这里必须了解shell排序的新人，但首先我必须找到一个Java shell排序示例。我在Google上找到一个例子，但这太难了。

Answer 1

您是否试过首先阅读维基百科文章here？它提供了一个相当不错的基础知识插图和例子。

此后您可能会喜欢查看一些java小程序&描述此排序过程的动画here。

希望在此之后，您可能会发现java代码here，例如，更具可读性。

希望它有帮助。

Answer 2

下面是一个例子：

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 3

可能，这的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 4

Shell排序通过比较由几个位置的间隙分开的元件改善了插入排序。

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

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

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 5

经典原语类型的实现：

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; 
    }; 
} 

P.S。：检查this link其他排序算法（它们是在C++中，虽然，容易携带到Java）。

Answer 6

这里，这个代码是非常简单的：

/** 
    * 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 7

这里是壳排序为一个Python实现可视化：

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 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 [];从马尔钦Ciura的arcticle采取 http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf

Answer 9

我找到了解希尔排序的最简单的方法 GapArray是把它分解成段：

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 10

这里是一个视频链接：https://youtu.be/SCBf7aqKQEY 这家伙已经取得一个很好的视频排序！

和一个简单的代码：

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 11

使用此

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; 

    } 
}