插入排序算法的缺陷

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

下面是插入排序的僞代碼（取自CLR「Introduction to al gorithms「一書）。

插入排序（A）

爲（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 

您的代碼是上述僞代碼幾乎相似。所有你需要的是for循環改變int j=0初始化int j=1：

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循環 我們需要排隊

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

}

詳細解釋插入排序的另一種實現方式的代碼和/或algortithm可以看到 - 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; 
}