錯誤選擇排序

Question

我從現場開始，並有一個關於數組排序的問題。 我無法找到該程序沒有排序的原因 感謝您的幫助。

代碼

package sorting; 

public class selectionSort 
{ 
    public static void main (String[]args) 
    { 
     int []a={2,5,3,1,7,10,12}; 

     printArray(a); 
     insertSort(a); 
     printArray(a); 
    } 

    public static void insertSort(int[]array) 
    { 
     for(int i=0;i<array.length-1;i++) 
     { 
      int smallestIndex=i; 
      for(int j=i+1;j<array.length;j++) 
      { 
       if(array[smallestIndex]>array[j]) 
       { 
        smallestIndex=j ; 
       } 
       if(smallestIndex!= i) 
       { 
        int temp=array[smallestIndex]; 
        array[smallestIndex]=array[i]; 
        array[i]=temp; 
       } 
      } 
     } 
    }//insertSORT 


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

} 

Answer 1

插入排序算法進行這兩種方式，我的意思是你希望你的第一個for循環，從左至右，第二個自右向左走，從位置開始你我已經到了。 您檢查第一個for循環中的下一個數字，如果小於您想要查找其所屬位置的前一個數字，並將所有其他數字向右移動。

for(int i = 1; i < A.length; i++){ 
     if(A[i]<A[i-1]){ 
      for(int j = i; j > 0; j--){ 
       do{ 
        int x = A[j-1]; 
        A[j-1] = A[j]; 
        A[j] = x; 
       } while (A[j]<A[j-1]); 
      } 
     } 
    } 

Answer 2

這種類型排序的邏輯應該是：

• 查找數組中最小的數字，並把它擺在首位。
• 查找數組其餘部分的最小數字，然後放在第二位。
• 查找數組其餘部分的最小數字，並將其放在第三位。

依此類推。

這裏的問題是，你需要找到哪個號碼是該陣列的其餘部分的所有最小的，而你是最小的完成掃描後，才，你應交流與我個元素數量。

但是你的錯誤是你在掃描時交換了數值。

所以，先走一圈。

┌───┬───┬───┬───┬───┬────┬────┐ 
│ 2 │ 5 │ 3 │ 1 │ 7 │ 10 │ 12 │ 
└───┴───┴───┴───┴───┴────┴────┘ 
    0 1 2 3 4 5 6 

你我個元素是2，通過掃描，你會得到J = 3，1。您設置smallestIndex至3.然後你換的，現在你有

┌───┬───┬───┬───┬───┬────┬────┐ 
│ 1 │ 5 │ 3 │ 2 │ 7 │ 10 │ 12 │ 
└───┴───┴───┴───┴───┴────┴────┘ 
    0 1 2 3 4 5 6 

這種情況很好 - 但您仍在掃描。您的j現在轉到4，它指向7。第一個if是不正確的。你不改變smallestIndex。但是，當您到達第二個if時，其值仍爲3。因此，您現在將再次交換：

┌───┬───┬───┬───┬───┬────┬────┐ 
│ 2 │ 5 │ 3 │ 1 │ 7 │ 10 │ 12 │ 
└───┴───┴───┴───┴───┴────┴────┘ 
    0 1 2 3 4 5 6 

然後再次對於j = 5，然後再在j = 6時再回來。你最終以2回到老地方。

解決的辦法是移動交換外部j循環 - 在確定哪個索引是最小索引後，才交換它們。

public static void insertSort(int[] array) { 
    for (int i = 0; i < array.length - 1; i++) { 
     int smallestIndex = i; 
     for (int j = i + 1; j < array.length; j++) { 
      if (array[smallestIndex] > array[j]) { 
       smallestIndex = j; 
      } 
      // Not here! 
     } 
     // Do the swap outside the j loop. 
     if (smallestIndex != i) { 
      int temp = array[smallestIndex]; 
      array[smallestIndex] = array[i]; 
      array[i] = temp; 
     } 
    } 
} 

Answer 3

首先，選擇排序和INSERTION排序是兩種不同的算法。你的方法名稱是誤導性的。

有關於他們這裏實行信息： https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Selection_sort https://en.wikipedia.org/wiki/Selection_sort#Implementation https://en.wikipedia.org/wiki/Insertion_sort#Algorithm_for_insertion_sort