вставки алгоритм сортировки ошибка в Java коде

Question

Так что я иду через некоторые из общих алгоритмов сортировки и написал это:

Код:

public void insertionSort() { 
    int key; 
    int i; 
    for (int j = 1; j < this.a.length; j++) { 
     key = a[j]; 
     i = j; 

     while (i > 0 && a[i-1] > key) { 
      a[i] = a[i-1]; 
      i = i - 1; 
     } 
     a[i] = key; 
    } 
} 

Результат:

jan@janspc:~/Dropbox/programming/java/algorithms$ javac sort.java 
jan@janspc:~/Dropbox/programming/java/algorithms$ java Test 
49, 68, 60, 14, 70, 8, 83, 96, 29, 7, 92, 35, 17, 84, 31, 62, 48, 95, 16, 22, 31, 97, 72, 55, 88, 63, 1, 63, 96, 32, 74, 15, 92, 77, 50, 13, 12, 36, 90, 93, 20, 15, 67, 88, 23, 31, 95, 90, 86, 65, 35, 27, 60, 4, 90, 11, 22, 97, 65, 88, 23, 1, 25, 21, 9, 81, 87, 56, 2, 4, 63, 52, 55, 86, 62, 30, 55, 64, 19, 10, 45, 92, 87, 43, 39, 95, 20, 43, 3, 30, 74, 64, 4, 90, 91, 93, 94, 44, 87, 21, 

49, 1, 1, 2, 3, 4, 4, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 17, 19, 20, 20, 21, 21, 22, 22, 23, 23, 25, 27, 29, 30, 30, 31, 31, 31, 32, 35, 35, 36, 39, 43, 43, 44, 45, 48, 50, 52, 55, 55, 55, 56, 60, 60, 62, 62, 63, 63, 63, 64, 64, 65, 65, 67, 68, 70, 72, 74, 74, 77, 81, 83, 84, 86, 86, 87, 87, 87, 88, 88, 88, 90, 90, 90, 90, 91, 92, 92, 92, 93, 93, 94, 95, 95, 95, 96, 96, 97, 97, 

Execution took: 110628 nano sek? 

Как видно из теста, первое значение не зависит от сортировки. Что случилось с моим алгоритмом?

Answer 1

В первой итерации цикл while не выполняется, поскольку i < 0. На следующей итерации цикл while не запускается, потому что i == 0.

Вы, вероятно, следует использовать while (i >= 0 && a[i] > key) (не тестировалось, хотя)

Answer 2

Вам нужно >= здесь:

while (i >= 0 && a[i] > key){ 

Без этого изменения он никогда не сравнится следующие элементы от первого.

Answer 3

while (i > 0 && a[i] > key){ должен быть while (i >= 0 && a[i] > key){

Успехов ...

Answer 4

Исправленный код:

public void insertionSort() { 
    int key; 
    int i; 
    for (int j = 1; j < this.a.length; j++) { 
     key = a[j]; 
     i = j; 

     while (i > 0 && a[i-1] > key) { 
      a[i] = a[i-1]; 
      i = i - 1; 
     } 
     a[i] = key; 
    } 
} 

Answer 5

Ниже псевдо-код сортировки Insertion (взятый из CLR «Введение в al горизм ").

погружного Сортировка (А)

для (J = 2 до a.length)

key = A[j]> 
i = j-1 
while i>0 && A[i]>key 
    A[i+1] = A[i] 
    i = i-1 
A[i+1] = key 

Ваш код практически аналогичен выше псевдокоде. Все, что вам нужно изменить инициализацию int j=0 к int j=1 в for цикле:

for (int j = 1; j < this.a.length; j++) { 
    key = a[j]; 
    i = j - 1; 

    while (i > 0 && a[i] > key) { 
     a[i + 1] = a[i]; 
     i = i - 1; 
    } 
    a[i+1] = key; 
} 

Answer 6

В Insertion Sort мы должны проверить каждый и каждый элемент из массива и сравнить с другим элементом получения более точного результата.Проблема в коде в то время как цикл мы должны выстраиваться

while (i >= 0 && a[i] > key) 

Answer 7

Вот еще одна реализация вставки рода в Java

общественного класса сортировка вставками {

static int intArray[] = { 1000, 1, 100, 101, 15 }; 

public static void doSort() { 
    for (int outer = 1; outer < intArray.length; outer++) { 
     for(int inner=outer;inner>0; inner--){ 
      if(intArray[inner]<intArray[inner-1]){ 
       int temp=intArray[inner]; 
       intArray[inner]=intArray[inner-1]; 
       intArray[inner-1]=temp; 
       continue; 
      } 
     } 
    } 
} 

public static void printArray() { 
    for (int i = 0; i < intArray.length; i++) { 
     System.out.print(" " + intArray[i]); 
    } 
} 

public static void main(String args[]) { 
    System.out.print("Array Before Sorting->"); 
    printArray(); 
    doSort(); 
    System.out.print("\nArray After Sorting ->"); 
    printArray(); 
} 

}

Подробное объяснение кода и/или альгортита можно посмотреть по адресу: http://www.javabrahman.com/algorithms-in-java/insertion-sort-in-java/

Answer 8

здесь очень просто реализация вставки рода

package insertion_sort; 

public class insertion_sort { 
    public static void main(String ar[]) { 
     int[] a = {24, 13, 9, 64, 7, 23, 34, 47, 87, 9, 37, 1992}; 
     insertion(a,12); 
    } 

    public static void insertion(int[] a, int n) { 
     for (int i = 1; i <= n - 1; i++) { 
      int value = a[i]; 
      int hole = i; 
      while (hole > 0 && a[hole - 1] > value) { 
       a[hole] = a[hole - 1]; 
       hole = hole - 1;  
      } 
      a[hole] = value; 
     } 
     print(a);  
    } 

    public static void print(int[] A) {  
     for (int i = 0; i < A.length; i++) {  
      System.out.print(A[i] + " ");  
     }  
     System.out.println(); 
    }  
} 

Answer 9

public static int[] insrtSort(int array[]){ 

    for(int i=0 ; i<array.length-1;i++){ 
     int value=array[i+1],k=i; 

     while(value<array[k]){ 

      array[k+1]=array[k]; 
      if(k!=0) 
      k--; 
      else 
       array[0]=value; 
     } 
     if(k!=0) 
     array[k+1]=value; 
    } 
    return array; 
    } 

Answer 10

Это тот же самый код, но как метод, который может быть передан массив Интс для сортировки.

public static int[] insertionSort(int[] array) { 
    int key; 
    int i; 


    for (int j = 1; j < array.length; j++) { 
     key = array[j]; 
     i = j; 

     while (i > 0 && array[i-1] < key) { 
      array[i] = array[i-1]; 
      i = i - 1; 
     } 
     array[i] = key; 
    } 
    return array; 
}