標籤：

如果不考慮空間， 如何使快排成為穩定的排序演算法？

01-08

rt

將要排序的元素Xi變成(Xi, i)然後做雙關鍵字快排不就好了。。

空間翻倍，時間基本不變（極限情況下所有Xi都相等那麼每次比較都要同時比較元素與下標，時間翻倍）

這些東西都是有bug的。。。。。

快速排序不穩定性是怎麼產生的？是因為在數組元素交換的過程中，會改變原有元素的順序。只要建一個循環

for(int i=0;i&

這樣在對A進行排序的時候，每一次當i和j的元素髮生交換的時候，同時交換B[i]和B[j]。

具體的實現過程，可以定義一個STABLE_FUNCTION函數

STABLE_FUNCTION(A,B,temp,D,K,K_temp)
{
int *count1=new int[k+1];
for(int i1=0;i1&1)
{
temp[j2]=B[i2];
j2++;
}
i2++;
}
COUNTING-SORT(temp,D,k_count); //執行計數排序

for(j2=0;j2&

void COUNTING-SORT(int A[n],int B[n],int k)
{
int *count=new int[k+1];
for(int i=0;i&<=k;i++) count[i]=0; for(int j=0;j&=0;j--)
{
B[count[A[j]]-1]=A[j];
count[A[j]]=count[A[j]]-1;
}
}

開額外O(n)空間.每輪partition都直接掃一遍l..r, 小於pivot的放一個數組,大於pivot的放另外一個數組. 然後再合併到原數組當中.這樣就是穩定的了

推薦閱讀：

※為什麼演算法中會出現magic number?
※如何評價noip2017day2？
※王宏志是誰？在他的背後又有哪些傳奇經歷？
※如何支持動態加滿足某種條件不定個數邊，在線判斷是否是二分圖（見問題描述）？
※平面上有N個點，如何選出3個點，使得他們組成的三角形面積最小/最大？

TAG:演算法 | NOIP | ACM競賽 |