不知道如何去執行Quicksort

-1

我正在嘗試在此進行快速排序以進行正式研究。但我不知道如何quicksort工作即時看着這個算法，但不知道現在使用冒泡排序什麼或如何實現它，但我如何繼續並實現quicksort？不知道如何去執行Quicksort

# choose pivot 
swap a[1,rand(1,n)] 

# 2-way partition 
k = 1 
for i = 2:n, if a[i] < a[1], swap a[++k,i] 
swap a[1,k] 
→ invariant: a[1..k-1] < a[k] <= a[k+1..n] 

# recursive sorts 
sort a[1..k-1] 
sort a[k+1,n]

這低於

int main() 
{ 
srand(time(NULL)); 
    int length = 250000; 
    double arr[length]; 
    for(int i = 0; i<length; ++i) arr[i] = rand(); 
    // mergeSort2(arr, arr+length-1); 


     for(int i = 0; i < (length-1); i++) 
    { 
     for(int j = i+1; j < length; j++) 
    { 
      if(arr[i] > arr[j]) 
      { 
       swap(arr[i], arr[j]); 
      } 
     } 
    } 

    ofstream ofs("input.txt"); 
    for(int i = 0; i<length; ++i) ofs << i << " " << arr[i] << endl; 
}

來源

2011-12-25 mystycs

你先看看這個嗎？ http://www.csanimated.com/animation.php?t=Quicksort – CppLearner 2011-12-25 04:57:16

現在看代碼沒有任何錯誤。人們通常在5秒鐘內就忘記了實際的實施。重要的是瞭解機制（QS的工作原理）。 – CppLearner 2011-12-25 04:58:32

不推薦使用Bubble Sort（或者甚至考慮）。無論如何，你的代碼有什麼問題？ – 2011-12-25 06:03:33

我的代碼，這是animation真的很有幫助。

快速排序的心臟（潛水命令與征服）僅僅是如下：

選擇一個元素作爲支點
- 在實踐大部分時間我們不」不在乎哪一個。正如你將會看到的那樣，隨機選擇一個樞軸（而不是前/後/中）將會最大限度地降低最壞情況下的可能性。
- 爲了測試目的，挑中間人是個不錯的選擇。
分區（L =左，R =右）

目標是原始的陣列劃分爲兩個集合（幾乎!!）

S_LEFT = {X中的S - {樞軸}：x小於或等於樞轉}

S_right = {S中X - {樞軸}：X大於或等於樞轉}

爲了簡化符號：
- a [1] .... a [i-1]小於或等於a [i]
- a [i + 1] ... a [r]大於或等於到[i]
- ，因此，最後，[i]（主元素）應該在其適當的位置。

策略

有到QS編程兩種常用的方法，但在一般QS採用三個參數（陣列，低，高），其中低是的左端索引陣列和高是陣列的右端指數（可能是2,3，5,10，不一定是0，長度爲1）

Initially 
l = low-1 
r = high 

advances l when A[l] less than or equal to pivot 
decrements r when A[r] is greater than or equal to pivot 
swap A[l] and A[r] 
repeat this process until l is greater than or equal to r, and swap (pivot, A[l]) 
Call QuickSort(A, left, l-1) 
Call QuickSort(A, l+1, right)

我給你最深的實施。只需在紙上畫一個小例子（9號尺寸似乎合理）即可。在你的實現正確之前不要使用rand。

試試這個數組：

myArray的= 9,6,2,5,11,4,20,1,3

我可以寫更多的明天。

來源

2011-12-25 05:37:39 CppLearner

不知道如何去執行Quicksort

回答

相關問題