有沒有不好的代碼？ （C上的快速排序時間複雜度）

Question

void QuickSort(int* x, int first, int last) { 
    if (first >= last) 
     ; 
    else { 
     int pivotindex = Partition(x, first, last); 

     QuickSort(x, first, pivotindex - 1); 
     QuickSort(x, pivotindex + 1, last); 
    } 
} 

int Partition(int* x, int first, int last) { 
    int isbig = first + 1, issmall = last, tmp; 

    while (1) { 
     while (x[isbig++] < x[first] && isbig != last + 1);  // 

     while (x[issmall--] > x[first] && issmall != first); // 

     if (isbig < issmall) { //   tmp = x[issmall]; 
      x[issmall] = x[isbig]; 
      x[isbig] = tmp; 
     } 
     else { //   tmp = x[first]; 
      x[first] = x[issmall]; 
      x[issmall] = tmp; 

      break; // 
     } 
    } 

    return issmall; // 
} 

我對這段代碼有問題。我自己編碼。 它正在工作。但是這個問題比我所做的合併排序算法要慢。 我找不到問題所在。 （我知道作爲合併排序和快速排序的時間複雜度是不排序的數據相同，但對10,000個數據排序：time comparison ignore korean）

它比歸併排序的10倍。我認爲這意味着代碼不好。 但我找不到它在哪裏。 有什麼不好的代碼會使時間複雜性變得更糟嗎？

Answer 1

快速排序是O(n^2)在最壞的情況下，你在這裏看到。發生這種情況是因爲您使用數組的第一個元素作爲數據透視表並對排序後的數據進行排序，因此數組被分爲一個元素和n-1個元素。

爲了比較，mergesort總是O(n log n)。

而不是使用x[first]，您可以使用x[(first + last)/2]作爲關鍵。

請參閱：https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot