Shell排序Java示例

谁能给我一个shell排序的例子？ 我是这里的新人，他必须学习shell排序，但首先我必须找到一个Java shell排序示例。 我在谷歌找到了一个例子，但这太难了。

Answer 1

您是否尝试过首先阅读维基百科文章？ 它通过插图和示例提供了非常好的基础知识。

此后，您可能想查看一些描述此排序过程的Java小程序和动画。

希望在那之后，你可能会发现这里的java代码，例如，更具可读性。

希望能帮助到你。

Answer 2

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

/** * Shellsort, using Shell's (poor) increments. * @param a an array of Comparable items. */ public static > 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; } } } 

我从一本名为Java中的数据结构和算法分析的书中偷了它。 这本书很容易理解。 我建议你阅读它。

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 > 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[jh].compareTo(s) > 0); j-=h) a[j] = a[jh]; a[j] = s; } h /= 3; } } } 

Answer 5

这是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[jh]: 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 6

我发现理解shell排序的最简单方法是将其分解为段：

 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; ih-1 && theArray[jh] >= temp; j=jh){ a[j] = a[jh]; } a[j] = temp; } h = (h-1)/3; } } Output: 5, 12, 22, 33, 43, 44, 53, 57, 97, 765 

Answer 7

这是一个例子：

 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 8

经典原始类型实现：

 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 = ih; 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 9

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

list – 是int []; GapArray取自Marcin Ciura的arcticle http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf

Answer 10

这是一个video链接： https ： //youtu.be/SCBf7aqKQEY这家伙制作了一个很好的shell排序video！

还有一个简单的代码：

 int sort(int arr[]) { int n = arr.length; int gap = n/2; int i,j; while(gap>0) { for (i=0,j=i+gap; jarr[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; } }