Tri de Shell exemple Java

Quelqu'un peut-il me donner des exemple sur le tri de shell? Je suis une nouvelle personne ici qui doivent apprendre à propos de tri de shell, mais je dois d'abord trouver un Java tri de shell exemple. J'ai trouvé un exemple dans Google, mais c'est trop difficile.

OriginalL'auteur Nightstalker | 2011-01-28

  1. 14

    Avez-vous essayé la lecture de l'article de wikipédia en premier ici? Il fournit une assez bonne bases avec une illustration et des exemples.

    Par la suite, vous pourriez, comme pour vérifier certaines des applets java & animations illustrant ce processus de tri ici.

    J'espère que, après que, vous pouvez trouver le code java ici, par exemple, beaucoup plus lisible.

    Espère que cela aide.

    2e et 3e liens sont rompus 🙁

    OriginalL'auteur evandrix

  2. 13

    Ici, ce code est très simple : 

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

    Je l'ai volé à partir d'un livre appelé Structures de données et un Algorithme d'Analyse en Java. C'est un très bon livre facile à comprendre. Je vous conseille de le lire.

    Merci de poster ce! C'est le seul VRAI tri de shell réponse de toutes les réponses. Le reste de ces Knuth la variante du Tri de Shell et je suis sûr que l'écart / 2.2 réponse est juste une perte de temps.
    J'ai inclus le livre, vous pouvez le lire, il est très parfait.
    J'ai l'habitude de ne pas jaillir sur la algos...mais c'est génial!
    Très facile à comprendre. Merci d'être aussi clair.

    OriginalL'auteur Adelin

  3. 9

    Peut-être, ce java code va vous aider. 

     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();
}
}
    merci monsieur. mais je suis encore débutant n pas de comprendre pour apprendre java

    OriginalL'auteur sgokhales

  4. 5

    Tri de Shell améliore le tri par insertion en comparant les éléments séparés par un écart de plusieurs postes.

    Cela permet un élément à prendre "plus grand" à l'égard de la position prévue. Plusieurs passages sur les données sont prises avec de plus en plus petites tailles écart. La dernière étape de tri de Shell est une simple insertion de tri, mais d'ici là, le tableau de données est garanti d'être presque triées.

    Ce code peut vous aider dans la compréhension de la logique de mieux.

    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;
}
}
}
    La bonne réponse. 🙂
    Je pense que vous avez besoin pour commencer avec h dans la boucle: for(int i = h-1; i < un.longueur; i++). Causer d'autres sur j-h expression vous donnera -1 et le résultat sera un 0-l'utilisation du cycle.
    C'est en fait la Knuth de tri. Autres que le seul problème que je vois est la règle qui devrait être <= un.longueur / 3 n'est pas suivi dans votre algorithme. Il est supposé être h <= Math.ceil(un.longueur / 3) mais personne ne semble compter que.

    OriginalL'auteur ykombinator

  5. 3

    Ici est une visualisation de tri de shell pour un python de mise en œuvre:

    Tri de Shell exemple Java

    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")

    OriginalL'auteur slashdottir

  6. 2

    J'ai trouver la meilleure façon de comprendre tri de shell est de le décomposer en segments:

    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

    OriginalL'auteur benscabbia

  7. 1

    Voici un exemple:

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

    OriginalL'auteur Teknophilia

  8. 0

    Classique de type primitif de mise en œuvre:

    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.: Vérifier ce lien pour d'autres algorithmes de tri (ils sont en c++, cependant, facilement portable pour java).

    OriginalL'auteur Denys S.

  9. 0
    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 ++;
}
}
}
}

    liste est de type int[];
    GapArray prises de arcticle de Marcin Ciura
    http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf

    OriginalL'auteur user3593346

  10. 0

    Voici un lien vidéo: https://youtu.be/SCBf7aqKQEY
    Le gars a fait une bonne vidéo de tri de shell!!

    Et un code simple:

    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;
}
    Lorsque vous répondez à essayer de donner une description sur la façon de résoudre et comment il fonctionne.

    OriginalL'auteur Siddharth Arora

  11. 0

    Utiliser cette

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

    OriginalL'auteur JUNTAE