logo标签列表

如何对已排序的数组进行重新排序，其中一个元素被更新了

javaalgorithmsorting
5

我有一个固定大小的数组（实际大小为20），允许重复。例如：

1 2 2 3 3 4 5 6 7 8 9

现在只有一个元素更新：
1 5 2 3 3 4 5 6 7 8 9

我需要对这个数组进行排序。我应该使用冒泡排序吗？

更新 我不知道我写的是什么。但是我认为可能没有更快的排序方法了。欢迎留言！

    // array is already almost sorted and INCREASING, element at pos need to be inserted to the right place
    private void SortQuotes(List<Quote> quoteList, int pos)
    {
        var quoteToMove = quoteList[pos];
        if (pos == 0 || quoteList[pos - 1].Price < quoteToMove.Price)
        {
            MoveElementsDown(quoteList, pos);
        } else if (pos == quoteList.Count - 1 || quoteList[pos + 1].Price > quoteToMove.Price)
        {
            MoveElementsUp(quoteList, pos);
        }
    }

    private void MoveElementsDown(List<Quote> quoteList, int pos)
    {
        var quoteToInsert = quoteList[pos];
        var price = quoteToInsert.Price;
        for (int i = pos - 1; i >= 0; i--)
        {
            var nextQuote = quoteList[i];
            if (nextQuote.Price > price)
            {
                quoteList[i + 1] = quoteList[i];
                if (i == 0)   // last element
                {
                    quoteList[i] = quoteToInsert;
                }
            }
            else
            {
                quoteList[i + 1] = quoteToInsert;
                break;
            }
        }
    }

    private void MoveElementsUp(List<Quote> quoteList, int pos)
    {
        var quoteToInsert = quoteList[pos];
        var price = quoteToInsert.Price;
        for (int i = pos + 1; i < quoteList.Count; i++)
        {
            var nextQuote = quoteList[i];
            if (nextQuote.Price < price)
            {
                quoteList[i - 1] = quoteList[i];
                if (i == quoteList.Count - 1)   // last element
                {
                    quoteList[i] = quoteToInsert;
                }
            }
            else
            {
                quoteList[i - 1] = quoteToInsert;
                break;
            }
        }
    }

更新 我知道哪个元素是奇数，也就是说，它的位置已知！

在您的情况下，使用冒泡排序并不是太糟糕，但是定制的冒泡排序只需迭代一次列表（而不是N次），这将花费O(n)。 - Amir Pashazadeh
8个回答
1

这个解决方案将每个元素向右移动一个位置，直到找到奇数元素的正确位置。由于它已经在第一步中被覆盖，因此它保存在临时变量'h'中，然后写入最终位置。它需要最少的比较和移位操作：

 static void MoveOddElementToRightPosition(int[] a, int oddPosition)
 {
   int h = a[oddPosition];
   int i;
   if (h > a[oddPosition + 1])
     for (i = oddPosition; i < a.Count()-1 && a[i+1] <= h; i++)
        a[i] = a[i+1];
   else
     for (i = oddPosition; i > 0 && a[i-1] >= h; i--)
        a[i] = a[i - 1];
   a[i] = h;
 }
这与我在描述中写的几乎相同。然而，我认为这是正确的答案。 - Oleg Vazhnev
1
这只是向上移动。如果 A[OldPos] 恰好低于 a[OldPos-1] 呢？ - wildplasser
抱歉，我写这个的时候可能有点晚了。我会添加一个条件。 - alzaimar
0

你不需要再次排序。

只有一个元素发生了变化。所以你只需要遍历列表，将更改后的数字放到适当的位置。这将具有O(n)的复杂度。

int a[] = {1, 5, 2, 3, 3, 4, 5, 6, 7, 8, 9};
int count = 0;

//find the odd element
for(int jj=1; jj< a.length; jj++){
    if(a[jj] < a[count])
        break;
    else count++;
}
System.out.println(" Odd position "  + count);

//put odd element to proper position
for(int k= count+1; k<a.length; k++){
    if(a[count] > a[k]){
        int t = a[count];
        a[count] = a[k];
        a[k] = t;
        count++;
    }
}

以上是已经测试过给定输入的可工作代码。 祝您使用愉快。
谢谢，你的代码在每次迭代中都写入下一个将被重写的元素。最好只在最后一步写入“奇数”元素（如上述描述中的我的代码）。 - Oleg Vazhnev
1
你在第二个循环中使用了太多的赋值/交换操作。请看下面我改进后的代码： - alzaimar
同意，它并不是非常优化的。只是想要一个能工作的代码 :) - rai.skumar
0

这是一个简单的C语言实现。测试后请删除fprintf(stderr, ...。ITEM可以是任何东西，只要有比较函数即可。否则：使用ITEM指针（可能需要添加额外的sizeofelem参数，类似于qsort）。

#include <stdio.h>
#include <string.h>

typedef int ITEM;

int item_cmp(ITEM one, ITEM two);
unsigned one_bubble( ITEM *arr, unsigned cnt, unsigned hot , int (*cmp)(ITEM,ITEM) );

int item_cmp(ITEM one, ITEM two)
{
fprintf(stderr,"Cmp= %u to %u: %d\n", one, two, one-two);
if (one > two) return 1;
else if (one < two) return -1;
else return 0;
}

unsigned one_bubble( ITEM *arr, unsigned cnt, unsigned hot , int (*cmp)(ITEM,ITEM) )
{
unsigned goal = cnt;
int diff;
ITEM temp;

        /* hot element should move to the left */
if (hot > 0 && (diff=cmp( arr[hot-1], arr[hot])) > 0) {
        /* Find place to insert (this could be a binary search) */
        for (goal= hot; goal-- > 0; ) {
                diff=cmp( arr[goal], arr[hot]);
                if (diff <= 0) break;
                }
        goal++;
        fprintf(stderr,"Move %u LEFT to %u\n", hot, goal);
        if (goal==hot) return hot;
        temp = arr[hot];
                /* shift right */
        fprintf(stderr,"memmove(%u,%u,%u)\n", goal+1, goal, (hot-goal) );
        memmove(arr+goal+1, arr+goal, (hot-goal) *sizeof temp);
        arr[goal] = temp;
        return goal; /* new position */
        }
        /* hot element should move to the right */
else if (hot < cnt-1 && (diff=cmp( arr[hot], arr[hot+1])) > 0) {
        /* Find place to insert (this could be a binary search) */
        for (goal= hot+1; goal < cnt; goal++ ) {
                diff=cmp( arr[hot], arr[goal]);
                if (diff <= 0) break;
                }
        goal--;
        fprintf(stderr,"Move %u RIGHT to %u\n", hot, goal);
        if (goal==hot) return hot;
        temp = arr[hot];
                /* shift left */
        fprintf(stderr,"memmove(%u,%u,%u)\n", hot, hot+1, (goal-hot) );
        memmove(arr+hot, arr+hot+1, (goal-hot) *sizeof temp);
        arr[goal] = temp;
        return goal; /* new position */
        }
fprintf(stderr,"Diff=%d Move %u Not to %u\n", diff, hot, goal);
return hot;
}

ITEM array[10] = { 1,10,2,3,4,5,6,7,8,9,};
#define HOT_POS 1
int main(void)
{
unsigned idx;

idx = one_bubble(array, 10, HOT_POS, item_cmp);

printf("%u-> %u\n", HOT_POS, idx );

for (idx = 0; idx < 10; idx++) {
        printf("%u: %u\n", idx, array[idx] );
        }

return 0;
}
0

如果最后一个元素需要移动到前面，冒泡排序将需要n^2的时间。建议使用插入排序。

一次迭代的冒泡排序将需要 O(n) 的时间复杂度。 - Amir Pashazadeh
而且，如果错位的元素需要移动到列表的前面，只会将该元素向前移动一个位置。 - Imre Kerr
我忘了说我知道哪个元素是奇数的！ - Oleg Vazhnev
0

由于数组很小，插入排序对于小数组大约需要 ~O(n) 的时间，如果您只是更新一个值，插入排序应该是最好的选择。

插入排序不需要O(n)。 - rai.skumar
请参考：https://dev59.com/ImrWa4cB1Zd3GeqP_HXW - Rahul
它谈论的是已经排序的列表。但是这个列表并没有排序，有一个奇怪的元素。 - rai.skumar
这个列表已经接近排序完成了。你可以通过下面链接中的动画自行检查。选择你的数据集并点击左侧的刷新按钮。对于小数组和接近排序的数组，插入排序算法具有线性性能。http://www.sorting-algorithms.com/insertion-sort - Rahul
另外，如果您检查Arrays.sort()的jdk实现。您可以检查INSERTION_SORT_THRESHOLD，如果大小<threshold，则使用插入排序，否则使用归并排序。 目前threshold_size = 7 - Rahul
0

它可以在O(n)时间内完成。如果您不知道该元素，则在O(n)时间内搜索该元素，然后只需比较和交换每个元素即可，这需要O(n)时间。因此总共需要2n的时间，也就是O(n)时间。如果您知道已修改的元素，则只需比较和交换每个元素。

0
  • 如果您想快速替换元素，那么您也可以使用删除和插入速度快的结构，例如Java中的TreeSet。这意味着在理论上是O(log(n))，但如果您只操作20个元素的数组，则可能不值得。
  • 如果所有不同元素的集合是有限的，就像您的示例中只使用1到9的数字一样，那么有一个O(1)的解决方案。您只需保留一个包含元素出现次数的数组，而不是排序列表。
  • 如果您仍然想将所有内容保存在数组中，则最快的方法是：
    1. 通过二分法在O(log(n))中找到要删除的元素的位置A。
    2. 以同样的方式找到新元素要到达的位置B。更准确地说，B是新元素小于a[k]的最小索引，其中k > B。
    3. 如果A < B，则将A + 1和B之间的所有元素向左移动，然后将新元素设置为位置B。如果B > A，则执行相同的操作但向右移动。现在，此步骤的时间复杂度为O(n)，但没有逻辑，只是在移动内存。在C中，您可以使用memmove进行此操作，并且已经进行了大量优化，但我不知道是否有任何Java等效项。
我认为这里不需要二分搜索。无论如何，我都需要移动过时元素的组。因此，纯冒泡排序可能会更快，而不是使用二分搜索。 - Oleg Vazhnev
1
我们正在谈论算法，复杂度很重要。通常，通过迭代数组，比较和移动每个元素比寻找正确位置然后执行mem move更快。 - alzaimar
0

冒泡排序在这种情况下最多需要20次比较，还算可以。

但是使用二分查找来找到新位置的时间复杂度为O(log(n))，在这种情况下只需要5次比较。
如果你需要更快的速度，可以使用二分查找，否则你可以继续使用冒泡排序。

重点是，在冒泡排序时，我会更新数组。但是在找到位置后，我必须花费O(n)的操作来移动元素，因此冒泡排序更好。 - Oleg Vazhnev
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接