如何使用固定數據透視表將迭代快速排序更改爲使用隨機數據透視的迭代快速排序？

我發現這個代碼用於固定軸的快速排序。它總是以給定表格的右側元素作爲支點。我希望它將一個隨機元素作爲一個關鍵點。我認爲x是一個支點，所以我認爲將它改爲給定列表中的隨機元素是一個好主意，但事實證明它不起作用。如何使用固定數據透視表將迭代快速排序更改爲使用隨機數據透視的迭代快速排序？

void swap (int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 


int partition (int arr[], int l, int h) 
{ 
    int x = arr[h]; 
    int i = (l - 1); 
    for (int j = l; j <= h- 1; j++) 
    { 
     if (arr[j] <= x) 
     { 
      i++; 
      swap (&arr[i], &arr[j]); 
     } 
    } 
    swap (&arr[i + 1], &arr[h]); 
    return (i + 1); 
} 

void quickSortIterative (int arr[], int l, int h) 
{ 
    int stack[ h - l + 1 ]; 
    int top = -1; 

    stack[ ++top ] = l; 
    stack[ ++top ] = h; 

    while (top >= 0) 
    { 
     h = stack[ top-- ]; 
     l = stack[ top-- ]; 

     int p = partition(arr, l, h); 

     if (p-1 > l) 
     { 
      stack[ ++top ] = l; 
      stack[ ++top ] = p - 1; 
     } 
     if (p+1 < h) 
     { 
      stack[ ++top ] = p + 1; 
      stack[ ++top ] = h; 
     } 
    } 
}

我試圖改變線

int x = arr[h];

和

swap(&arr[i+1], &arr[j]);

到

int r = l+rand()%(h-l); 
int x = arr[r];

然後

swap(&arr[i+1], &arr[r]);

但它沒有正確排序。很明顯，我在這裏做錯了什麼。請幫忙。

來源

2013-03-20 raven_raven

任何理由遞歸被替換爲使用可變長度數組？它不會從堆棧溢出中拯救你。 – 2013-03-20 06:21:14

@Alexey Frunze這是我的大學鍛鍊。我應該比較不同種類的快速排序。遞歸的（無論是固定的還是隨機的）沒有問題，但迭代是一個問題來執行我。我結束了使用別人的代碼，導致不理解它。 – 2013-03-20 06:37:19

您的分區函數假定數據透視表位於分區的末尾。考慮先將隨機數據透視表移動到分區的末尾。

即選擇你的支點之後添加

swap(&arr[r], &arr[h]);

。

來源

2013-03-20 06:03:05

問題是，'分區'功能現在移動的關鍵點，因此它不保留在r索引。該函數也會丟失最後一個元素（索引爲h）。最簡單的解決辦法是把樞軸到最右邊的位置，只是選擇後，並保持其他的一切都是相同的：把swap(&arr[r], &arr[h]);第一循環之前在partition()，最後交換恢復到swap (&arr[i + 1], &arr[h]);

來源

2013-03-20 06:05:41 Inspired

如何使用固定數據透視表將迭代快速排序更改爲使用隨機數據透視的迭代快速排序？

回答

相關問題