数据结构
网络
关系数据库管理系统 (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+
广告