插入排序算法的缺陷

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