如何在一个元素更新的地方对已经排序的数组进行重新排序 [英] How to re-sort already sorted array where one element updates

问题描述

我有固定大小的数组(现实生活中大小为20)，允许重复例如:

I have array with constant size (size = 20 in real life), duplicates are allowed For example:

1 2 2 3 3 4 5 6 7 8 9

现在只更新一个元素:

1 5 2 3 3 4 5 6 7 8 9

我需要求助于此数组.我应该只用Bubblesort吗?

I need to resort this array. Should I just use bubblesort?

更新，我不知道该怎么称呼我写的东西.但是我想不可能更快地排序.欢迎发表评论！

update I don't know how to call what I wrote. But i suppose it is not possible to sort faster. comments are welcome!

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

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

updated i do know which element is odd, i.e. it's position is known!

推荐答案

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

This solution shifts each element by one until the right position for the odd element is found. As it has been overwritten already in the first step, it is saved in a temporary variable 'h' and then written to the final position. It requires the minimum of comparisions and shift operations:

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

这篇关于如何在一个元素更新的地方对已经排序的数组进行重新排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！