的std ::列表 - 排序一項

Question

是否有可能一個列表排序，基於關閉一個項目？

舉例來說，如果我有

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

我知道3是第二個元素，是可以有效地排序3到它的2和4之間的正確位置，而無需重新排序整個名單？

編輯：我還要指出的是，在這種情況下，假定列表的其餘是已排序;它只是3現在不合適。

Answer 1

你可以簡單地發現，無序的對象（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之前，您需要implement std::is_sorted_until yourself。

Answer 2

如果你有知識的人，水平，你爲什麼不只是交換自己的物品，而不是試圖強迫sort這樣做對嗎？

當然，這是一個更好的辦法。

即使你不知道知道它必須去的地方，你可以快速找到它，將其刪除，然後將它插入到正確的位置。

Answer 3

我想你可以使用insert方法來移動元素，但我想知道更多關於你計算它的「正確」位置的方式：可能有更好的算法。

Answer 4

如果你想遍歷可能的列表，它顯然是唯一的終端到終端。所以：

• ，如果你不知道在哪裏誤有序元素是你，直到你找到它，然後
• 你能記住的值，並刪除了先通過一個元素一個掃描-of順序從列表元素，然後
• 有兩種可能性：
  • 該元素是更大比你碰到的任何其他元素的排列順序，在這種情況下，你需要不斷經歷的其餘元素，直到找到插入它的正確位置。
  • 該元素將某處屬於你已經越過元素之中，在這種情況下：
  • • 可以向後從第一個元素再次移動，或向前，直到你找到正確的地方把它。
  • • ，如果你已經創建了你早先遍歷的一些記錄，你可以用它代替查找插入到位快，例如：如果你已經創建列表iterator s的vector，你可以做在vector中進行二進制搜索。每個第N個元素的向量，哈希表等都是其他可能性。

Answer 5

對於這種非常有限的情況下，編寫自己的冒泡很可能比的std ::排序更快。

Answer 6

這是如果你不使用std::list。

與選擇排序algorthm，只需排序項0至3（selectionSort(list,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