2016-03-20 244 views
0

我試圖使用一本書中的僞代碼(看起來像來自維基百科的一個僞代碼)來實現quicksort,但我無法讓它工作。快速排序不工作

此源代碼:

int partitionare(int a[], int n, int p, int r) 
{ 
    int x, i, j, aux; 
    x = a[r]; // pivot 
    i = p - 1; 
    for (j = p; j < r; j++) 
    { 
     if (a[j] <= x) 
     { 
      i++; 
      aux = a[j]; 
      a[j] = a[i]; 
      a[i] = aux; 
     } 
    } 
    aux = a[i + 1]; 
    a[i + 1] = a[r]; 
    a[r] = aux; 
    return i + 1; 
} 
void quicksort(int a[], int n, int p, int r) 
{ 
    if (p < r) 
    { 
     int q = partitionare(a, n, p, r); 
     partitionare(a, n, p, q - 1); 
     partitionare(a, n, q + 1, r); 
    } 
} 

,其中p和r是beggining和陣列

的結束和呼叫功能:

quicksort(a, n, 0, n-1); 

不介意第二參數這僅僅是爲了測試目的。

+2

你是什麼意思不工作?你看到的測試輸入結果是什麼? –

+0

Ups,對不起,我忘了提。 輸入:2,8,7,1,3,5,6,4 輸出:2,1,3,4,7,5,6,8 – Altair2033

回答

1

Accoding的功能quicksort()Wikipedia article最後調用自身遞歸(不是功能partition()

void quicksort(int a[], int n, int p, int r) 
{ 
    if (p < r) 
    { 
     int q = partitionare(a, n, p, r); 
     partitionare(a, n, p, q - 1);  /* recursive quicksort() here */ 
     partitionare(a, n, q + 1, r);  /* recursive quicksort() here */ 
    } 
} 
+0

我的上帝,它的工作原理。我的書也是如此,但有效的是,我失明瞭。而這個問題花了我10個小時。你先生,是一個拯救生命的人。非常感謝你。 :) – Altair2033