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;
            }
        }
    }

更新我确实知道哪个元素是奇怪的，即它的位置是已知的！

4

8 回答 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;
 }
于 2012-12-08T18:49:37.380 回答
0

如果最后一个元素需要到达前面，冒泡排序将使用 n^2 次。使用插入排序。

于 2012-12-08T10:22:12.200 回答
0

由于数组很小，对于小型数组，插入排序大约需要 ~O(n) 时间，如果您只是更新 1 个值，则插入排序应该以最好的方式实现您的目的。

于 2012-12-08T11:49:30.287 回答
0

It can be done in O(n). 如果您不知道该元素，则在 O(n) 中搜索该元素，然后您只需要比较和交换每个元素，这将花费 O(n)。所以总共 2n 这意味着 O(n)。如果您知道已修改的元素，然后比较并交换每个元素。

于 2012-12-08T12:02:11.953 回答
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++;
    }
}

以上是针对给定输入测试的工作代码。享受。

于 2012-12-08T12:42:20.957 回答
0
  • 如果您对快速替换元素感兴趣，那么您还可以使用删除和插入快速的结构，例如 Java 中的TreeSet。这在理论上意味着 O(log(n))，但如果你只是操作 20 个元素的数组，它可能不值得
  • 如果所有不同元素的集合是有限的，例如在您的示例中您只使用 1 到 9 的数字，那么在 O(1) 中就有一个解决方案。您只需保留一个包含元素出现次数的数组，而不是排序列表。
  • 如果您仍想将所有内容保存在数组中，那么最快的方法是
    1. 通过 O(log(n)) 中的二等分找到要删除的元素的位置 A。
    2. 找到新元素将以相同方式结束的位置 B。更准确地说，B 是每个 k > B 的 new_element < a[k] 的最小索引
    3. 如果 A < B，将 A + 1 和 B 之间的所有元素向左移动，然后将新元素设置到位置 B。如果 B > A，你做同样的事情，但向右。现在这一步在 O(n) 中，但没有逻辑，它只是移动内存。在 C 语言中，您可以使用 memmove 并对其进行了高度优化，但我不知道任何 Java 等价物。
于 2012-12-08T13:30:53.993 回答
0

在这种情况下，冒泡排序非常好，最多比较 20 次。

但是通过二分查找找到新位置是 O(log(n))，在这种情况下是 5 次比较。
稍微快一些，如果您需要最后一点奇数的速度，请使用二进制搜索，否则您可以坚持使用冒泡排序。

于 2012-12-08T16:26:42.550 回答
0

这是纯 C 中的一个幼稚实现。删除fprintf(stderr, ...后测试。只要有比较功能，ITEM 可以是任何东西。否则：使用指向 ITEM 的指针，（并且可能添加一个额外的 sizeofelem 参数，ala 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;
}
于 2012-12-08T19:08:29.063 回答