插入排序輸出不符合預期

Question

我的插入排序輸出不正確。當我試圖調用insertionSort方法時，返回的數組未被排序

是否正確使用break語句？

public int[] insertionSort(int [] arr){ 
    for(int i=1;i<arr.length;i++){ 
     for(int j=0;j<=i-1;){ 
      int temp; 
      if(arr[i] < arr[j]){ 
       temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; 
       break; 
      } 
      else j++; 
      } 
     } 
     return arr; 
} 

調用的方法與int [] array = {10,5,6,7,1,9,3,8}，但結果是不正確的：

輸出排序後：1，3，7，8，5，10，6，9，//輸出未排序但它由有些

Answer 1

改變這裏是工作的代碼：

public static int[] insertionSort(int[] arr) { 
     for (int i = 1; i < arr.length; i++) { 
      int j = i; 
      while (j > 0 && arr[j] < arr[j - 1]) { 
       // Swap 
       int tmp = arr[j]; 
       arr[j] = arr[j - 1]; 
       arr[j - 1] = tmp; 

       j--; 
      } 
     } 
     return arr; 
    } 

一個個的您的代碼存在的問題是，您會將i-th元素置於正確的位置，但可能會弄亂已處於正確位置的元素的位置。

插入排序的想法是在正確的位置插入i-th元素，這意味着您必須將所有元素移動到右側。但是，在您的情況下，您只需在找到正確的位置後交換j-th元素和i-th。

的例子： 1 3 5 8 10這是數組 現在你嘗試插入元素6的當前狀態，你會發現正確的位置是3，所以你交換他們，結果是： 1 3 5 6 10 8它搞砸編號爲8的位置。