3

给定一个不同整数的数组。您可以从数组中删除一个元素并将其附加到它的末尾。这是一次 MOVE，计为一次 MOVE 操作。找到对数组进行排序所需的最小移动次数。

4

3 回答 3

14

据我了解，将一个元素移动到末尾会移动该位置之后的所有元素，因此移动的第三个元素

[a_1, a_2, a_3, a_4, a_5, a_6]

最终产生

[a_1, a_2, a_4, a_5, a_6, a_3]

如果这种理解是正确的，那么最少步数的策略是

  1. 如果数组已排序，则停止。
  2. 找到出现在数组中较小元素之前的最小元素
  3. 将该元素移动到末尾

  4. 转到 1。

     Ex: 
  I/p: 8 6 1 7 5 2 3 9

 Process:
       8 6 1 7 2 3 9 5
       8 1 7 2 3 9 5 6
       8 1 2 3 9 5 6 7
       1 2 3 9 5 6 7 8
       1 2 3 5 6 7 8 9 -> sorted

   So totally 5 moves to be done to sort an array.

证明：随着每一步，按升序排列的最终排序数组的初始元素序列至少增加一个，因此算法终止。该算法仅在数组排序后终止。

每个数组元素最多移动一次。如果元素v在迭代中移动i，则所有元素<= v都按升序排列在数组中。移动任何元素> v都不会改变该相对位置，因此v不会被选为要在以后的任何迭代中移动的元素。

一个数组元素被移动当且仅当它至少和第一个被移动的元素一样大，比如v_1。

通过构造，移动的元素形成严格递增的序列，因此没有元素< v_1被移动。

移动后v_1，所有大于 的元素v_1都被放置在v_1数组中较小的元素（即，可能还有其他元素）之前。改变元素相对位置的唯一方法w > v_1是v_1移动w到末尾，因此w必须在某个步骤移动。

在任何排序序列中，所有元素>= v_1必须至少移动一次：

v_1必须在某个步骤中移动，因为在原始数组中有一个v_0 < v_1放置在之后的位置，并且改变andv_1顺序的唯一方法是移动。v_0v_1v_1

如上所述，所有w > v_1必须在移动后至少移动一次v_1。

可以在 O(n) 中找到所需的移动次数，但当然排序本身是二次的。

在找到第一个要移动的元素 之后v_1，只需计算k小于 的元素的数量v_1，则所需的移动次数为n - k。

v_1在O(n)中找到：（我本来以为是向前，结果是向后，如果向后，就很简单了。）

首先，从数组的末尾开始扫描，直到找到局部最小值或到达数组的开头。如果到达起点，则数组已经排序，无需移动。否则，将（局部）最小值的值和之前元素的值存储为暂定值 f v_1。然后继续前进，直到到达数组的开头，如果当前元素较小，则在每个步骤中更新最小值，如果v_1当前元素大于最小值但小于 tentative ，则更新 tentative v_1。

int move_count(int *a, int n) {
    int j = n-1;
    while(j > 0 && a[j-1] < a[j]) --j;
    if (j == 0) return 0;   // the array is already sorted
    // min_val holds the smallest element in the array after
    // the currently investigated position, v_1 holds the smallest
    // element after the current position that is larger than any later
    int min_val = a[j], v_1 = a[j-1];
    j -= 2;
    while(j >= 0) {
        if (a[j] < min_val) {
            min_val = a[j];
        } else if (a[j] < v_1) {
            v_1 = a[j];
        }
        --j;
    }
    int count_smaller = 0;
    for(j = 0; j < n; ++j) {
        if (a[j] < v_1) ++count_smaller;
    }
    return n - count_smaller;
}
于 2012-07-27T16:12:04.210 回答
1

解决方案将基于选择排序。看看http://www.sorting-algorithms.com/selection-sort中的这个动画，了解一下。这个想法很简单，就是在第 k 次迭代中找到第 k 个最大的元素，然后在那个元素上调用 MOVE。动画中也演示了找到这个元素。复杂度为 O(n)。

于 2012-07-27T05:09:32.000 回答
0

如果 MOVE 是唯一允许移动数组中元素的方法，那么选择排序就是将第 k 个元素 MOVE 移动到末尾并用第 k 次迭代中的第 k 个最小元素替换的方法。

最小移动操作 = 0（当数组已经排序时）。
最大移动操作 = n（当数组以所需的相反顺序排序时）。
因此，总移动操作 = O(n)。

排序算法的复杂度不变。

于 2012-07-27T13:20:57.587 回答