JavaScript 快速排序链表程序

单链表是一种线性数据结构，由节点组成。每个节点包含数据和指向下一个节点的指针，该指针包含下一个节点的内存地址，因为每个节点分配的内存不是连续的。

排序是一种技术，通过它我们可以以递增或递减的方式将特定数据结构（如链表、数组、向量等）的所有元素正确排序。在本篇文章中，我们将看到相应的代码和解释。

问题介绍

在这个问题中，我们需要在单链表上实现快速排序算法。快速排序是一种使用递归实现的排序算法或技术，具有最佳的时间复杂度O(N * log(N))。

递归是快速排序算法的前提条件。递归是一种编程模式，在该模式中，我们定义一个函数，该函数将反复调用自己，输入的参数（作为参数传递的）不断减少或增加。递归调用将以基础条件结束。在实现代码格式之前，让我们看一下实现快速排序算法的步骤。

方法

为了在单链表上实现快速排序，我们将按照以下步骤进行操作：

使用partition函数使得主节点处于适当的位置。
- partition函数中的最后一个元素将被标记为主节点。
- 然后，我们将遍历当前列表，并将任何值大于主节点的节点重新定位到尾部。如果节点的值较低，则应保持不动。
- 最后，我们将返回作为主节点的节点。
我们将在主节点的左侧找到单链表的尾节点，并对左侧的链表重复此步骤。
类似地，按照左侧进行操作，对主节点右侧的链表重复此步骤。
由于整个单链表现在已经排序完成，我们在连接左侧和右侧链表后，返回链表的头部。

示例

// class to provide structure to the node 
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}

// defining the head of the linked list 
var head = null

// function to add a new node in a linked list 
function addNode(value) {
   var temp = new Node(value);
   if(head == null) {
   head = temp;
   }
   else{
      var current = head;
      while (current.next != null)      {
         current = current.next;
      }
      current.next = temp;
   }
}

// function to print all the elements of the linked list 
function print(head) {
   var temp = head;
   var ll = "";
   while (temp.next != null) {
      ll += temp.value + " -> "
      temp = temp.next;
   }
   ll += temp.value + " -> null"; 
   console.log(ll)
}

// function for partition of the linked list 
function partitionLast(first , last) {
   if (first == last || first == null || last == null)  {
      return first
   }
   var prev_pivot = first;
   var cur= first;
   var pivot = last.value;

   // traversing one node before the last 

   // as end is the pivot 
   while (first != last) {
      if (first.value < pivot) {
         prev_pivot = cur;
         var temp = cur.value;
         cur.value = first.value;
         first.value = temp;
         cur = cur.next;
      }
      first = first.next;
   }

   // swapping the positions
   var temp = cur.value;
   cur.value = pivot;
   last.value = temp;

   // as current is now pivot so return previous one 
   return prev_pivot
}
function quickSort(first, last) {
   // base condition 
   if (first == null || first == last || first == last.next){
      return; 
   }

   // split list and partition recurse
   var prev_pivot = partitionLast(first, last);
   quickSort(first, prev_pivot);

   // if pivot is moved to the start make both of them same 

   // which means we have to pick the new pivot 
   if (prev_pivot != null && prev_pivot == first){
      quickSort(prev_pivot.next, last);
   }

   // if pivot is in between of the list,

   // start from next of pivot,

   // since we have pivot_prev, so we move two nodes
   else if (prev_pivot != null && prev_pivot.next != null)  {
      quickSort(prev_pivot.next.next, end);
   }
}

// creating the linked list 
addNode(30);
addNode(3);
addNode(4);
addNode(20);
addNode(5);
var end = head;
while (end.next != null) {
   end = end.next;
}
console.log("Linked List before sorting");
print(head);
quickSort(head, end);
console.log("Linked List after sorting");
print(head);