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

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}

=> merge(线性,附加线性内存)=>

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

编辑:如何合并两个阵列,没有额外的内存,看看这个答案

Answer 2

我的解决方案

1. 从数组和数组结束开始 2个指针.

2. 进入结果数组,从两个指针写入一个min(或者如果你需要以降序排序,则为max),并将指针移动到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更小.

现在我们已经为{16,15,13,​​14}排序了{10,11,12}和子问题(子问题的N减少了两次)

该算法的复杂度为:O(N)+(N/2)+ O(N/4)+ ...总是O(N)

图为更好的插图: