的Java：選擇排序我的實現與另一

下面是我的實現選擇排序的：的Java：選擇排序我的實現與另一

package algorithm.selectionsort; 

public class SelectionSort { 

    public static void main(String[] args) { 
     int[] myArray = selectionSort(new int[] { 9, 9, 9, 8, 7, 73, 32, 109, 1100, 432, 321, 0 }); 

     for (int element : myArray) { 
      System.out.print("" + element + " "); 
     } 

    } 

    public static int[] selectionSort(int[] a) { 
     int min; 
     for (int i = 0; i < a.length - 1; i++) { 
      min = i; 
      for (int j = i + 1; j < a.length; j++) { 
       if (a[j] < a[min]) { 
        min = j; 
        int temp = a[i]; 
        a[i] = a[min]; 
        a[min] = temp; 

       } 
      } 
     } 
     return a; 

    } 

}

我發現我的導師代碼它略有不同：

public static int[] selectionSort(int[] a) { 
    int min; 
    for (int i = 0; i < a.length - 1; i++) { 
     min = i; 
     for (int j = i + 1; j < a.length; j++) { 
      if (a[j] < a[min]) { 
       min = j; 


      } 
     } 
     int temp = a[i]; 
     a[i] = a[min]; 
     a[min] = temp; 
    } 
    return a; 

}

兩種實施工作。我很好奇這裏有什麼不同。效率如何？

來源

2017-08-29 Dewey Banks

我明白了 - 我不必要地一遍又一遍地重複相同的代碼。效果是一樣的，但這會讓我放慢抓取龐大的數據集。 –

你的老師實現了選擇排序，你發明了另一種看起來非常相似但效率較低的排序。 – alfasin

https://codereview.stackexchange.com – nullpointer

你的導師和你的導師之間的區別在於他遍歷數組，並且對於每個元素，搜索最小值，然後在牆索引之後與元素進行交換。

對於你的，你遍歷數組和每個元素，同時搜索最小值，如果當前值是<那麼當前暫定最小值，與牆索引之後的元素進行交換。

所以不是換了N次，你可以可以互換N * N次，最糟糕的情況：

你只是一個通（最壞情況）掉期：

100, 90, 88, 70, 55, 43, 32, 28, 19, 10 
90, 100, 88, 70, 55, 43, 32, 28, 19, 10 
88, 100, 90, 70, 55, 43, 32, 28, 19, 10 
70, 100, 90, 88, 55, 43, 32, 28, 19, 10 
55, 100, 90, 88, 70, 43, 32, 28, 19, 10 
43, 100, 90, 88, 70, 55, 32, 28, 19, 10 
32, 100, 90, 88, 70, 55, 43, 28, 19, 10 
28, 100, 90, 88, 70, 55, 43, 32, 19, 10 
19, 100, 90, 88, 70, 55, 43, 32, 28, 10 
10, 100, 90, 88, 70, 55, 43, 32, 28, 19

你的教練的交換隻是一次通過（最糟糕的情況）：

100, 90, 88, 70, 55, 43, 32, 28, 19, 10 
10, 90, 88, 70, 55, 43, 32, 28, 19, 100

實質上，您在搜索最小值的同時交換值。您交換的「min」可能不是數組中的最小值。

來源

2017-08-29 02:45:53 user3437460

ofcouse of your instructor's code is more efficiency and more elegant。什麼是選擇排序？

該算法將輸入列表分爲兩部分：已經排序的項目的子列表，其從列表的前部（左側）從左到右構建，以及剩餘的待排序項目的子列表佔據了名單的其餘部分。最初，排序的子列表是空的，未排序的子列表是整個輸入列表。該算法通過查找未排序子列表中最小（或最大，取決於排序順序）元素，與最左邊未排序元素交換（交換）它（按排序順序），並將子列表邊界移動到對。

如果要排序的列表的長度爲ñ，那麼就ň交換的時候應該做的，但在你的代碼，它是N *（N-1）*（N- 2）....

來源

2017-08-29 02:49:53 Javdroider

的Java：選擇排序我的實現與另一

回答

相關問題