給定一個排序數組，其中有幾個數字在相反的位置。如何排序？

我實際上試圖解決一個問題，我有一個排序的數組，但少數數字是相反的。例如：1 2 3 4 9 8 7 11 12 14是數組。給定一個排序數組，其中有幾個數字在相反的位置。如何排序？

現在，我首先想到的是應用Binary Search算法來找到一個PEAK (a[i]>a[i+1] && a[i]>a[i-1])

不過，我覺得它可能不總是給出正確的結果。此外，由於列表幾乎排序，因此可能效率不高。

下一個印象：應用Insertion Sort因爲列表進行排序和插入排序給出了最好的性能在這種情況下，如果我沒看錯的。

所以任何人都可以提出更好的解決方案或者我的解決方案是否正確？高效的無效率？

P.S - 這不是功課！

UPDATE：插入排序（O（N）在這種情況下）或線性掃描以找到子序列，然後再次反轉它（O（N））。如果我們可以優化它，有沒有機會？或者可能在O（logn）中做？

來源

2012-07-30 h4ck3d

找到反轉運行的開始和結束並將其還原回去？ – wildplasser 2012-07-30 15:49:37

線性搜索第一個反轉（即a[i+1] < a[i]），將其索引稱爲inv1。繼續，直到倒數停止，稱爲最後一個索引inv2。反轉inv1和inv2之間的數組，包括（含）。

在您的例子，inv1爲4，inv2是6;數組元素從零開始編號。

該算法在原始條目數量上是線性的。

來源

2012-07-30 15:50:26 dasblinkenlight

不錯，所以那會是O（n + d）？ d是否。倒置？ – h4ck3d 2012-07-30 15:51:36

@sTEAK。它是'O（n）'，因爲'd'也是'O（n）'，O（2n）'和'O（n）'相同。:) – dasblinkenlight 2012-07-30 15:53:19

是的，這是正確的。我們可以在O（logn）中做到嗎？如果這樣的解決方案存在？ – h4ck3d 2012-07-30 15:55:57

如果你確定列表排序但是，被逆轉的嵌入式子，我建議你做一個簡單的掃描，檢測反向序列的開始（通過查找第一反方向變化），掃描到子序列的末尾（更改恢復正確的方向）並反轉子序列。這也應該適用於多個子序列，只要它們不重疊。複雜性應該是O（n）。

來源

2012-07-30 15:49:14

你能給出一個多個子序列的例子，這樣我就可以清楚了嗎？ – h4ck3d 2012-07-30 15:52:16

注意：應該有額外的決定是否在{4,9}之間或者在{9,8}之間切換。（I只需添加一個;-)

#include <stdio.h> 

int array[] = {1,2,3,4,9,8,7,11,12,14}; 

unsigned findrev(int *arr, unsigned len, unsigned *ppos); 
void revrev(int *arr, unsigned len); 

unsigned findrev(int *arr, unsigned len, unsigned *ppos) 
{ 
unsigned zlen,pos; 

for(zlen=pos=0; pos < len-1; pos++) { 
     if (arr[pos+1] < arr[pos]) zlen++; 
     else if (zlen) break; 
     } 
if (zlen) *ppos = pos - zlen++; 

return zlen; 
} 

void revrev(int *arr, unsigned len) 
{ 
unsigned pos; 
for (pos = 0; pos < --len; pos++) { 
     int tmp; 
     tmp = arr[pos]; 
     arr[pos] = arr[len] ; 
     arr[len] = tmp; 
     } 
} 

int main(void) 
{ 
unsigned start,len; 

len = findrev(array, 10, &start); 
printf("Start=%u Len=%u\n", start, len); 
revrev(array+start, len); 

for (start=0; start < 10; start++) { 
     printf(" %d", array[start]); 
     } 
printf("\n" ); 

return 0; 
}

注意：反向遊程的長度也可以通過一個二進制搜索的第一個值大於反轉序列的第一個元素較大（或相等）中找到。

來源

2012-07-30 16:15:05 wildplasser

Timsort是排序的主要爲已排序的陣列相當不錯 - 最重要的是，它並就地歸併使用兩種不同的mergesteps取決於這將更好地工作。我被告知它可以在python和java標準庫中找到，也許是其他的。儘管如此，你仍然可能不應該在一個循環內使用它 - 在一個循環內部，你最好使用一個treap（用於良好的平均速度）或紅黑樹（用於低標準偏差速度）。

來源

2012-07-30 17:10:15 user1277476

我認爲線性溶液[O（N）]是由於在正號的列表的最佳解決方案，如果n/2數的反向排序如實施例在下文中，我們將要反轉的n/2數其給出O（n）的複雜性。

即使在這種情況下，對於相似的序列，我認爲在最壞的情況下插入排序將是O（n^2）而不是O（n）。

實施例：考慮下面分佈的陣列，我們嘗試使用插入排序，

N/4排序號碼| n2反向排序的數字| n/4排序的數字

對於n/2個反向排序的數字，排序的複雜度爲O（n^2）。

來源

2012-08-04 02:45:41 Gaurang

給定一個排序數組，其中有幾個數字在相反的位置。如何排序？

回答

相關問題