模板化快速/合併排序

我一直在嘗試在C++中編寫一個模板化函數，它可以接受任何類型的數組並對其進行排序。使用的排序必須是快速排序或合併排序，但是在實現其中的任何一種時遇到很多問題，因爲快速排序標題通常帶有頂部和底部參數，而合併排序帶有第一和最後一個參數。我的函數頭看起來像這樣：void mySort（T *陣列，INT N）模板化快速/合併排序

到目前爲止，我有這樣的：

template <typename T> 
void sort(T *a, int n) 
{ 
    int i = 0; 
    int j = n-1; 
    int tmp; 
    int pivot = a[(n-1)/2]; 
    while (i <= j){ 
    while (a[i] < pivot) 
     i++; 
    while (a[j] > pivot) 
     j--; 
    if (i<=j){ 
     tmp = a[i]; 
     a[i] = a[j]; 
     a[j] = a[i]; 
     i++; 
     j--; 
    } 
    } 

    if(0<j) 
    sort(a, j); 
    /* 
    if(i<right) 
    sort(
    */ 
}

我試圖用遞歸調用進行排序，但我不能找出如何爲所創建的正確分區調用遞歸，而無需使用不同的參數列表。

來源

2015-11-29 WashingtonSentinel

，還是你的代碼沒有他們，只有陣列和大小。爲什麼？ – VillasV

當n太小時，您還需要停止遞歸。例如，當'j == 1'滿意'0 JSF

如果您忽略了關於pivot元素結束位置的任何知識，並且忽略任何遞歸問題的終止，那麼第二個排序將是'sort（a + j，n-j）;'。（不是說你應該忽略這些東西，只是回答你似乎在問的問題）。 – JSF

在回答實際問題之前：您的代碼將受益於將分區代碼從函數體中分解出來！這樣一來，你會基本上是調用分區確定兩個陣列之間的中點被調用，也就是說，你有這樣的事情：

template <typename T> 
void sort(T* a, int n) { 
    T* mid = partition(a, n); 
    // ... 
}

的想法是，[a, mid)包含小排序的所有元素比樞軸和[mid, a + n)包含排序等於或大於樞軸的所有元素。所有剩下的就是

呼叫sort()遞歸與兩個陣列，即

sort(a, mid - a); 
sort(mid, (a + n) - mid);

確保sort()結束，如果獲得的陣列小大於2

中當然，如果你想要快速排序快速你還需要拉六打技巧。像：

使用Introsort保證複雜O(n lg n)（例如一起歸併排序）。
使用插入按小範圍排序。
使用分區和插入排序的實現來利用合適的標記。
直接排序真正的排序範圍。

其中奇怪的是玩是無用的事情是選擇一個樞軸。據我所知，使用中間元素以及任何更高級的技術（假設實現了上述那些優化）。

來源

2015-11-29 18:51:39

@rcgldr：當然 - 原文幾乎可以肯定地使用帶索引的數組。事實證明，使用指針實際上只是像'partition（）'和'qsort（）'這樣的算法。 –

刪除我之前的評論。對於這個特定的方案，當進行遞歸調用時，（i - j）== 1或（i - j）== 2，這取決於數據透視表旁邊的值。 – rcgldr

單獨從遞歸函數調用的函數：

// recursive function 
template <typename T> 
void quicksort(T *a, int lo, int hi) 
{ 
    // ... 
} 

// called function  
template <typename T> 
void sort(T *a, int n) 
{ 
    if(n < 2)return; 
    quicksort(a, 0, n-1); 
}

你已經知道，這兩類需要的第一和最後一個參數

來源

2015-11-29 20:06:51 rcgldr

模板化快速/合併排序

回答

相關問題