只需通過修改比較來使qsort穩定？

Question

可能重複：
Stabilizing the standard library qsort?

是否有可能只是通過修改我的補償運算，使爲整數的qsort穩定嗎？這是我的代碼。我正在使用這個大小約爲5-7的小數組。

static int compare(const void *a, const void *b) 
{ 
    const int A(*(const int*)(a)); 
    const int B(*(const int*)(b)); 

    return B - A; 
} 

Answer 1

如果您正在使用C++中，stable_sort性能穩定，並有O（nlogn）的性能。

否則，就地quicksort就其本質而言，不穩定（我相信如此）。然而，使用額外數組存儲信息的平凡變體是穩定的。

我用的qsort()是不穩定的至少一個版本，因爲一旦我發現，通過qsort()和stable_sort()我的機器上輸入的情況下產生的結果是不同的。

Answer 2

您不能採用不穩定的排序算法，如快速排序，只需通過更改比較運算符即可使其穩定。你必須開始與一個穩定的排序算法，然後比較並不重要（只要它是嚴格的C++弱排序）。

Answer 3

如果你正在排序的數組真的很小，那麼使用另一種排序算法可能會更好。見例如答案爲：Fast stable sort for small arrays (under 32 or 64 elements)和Fast algorithm implementation to sort very small list。