Sắp xếp danh sách trong C ++

Giả sử chúng ta có một danh sách, chúng ta phải sắp xếp nó theo thời gian O (n logn) bằng cách sử dụng độ phức tạp không gian không đổi, vì vậy nếu danh sách giống như [4,2,1,3], thì nó sẽ là [1,2,3, 4]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức để hợp nhất hai danh sách theo thứ tự, sắp xếp, phương thức đó là merge (), điều này nhận hai danh sách l1 và l2.

• Phương thức danh sách sắp xếp sẽ hoạt động như bên dưới -

• nếu phần đầu là rỗng hoặc phần tiếp theo của phần đầu là rỗng, thì trả về phần đầu

• chậm:=đầu, nhanh:=đầu, và trước =null

• trong khi nhanh không phải là rỗng và tiếp theo của nhanh cũng không phải là rỗng, thực hiện

  • trước:=chậm

  • chậm:=tiếp theo của chậm

  • fast:=next of next of fast

• tiếp theo của trước:=null

• l1:=sortList (head)

• l2:=sortList (chậm)

• hợp nhất trả về (l1, l2)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
   int val;
   ListNode *next;
   ListNode(int data){
      val = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
void print_list(ListNode *head){
   ListNode *ptr = head;
   cout << "[";
   while(ptr){
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
   public:
   ListNode* sortList(ListNode* head) {
      if(!head || !head->next)return head;
      ListNode *slow = head, *fast = head, *prev = NULL;
      while(fast && fast->next){
         prev = slow;
         slow = slow->next;
         fast = fast->next->next;
      }
      prev->next = NULL;
      ListNode* l1 = sortList(head);
      ListNode* l2 = sortList(slow);
      return mergeList(l1,l2);
   }
   ListNode* mergeList(ListNode* l1, ListNode* l2){
      ListNode* temp = new ListNode(0);
      ListNode* p =temp;
      while(l1 && l2){
         if(l1->val<=l2->val){
            p->next = l1;
            l1 = l1->next;
         }else{
            p->next = l2;
            l2 = l2->next;
         }
         p = p->next;
      }
      if(l1){
         p->next = l1;
      }
      if(l2){
         p->next = l2;
      }
      return temp->next;
   }
};
main(){
   vector<int> v = {4,2,1,3,5,19,18,6,7};
   ListNode *h1 = make_list(v);
   Solution ob;
   print_list((ob.sortList(h1)));
}

Đầu vào

[4,2,1,3,5,9,8,6,7]

Đầu ra

[1, 2, 3, 4, 5, 6, 7, 18, 19, ]