資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式實現連結串列上的歸併排序演算法
歸併排序技術基於分治法。我們將整個資料集分成更小的部分，然後以排序的順序將它們合併成更大的部分。它對於最壞情況也很有效，因為該演算法在最壞情況下也具有較低的時複雜度。
使用歸併排序可以非常有效地對連結串列進行排序。對於連結串列，合併任務非常簡單。我們可以簡單地更新連結來合併它們。在本節中，我們將瞭解如何使用這種方法對連結串列進行排序。
歸併排序技術的複雜度
時間複雜度 − 所有情況下均為 O(n log n)
空間複雜度 − O(n)
Input − The unsorted list: 14 20 78 98 20 45 Output − Array after Sorting: 14 20 20 45 78 98
演算法
mergeList(ll1, ll2)
輸入 − 它接受兩個連結串列 ll1 和 ll2
輸出 − 合併後的連結串列
Begin
if ll1 is empty, then
return ll2
if ll2 is empty, then
return ll1
if data(ll1) <= data(ll2), then
new_head = ll1;
next(new_head) = mergeList(next(ll1), ll2)
else
new_head = ll2;
next(new_head) = mergeList(ll1, next(ll2))
return new_head
Endsplit_list(start, ll1, ll2)
輸入 − 連結串列的起始指標，兩個輸出引數 ll1 和 ll2
輸出 − 從連結串列生成的兩個連結串列
Begin
slow := start
fast := next(start)
while fast is not null, do
fast := next(fast)
if fast is not null, then
slow := next(slow)
fast := next(fast)
end while
ll1 := start
ll2 := next(slow)
next(slow) := null
EndmergeSort(start)
輸入 − 連結串列
輸出 − 已排序的連結串列
Begin
head = start
if head is null or next(head) is null, then
return
split_list(head, ll1, ll2)
mergeSort(ll1)
mergeSort(ll2)
start := mergeList(ll1, ll2)
End原始碼 (C++)
#include<bits/stdc++.h>
using namespace std;
class node { //define node to store data and next address
public:
int data;
node *next;
};
void display(class node* start) {
node* p = start; // current node set to head
while(p != NULL) { //traverse until current node isn't NULL
cout << p -> data << " ";
p = p -> next; // go to next node
}
}
node* getNode(int d) {
node* temp = new node;
temp -> data = d;
temp -> next = NULL;
return temp;
}
node* mergeList(node* ll1, node* ll2) { //function for merging two sorted list
node* newhead = NULL;
if(ll1 == NULL)
return ll2;
if(ll2 == NULL)
return ll1;
//recursively merge the lists
if(ll1 -> data <= ll2 -> data) {
newhead = ll1;
newhead -> next = mergeList(ll1->next,ll2);
} else {
newhead = ll2;
newhead -> next = mergeList(ll1,ll2->next);
}
return newhead;
}
void splitList(node* start, node** ll1,node** ll2) {
//similar to flyod's tortoise algorithm
node* slow = start;
node* fast = start -> next;
while(fast!= NULL) {
fast = fast -> next;
if(fast!= NULL) {
slow = slow -> next;
fast = fast -> next;
}
}
*ll1 = start;
*ll2 = slow -> next;
//spliting
slow -> next = NULL;
}
void mergeSort(node** start) {
node* head = *start;
node* ll1,*ll2;
//base case
if(head == NULL || head->next == NULL) {
return;
}
splitList(head,&ll1,&ll2); //split the list in two halves
//sort left and right sublists
mergeSort(&ll1);
mergeSort(&ll2);
//merge two sorted list
*start = mergeList(ll1,ll2);
return;
}
int main() {
cout << "Creating the linked list: " << endl;
cout << "Enter 0 to stop building the list, else enter any integer" << endl;
int k,count = 1,x;
node* curr,*temp;
cin >> k;
node* head = getNode(k); //buliding list, first node
cin >> k;
temp = head;
while(k) {
curr = getNode(k);
temp -> next = curr;//appending each node
temp = temp -> next;
cin >> k;
}
cout<<"Before sorting: " << endl;
display(head); // displaying the list
cout<<"\nAfter sorting: " << endl;
mergeSort(&head);
display(head);
return 0;
}輸出
Creating the linked list: Enter 0 to stop building the list, else enter any integer 89 54 15 64 74 98 10 24 26 0 Before sorting: 89 54 15 64 74 98 10 24 26 After sorting: 10 15 24 26 54 64 74 89 98
更新於：2019年7月30日
瀏覽量 1K+
廣告