比較使用合併排序vs選擇排序

我有一個10 int的數組，並使用選擇排序我計算它需要大約45比較排序整個數組，但我不知道多少它需要排序使用合併排序通過我的計算，它需要12比較....我在這裏是對還是錯？比較使用合併排序vs選擇排序

在此先感謝

這裏的合併方法

static void merge(int[] first, int[] second, int[] a) 
    { 
     int iFirst = 0; 
     int iSecond = 0; 
     int i = 0; 
     //moving the smaller element into a 
     while(iFirst < first.length && iSecond < second.length) 
     { 
      if(first[iFirst] < second[iSecond]) 
      { 
       a[i] = first[iFirst]; 
       iFirst++; 
      } 
      else 
      { 
       a[i] = second[iSecond]; 
       iSecond++; 
      } 
      i++;    
     } 
     counter += i; 

     //copying the remaning of the first array 
     while(iFirst < first.length) 
     { 
      a[i] = first[iFirst]; 
      iFirst++; i++; 
     } 
     //copying the remaining of second array 
     while(iSecond < second.length) 
     { 
      a[i] = second[iSecond]; 
      iSecond++; i++; 
     }   
    }

來源

2012-05-26 miatech

要與m - 元素陣列合併的n - 元素數組，你需要在最壞的情況下n+m-1比較（min{m,n}中最好的）。

因此，當您將10個元素的數組分成兩半時，頂級合併需要多達9個比較。兩個5元素的一半需要最多4次比較，使得9 + 2*4 = 17。將2個元素和3個元素部分中的5個元素分割需要多達1 + 3個比較，因此總的最壞情況將是25個比較（9 + 2 * 4 + 2 * 3 + 2 * 1）。

   10(9)        9 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \ 
     /    \ 
     /    \ 
     5(4)    5(4)     8 
    / \   / \ 
    / \   / \ 
    3(2)  2(1)  3(2)  2(1)    6 
/ \ / \ / \ / \ 
    2(1) 1 1  1 2(1) 1 1  1    2 
/ \   / \ 
1  1   1  1

來源

2012-05-26 21:10:29

你是什麼意思，最壞的情況下，最後你仍然需要比較所有的數字，對不對？ – miatech

不一定。如果你將'[1,2,3,4,5]'與'[6,7,8,9,10]'合併在一起，那麼你只需要比較第一個數組的6個元素和5個元素，之後，不需要再進行比較。如果要合併的其中一個排序數組的最大元素（較短）要小於另一個的最小元素，那麼這是最好的情況。所以合併需要從'min {m，n}'到'm + n-1'比較。我答案中的樹給出了最差的數字。 –

確定這裏的東西，我試圖用這個數字計算一個合併排序算法的比較45 62 98 89 47 59 72 82 45 18，並且我得到26個比較，因爲你可以看到我的數字遍佈（順序明智）他們是隨機數（0-100），因爲我看着10個數字我認爲這是最糟糕的情況或者不是？ – miatech

比較使用合併排序vs選擇排序

回答

相關問題