排序陣列中線性計時器和在適當位置

給出一個包含有對象與0 IDS大小爲n的一個未排序的陣列...，N-1中，代替和線性時間對數組進行排序。假設這些對象包含二進制數據等大型成員，因此實例化這些對象的新副本是非常昂貴的。

void linearSort(int* input, const int n) { 
    for (int i = 0; i < n; i++) { 
     while (input[i] != i) { 
      // swap 
      int swapPoint = input[i]; 
      input[i] = input[swapPoint]; 
      input[swapPoint] = swapPoint; 
     } 
    } 
}

這是線性的嗎？這種排序是否適用於任何種類的整數？如果是這樣，爲什麼我們需要快速排序？

來源

2012-01-05 JJ Liu

儘管在for內部有while循環，但這種排序是線性的O(n)。如果對於給定的i while循環出現多次，那麼對於匹配swapPoint的i值，根本不會執行while循環。

此實現僅適用於沒有重複項且值從0到n-1連續的整數的數組，因此Quicksort仍然與O(n log n)相關，因爲它適用於非順序值。

這可以通過使最壞的情況下，可以容易地測試：

input = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};

，然後使用以下代碼：

int whileCount = 0; 
for (int i = 0; i < n; i++) 
{ 
    while (input[i] != i) 
    { 
     whileCount++; 
     // swap 
     int swapPoint = input[i]; 
     input[i] = input[swapPoint]; 
     input[swapPoint] = swapPoint; 
    } 
    Console.WriteLine("for: {0}, while: {1}", i, whileCount); 
}

的輸出將是如下：

for: 0, while: 9 
for: 1, while: 9 
for: 2, while: 9 
for: 3, while: 9 
for: 4, while: 9 
for: 5, while: 9 
for: 6, while: 9 
for: 7, while: 9 
for: 8, while: 9 
for: 9, while: 9

所以即使在最糟糕的情況下，您也可以看到while循環運行在for循環的第一次迭代中，次，您仍然只獲得整個過程的while循環的n-1迭代。

用隨機數據進一步的例子：

{7, 1, 2, 4, 3, 5, 0, 6, 8, 9} => 2 on i=0, 1 on i=3 and nothing more. (total 3 while loop runs) 
{7, 8, 2, 1, 0, 3, 4, 5, 6, 9} => 7 on i=0 and nothing more (total 7 while loop runs) 
{9, 8, 7, 4, 3, 1, 0, 2, 5, 6} => 2 on i=0, 2 on i=1, 1 on i=2, 1 on i=3 (total 6 while loop runs)

來源

2012-01-05 10:13:02 Seph

謝謝，但我認爲while循環可能對特定的i執行多次，對吧？例如[2 0 1 3]，當i = 0時，它將執行兩次：首先使其變爲[1 0 2 3]，然後變爲[0 1 2 3]。 – 2012-01-05 11:05:00

這是完全正確的，但while循環在整個for循環中最多隻能運行n次。因此它是'O（N）'，不是更復雜。 – Seph 2012-01-05 11:15:43

我已經用一個例子更新了我的答案，這個例子顯示'while'循環中的內容只能在最多'n-1'次執行，而不管事先輸入的順序如何。 – Seph 2012-01-05 11:26:20

每次你把input[i]的位置swapPoint，這也正是它需要去。因此，在以下步驟中，這些元素已位於正確的位置，並且交換總時間不會超過n的大小。

來源

2012-01-05 11:32:14

排序陣列中線性計時器和在適當位置

回答

相關問題