arrays - 对先增后减的数组进行排序

Question

给定一个数组，该数组的元素按递增顺序排列，直到最大值，然后按递减顺序排列。

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

如何有效地对这个数组进行排序？

数组需要就地排序。

Answer 1

找到最大值，然后将数组反转到该值。然后对两个子数组应用合并 - 第一个包含最大值，然后是其余数组。这将具有线性计算复杂性并且需要线性附加内存。

在你的情况下：

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}

编辑：关于如何在没有额外内存的情况下合并两个数组，看看这个答案

Answer 2

我的解决方案：

1. 取 2 个指针start of array和end of array。

2. 将两个指针的最小值（或最大值，如果需要降序排序）写入结果数组，并将指针移到 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;
}

更新问题的解决方案：

作为解决方案，使用数组第一部分的部分排序。

(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 小一点。

现在我们已经对 {10, 11, 12} 和 {16, 15, 13, 14} 的子问题进行了排序（子问题的 N 减少了两倍）

该算法的复杂度为：O(N) + (N/2) + O(N/4) + ... 完全是 O(N)

图像更好地说明：

Answer 3

使用问题的属性。

您无需对已排序的数组进行排序。找到slope变化的点然后使用一个合适algorithm的来得到一个完整的排序数组。

您可以考虑实现一个有效使用此属性的双音分拣机。