Пример сортировки оболочки Java

Question

Может кто-нибудь привести пример с сортировкой оболочки? Я новичок здесь, который должен узнать о сортировке оболочки, но сначала я должен найти пример сортировки оболочки Java. Я нашел один пример в Google, но это слишком сложно.

Answer 1

Вы пытались сначала прочитать статью в Википедии здесь ?Это обеспечивает довольно хорошие основы с иллюстрациями и примерами.

После этого вы можете проверить некоторые java-апплеты и анимации, изображающие этот процесс сортировки здесь .

Надеюсь, послечто, вы можете найти код java здесь , например, гораздо более читабельным.

Надеюсь, это поможет.

Answer 2

Здесь этот код очень прост:

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

Я украл его из книги под названием Структуры данных и анализ алгоритмов в 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 является простая сортировка вставкой, но к тому времени массив данных гарантированно будет почти отсортирован.

Этот код может помочь вам лучше понять логику.

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

Вот визуализация сортировки оболочки для реализации на 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 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

Вот пример:

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

Используйте это

 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 9

Вот ссылка на видео: 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 10

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 взят из арктики Марчина Чуры http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf