在C++中對整數的整數進行排序

Question

我必須製作一種按照從小到大的順序存儲整數的鏈表。 如果你有或知道如何爲鏈表創建一個排序功能，請在這裏顯示，如果不在這裏和/或教我如何用C++編寫它。

Answer 1

如果我們簡單地向您顯示代碼，我們將會對您造成很大損害。相反，我會給你兩種不同的方法，你可以實現你喜歡的方法。

第一種方法是「排序」爲你插入：當你插入值，也就是說，7，你按照這個過程開始在你的列表中的第一項，直到您運行的節點：

如果您正在檢查的節點的值大於7，則在檢查並返回的節點之前插入新的節點。否則，你看看下一個節點。如果沒有下一個節點，那麼。您在列表的末尾插入一個新節點，因爲這意味着7比列表中的其他條目大並且返回。

第二種方法是使用衆多排序算法之一對整個列表進行排序。我建議你使用BubbleSort，因爲它很容易理解和實現。你可以在維基百科上閱讀更多關於bubblesort（ans許多其他排序算法）。

Answer 2

我經常通過索引指針列表對鏈接列表進行排序。構建一個節點需要一個等於節點數（N）*的節點指針的大小。這個概念很簡單。

注：這種算法是C，因爲我不能完全肯定，如果OP意味着類這是一個C++的問題（誰是地獄採用在您的處置鏈接在C列出++與標準集裝箱??）

1. 確定列表
2. 分配一個指針陣列對於N節點指針節點的數目（N）。
3. 加載列表中每個節點指針的指針數組。即遍歷列表，並在指針數組的每個插槽中放置一個指針，隨着您的增加而遞增。
4. 發送該節點指針數組到您的排序算法（我喜歡的運行時庫qsort()因爲它是標準配備）。
5. 排序之後，遍歷整個指針數組（少一個），設置每個節點的「下一個」指針指向後面的一個。最後一個設置它的「下一個」指針爲NULL。
6. 設置頭指針是第一指針[0]的指針數組英寸
7. 免費的指針數組

的記憶你的鏈接列表進行排序。

---

假設你的節點是這樣的：

struct node 
{ 
    ..data fields.. 
    int keyField; // << determines sort order 
    struct node *next; 
}; 

確定您的列表中的節點數。我假設你有一個進程可以做到這一點，這是微不足道的：

size_t list_count(struct node* head) 
{ 
    size_t count = 0; 
    while (head) 
    { 
     ++count; 
     head = head->next; 
    } 
    return count; 
} 

分配一個指針數組列表，其中NITEMS是列表節點與困擾數大於1（沒有任何意義的大小長度零或一）的列表：

struct node **ptrs = malloc(sizeof(*ptrs)*nItems); 

填充指針數組與列表中的所有項：

struct node *ptr = head; 
size_t i=0; 
for (;i<nItems;++i,ptr = ptr->next) 
    ptrs[i] = ptr; 

現在提供一個appropria發送這qsort() te比較功能。該排序基於我們的結構keyField一個例子比較函數低於：

int compare_node_ptrs(const void* left, const void* right) 
{ 
    struct node *l = *(struct node**)left; 
    struct node *r = *(struct node**)right; 
    return l->keyField - r->keyField; 
} 

調用快速排序（）看起來是這樣的：

qsort(ptrs, nItems, sizeof(*ptrs), compare_node_ptrs); 

如今漫步整個列表。重新連線「下一個」指針：

for (i=0;i<(nItems-2);++i) 
    ptrs[i]->next = ptrs[i+1]; 
ptrs[nItems-1] = NULL; 

重新連接頭指針。

head = ptrs[0]; 

最後，釋放指針數組。

free(ptrs); 

你的鏈接列表進行排序。

---

邊欄合併排序是唯一的O（nlogn）算法，我知道的，可以進行排序，沒有額外的空間需求的鏈接列表。該原型以下的一般的解決辦法是Nutz的：

mergesort_list(void **head, size_t offset_ptr, int(*comp)(void*,void*)) 

head: address of the head pointer. 
offset_ptr: offset in bytes from a node ptr where the 'link' pointer can be found. 
comp: comparison function. 

Answer 3

好老quicksort會做的伎倆（C++ 03型）：

#include <algorithm> 
#include <functional> 
#include <iostream> 
#include <iterator> 
#include <list> 

using namespace std; 

void qsort(list<int>::iterator first, list<int>::iterator last) 
{ 
    if (distance(first, last) < 2) 
     return; 
    int pivot = *first; 

    list<int>::iterator it = partition(first, last, bind2nd(less<int>(), pivot)); 

    qsort(first, it); 
    qsort(it, last); 
} 

int main() 
{ 
    std::list<int> l; 
    l.push_back(5); 
    l.push_back(4); 
    l.push_back(1); 
    l.push_back(10); 
    l.push_back(3); 
    l.push_back(6); 
    l.push_back(7); 

    cout << "List:"; 
    copy(l.begin(), l.end(), std::ostream_iterator<int>(std::cout, " ")); 
    cout << endl; 

    qsort(l.begin(), l.end()); 

    cout << "Sorted list:"; 
    copy(l.begin(), l.end(), std::ostream_iterator<int>(std::cout, " ")); 
    cout << endl; 
    return 0; 
} 

檢查：http://ideone.com/OOGXSp