对首先增加然后减少的数组进行排序

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，它有效地使用这个属性。