在链表上实现归并排序算法的 C++ 程序

2023-06-20 12:21:03 263

归并排序技术基于分治技术。我们将while数据集分成更小的部分，并按排序顺序将它们合并为一个更大的部分。它对最坏情况也非常有效，因为该算法在最坏情况下也具有较低的时间复杂度。

链表可以非常有效地使用归并排序进行排序。对于链表，合并任务非常简单。我们可以简单地更新链接以合并它们。在本节中，我们将看到如何使用这种方法对链表进行排序。

归并排序技术的复杂性

时间复杂度-O(nlogn)适用于所有情况

空间复杂度-O(n)

Input − The unsorted list: 14 20 78 98 20 45Output − Array after Sorting: 14 20 20 45 78 98

算法

合并列表(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
End

split_list（开始，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
End

mergeSort(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
using namespace std;
class node { //定义节点来存储数据和下一个地址
   public:
   int data;
   node *next;
};
void display(class node* start) {
   node* p = start; //当前节点设置为头部
   while(p != NULL) { //遍历直到当前节点不为空
      cout << p -> data << " ";
      p = p -> next; //转到下一个节点
   }
}
node* getNode(int d) {
   node* temp = new node;
   temp -> data = d;
   temp -> next = NULL;
   return temp;
}
node* mergeList(node* ll1, node* ll2) { //合并两个排序列表的函数
   node* newhead = NULL;
   if(ll1 == NULL)
      return ll2;
   if(ll2 == NULL)
      return ll1;
   //递归合并列表
   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) {
   //类似于flyod的乌龟算法
   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;
   //基本情况
   if(head == NULL || head->next == NULL) {
      return;
   }
   splitList(head,&ll1,&ll2); //将列表分成两半
   //排序左右子列表
   mergeSort(&ll1);
   mergeSort(&ll2);
   //合并两个排序列表
   *start = mergeList(ll1,ll2);
   return;
}
int main() {
   cout << "创建链表： " << 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);   //构建列表，第一个节点
   cin >> k;
   temp = head;
   while(k) {
      curr = getNode(k);
      temp -> next = curr;//附加每个节点
      temp = temp -> next;
      cin >> k;
   }
   cout<<"排序前： " << endl;
   display(head); //显示列表
   cout<<"\nAfter sorting: " << endl;
   mergeSort(&head);
   display(head);
   return 0;
}

输出结果

创建链表：
Enter 0 to stop building the list, else enter any integer
89
54
15
64
74
98
10
24
26
0
排序前：
89 54 15 64 74 98 10 24 26
After sorting:
10 15 24 26 54 64 74 89 98