如何將以下非穩定排序算法轉換爲穩定？

考慮n表示標記牌爲紅色或藍色如何將以下非穩定排序算法轉換爲穩定？

  i=1; 
      j=n;     
      while(i<n) 
      { 
       if(a[i]==RED) 
       i++; 
       if(a[j]==BLUE) 
       j--; 
       swap(a[i],a[j]); 
      }

如何使這個原地算法穩定，我能得到一個爲O（n^2）解決問題，任何人都可以提出一個O（n）的解決方案？在O（N 2）

來源

2014-09-01 hitish

如果'a'數組只包含卡片顏色，爲什麼不計算它們然後通過填充適當的值來重新創建數組？ – rostok 2014-09-01 16:06:42

@rostok按照OP的建議，這將不再適用。 – dasblinkenlight 2014-09-01 16:17:57

這有幫助嗎？ http://csjobinterview.wordpress.com/2012/03/30/array-stable-partition/ – 2014-09-01 16:55:12

一種方法：

一個）的每個元素的索引附加到元素本身。

{ 「RED1」，「RED2」，「BLUE3」，「BLUE4」}

二）交換功能應該考慮的最後一個字符時，指數指標，當您嘗試交換兩個紅色或兩個藍色。

例如，：當你嘗試換兩張紅牌的球隊 - >只能換，如果indexOfFirst（RED）> indexOfSecond（RED）

藍調音樂一樣。

注意：您將需要添加一些額外的邏輯來查找它是否是藍色或紅色。

來源

2014-09-01 16:39:14 BatScream

計數排序

如果只有藍色和紅色你計數藍色元素和紅色元素

[b1 r1 r2 b2 b3 r3 r4 b4 r5]

，並在for循環中你算你你有blue: 4red: 5

然後要素你知道結果表是[ r r r r r b b b b] ，你可以知道索引範圍，其中紅色元素和藍色元素（last紅色元素是{} red_count -1和最後一個藍色元素是{red_count} + {} blue_count -1）保存此值redIndex和blueIndex

你做第二個表，並從循環結束你搜索元素，最後是R5它的紅色，那他的指數應該是4，你遞減redIndex

[b1 r1 r2 b2 b3 r3 r4 b4 __] blueIndex:8 
[__ __ __ __ r5 __ __ __ __] redIndex:3 

[b1 r1 r2 b2 b3 r3 r4 __ __] blueIndex:7 
[__ __ __ __ r5 __ __ __ b4] redIndex:3 

[b1 r1 r2 b2 b3 r3 __ __ __] blueIndex:7 
[__ __ __ r4 r5 __ __ __ b4] redIndex:2 

.....

項排序O（2N）更快的方式，但與巨大的內存使用情況時的各種數據

來源

2014-09-01 17:02:12 Sylwekqaz

如果我們允許使用額外的內存，只需執行2遍掃描：

第一遍：

count = 0 
foreach a[i] == RED 
    b[count ++] = a[i] 
    i ++

第二遍：

foreach a[i] == BLUE 
    b[count ++] = a[i] 
    i ++

最後複製a = b

總體而言，時間複雜度會O(3n) = O(n)。

來源

2014-09-01 19:10:54 nevets

如何將以下非穩定排序算法轉換爲穩定？

回答

相關問題