對首先增加然後減少的數組進行排序

Question

給定一個數組，它具有遞增順序的元素直到最大值，然後按遞減順序編號。

Eg. int a[] = { 10, 12, 14, 16, 15, 13, 11}. 

該數組如何有效地排序？

該數組需要在原地排序。

Answer 1

我的解決辦法：

1. 取2個指針數組的開始和陣列的結束。

2. 到Result陣列從兩個指針寫分鐘（或最高如果按降序排序需要）值，和 指針移位至1個位置（起始指針1位置和結束指針-1 位置

3. 重複直到開始指針將被放置結束後指針。

的溶液複雜度爲O（N）。 所需內存是O（N）

僞代碼：

function Sort(a) 
{ 
    startPointer = 0; 
    endPointer = a.length-1; 
    result = new Array of size a.length 
    while (startPointer <= endPointer) 
    { 
    var newValue; 
    if (a[startPointer] < a[endPointer]) 
    { 
     newValue = a[startPointer]; 
     startPointer +1 
    } 
    else 
    { 
     newValue = a[endPointer]; 
     endPointer -1 
    } 
    result[a.length - startPointer - endPointer] = newValue; 
    } 

    return result; 
} 

解更新問題：

作爲溶液USDE partil陣列的第一部分的分選。

指針（10和11） {10，12，14，16，15，13，11}

指針（12和11） 交換12和11 {10，11，14 ，16,15,13,​​12}

（14和12）上的指針 交換14和12 {10,11,12,16,15,13,​​14} //將指針從14移動到13 a它更小。

現在我們已經排序{10，11，12}，併爲子問題{16，15，13，14}（N爲子問題twicely降低）

複雜這個算法是：O（N ）+（N/2）+ O（N/4）+ ...完全是O（N）

圖片爲了更好地說明：

Answer 2

找到最大值，然後將數組倒轉到該值。然後在兩個子數組上應用一個合併 - 第一個包含最大值並且比其餘數組更大的合併。這將具有線性計算複雜度並且將需要線性附加內存。

在你的情況：

a[] = { 10, 12, 14, 16, 15, 13, 11} =>{10,12,14,16}, {15,13,11}

=>反向（直鏈的，就地）=>

{16,14,12,10}, {15,13,11}

=>合併（直鏈的，額外的線性存儲器）=>

{16,15,14,13,12,11,10}

編輯：對於如何在不額外內存合併到位兩個數組看看this answer

Answer 3

使用問題的屬性。你不需要排序已經排序的數組。找到slope更改的位置，然後使用合適的algorithm獲取完整的排序數組。

你可以考慮實施一個bitonic sorter，它有效地使用這個屬性。