在不使用多個數組的情況下在C中執行Quicksort實現

-2

我想知道如何實現快速排序而不必創建額外的數組。然而，這個實現只在我使用1作爲關鍵點時才起作用。當我使用任何其他號碼時，程序段發生故障。我無法弄清楚哪個變量超出界限導致無限循環。對於此功能的任何批評/幫助，我將不勝感激。在不使用多個數組的情況下在C中執行Quicksort實現

void quick_sort(Item a[], int max, int pivot) 
{ 
    int i, j, p, t; 
    printf("%d", pivot); 
    if (max < 2) 
    { 
     return; 
    } 
    p = a[pivot]; 
    printf("%d", p); 
    for (i = 0, j = max-1;; i++, j--) 
    { 
     while (a[i] < p) 
     { 
      i++; 
     } 
     while (p < a[j]) 
     { 
      j--; 
     } 
     if (i >= j) 
     { 
      break; 
     } 
     t = a[i]; 
     a[i] = a[j]; 
     a[j] = t; 
    } 
    quick_sort(a, i, pivot); 
    quick_sort(a+i, max-i, pivot); 
}

來源

2015-04-27 Anthony Devoz

使用隨機函數從排序的每個階段的可用數字中選擇數據透視。去看看wikipedia的僞代碼 – softwarenewbie7331

您的程序，因爲段錯誤，如果你選擇了硬支點，就像2，舉例來說，如果quick_sort被稱爲分區中的只有2對陣列的正確的項目，a[2]將出界。

我認爲您的解決方案的最佳選擇是選擇函數內的數據透視表，可以是隨機的，也可以是任意值，如max/2。你只需要確保0 <= pivot < max：

void quick_sort(int a[], int max) 
{ 
    int pivot = max/2; 
    int i, j, p, t; 
    if (max < 2) 
    { 
     return; 
    } 
    p = a[pivot]; 
    for (i = 0, j = max-1;; i++, j--) 
    { 
     while (a[i] < p) 
     { 
      i++; 
     } 
     while (p < a[j]) 
     { 
      j--; 
     } 
     if (i >= j) 
     { 
      break; 
     } 
     t = a[i]; 
     a[i] = a[j]; 
     a[j] = t; 
    } 
    quick_sort(a, i); 
    quick_sort(a+i, max-i); 
}

來源

2015-04-28 01:30:47

的問題是在這兩條線：

quick_sort(a, i, pivot); 
quick_sort(a+i, max-i, pivot);

快速排序的工作原理是遞歸排序陣列的小部分。最終，你會發現數組中只有一個元素，這是遞歸基礎的情況。

問題是pivot值在數組收縮時通過所有調用傳遞下去。如果主鍵不是1，那麼總是最終會導致溢出（不管初始數組的大小如何）。

該樞軸需要選擇裏面的的遞歸函數。

來源

2015-04-28 01:34:02

在不使用多個數組的情況下在C中執行Quicksort實現

回答

相關問題