0

是否可以根据一个项目对列表进行排序？

例如，如果我有

1,3,2,4,5,6,7 ... 1000000

而且我知道这是第二个元素，3是否可以在不重新排序整个列表的情况下有效地排序3到它的正确位置？24

编辑：我还应该注意，在这种情况下，假设列表的其余部分已经排序；只是3现在不合适了。

4

6 回答 6

7

你可以简单地找到那个无序的对象（O（n）），取出对象（O（1）），找到正确的位置（O（n）），然后再次插入（O（1））。

假设 C++11，

#include <list>
#include <algorithm>
#include <iostream>

int main() {
    std::list<int> values {1, 2, 3, 9, 4, 5, 6, 7, 12, 14};

    auto it = std::is_sorted_until(values.begin(), values.end());
    auto val = *--it;
    // ^ find that object.

    auto next = values.erase(it);
    // ^ remove it.

    auto ins = std::lower_bound(next, values.end(), val);
    // ^ find where to put it back.

    values.insert(ins, val);
    // ^ insert it.

    for (auto value : values) {
        std::cout << value << std::endl;
    }
}

在 C++11 之前，您需要自己实现std::is_sorted_until.

于 2012-10-16T11:02:26.293 回答
1

对于这种非常有限的情况，编写自己的冒泡排序可能比 std::sort 更快。

于 2012-10-16T11:11:11.720 回答
0

If you think about the traversal possible for a list, it's clearly only end-to-end. So:

  • if you don't know where the mis-ordered element is you have to first scan through the elements one by one until you find it, then
  • you can remember the value and delete the out-of-order element from the list, then
  • there are two possibilities:
    • that element is greater in your sorting order than any other element you've yet encountered, in which case you need to keep going through the remaining elements until you find the correct place to insert it.
    • the element would belong somewhere amongst the elements you've already passed over, in which case:
      • you can move backwards, or forwards from the first element again, until you find the correct place to put it.
      • if you've created some records from your earlier traversal you can instead use it to find the insertion place faster, for example: if you've created a vector of list iterators, you can do a binary search in the vector. Vectors of every Nth element, hash tables etc. are all other possibilities.
于 2012-10-16T11:08:20.350 回答
0

这是如果你不使用std::list.

使用选择排序算法，selectionSort(list,3)如果您知道这是范围，您只需对项目 0 到 3 ( ) 进行排序。直到最后都不是整个范围。

示例代码：

#include <iostream>
using namespace std;



void selectionSort(int *array,int length)//selection sort function 
{
    int i,j,min,minat;
    for(i=0;i<(length-1);i++)
    {
        minat=i;
        min=array[i];
      for(j=i+1;j<(length);j++) //select the min of the rest of array
      {
          if(min>array[j])   //ascending order for descending reverse
          {
              minat=j;  //the position of the min element 
              min=array[j];
          }
      }
      int temp=array[i] ;
      array[i]=array[minat];  //swap 
      array[minat]=temp;

    }
}

void printElements(int *array,int length) //print array elements
{

    int i=0;
    for(i=0;i<length;i++)     cout<<array[i]<<"  ";
    cout<<" \n ";
}

int main(void)
{

    int list[]={1,3,2,4,5,6};   // array to sort 
    int number_of_elements=6;

    cout<<" \nBefore selectionSort\n";
    printElements(list,number_of_elements);      


    selectionSort(list,3); 

    cout<<" \nAfter selectionSort\n";
    printElements(list,number_of_elements);      


    cout<<" \nPress any key to continue\n";
    cin.ignore();
    cin.get();

   return 0;
}

输出：

Before selectionSort
1  3  2  4  5  6

After selectionSort
1  2  3  4  5  6

Press any key to continue
于 2012-10-16T12:15:22.863 回答
0

如果您有这样的知识水平，为什么不自己交换物品而不是试图强迫sort为您做呢？

当然这是更好的方法。

即使您不知道它必须去哪里，您也可以快速找到它，将其移除，然后将其插入正确的位置。

于 2012-10-16T11:02:32.603 回答
0

我想您可以使用该insert方法来移动元素，但我想更多地了解您计算其“正确”位置的方式：可能有更适合的算法。

于 2012-10-16T11:03:49.307 回答