数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学单链表快速排序的JavaScript程序
单链表是一种线性数据结构，由节点组成。每个节点包含数据和指向下一个节点的指针，该指针包含下一个节点的内存地址，因为分配给每个节点的内存不是连续的。
排序是一种技术，通过这种技术，我们可以将特定数据结构（如链表、数组、向量等）的所有元素以递增或递减的顺序正确排序（如果未指定，则为递增顺序）。我们将在本文中看到正确的代码和解释。
问题介绍
在这个问题中，我们必须在单链表上实现快速排序算法。快速排序是一种排序算法或技术，它使用递归实现，最佳时间复杂度为 O(N * log(N))。
递归是快速排序算法的先决条件。递归是一种编程模式，其中我们定义一个函数，该函数将不断调用自身，其输入（作为参数传递）的值不断减小或增大。将存在一个基本条件，通过该条件递归调用结束。让我们在以代码格式实现之前，看看实现快速排序算法的步骤。
方法
为了在单链表上实现快速排序，我们将遵循以下步骤：
为了将枢轴节点放在正确的位置，我们将使用分区函数。
分区函数中的最后一个元素被标记为枢轴。
然后，我们将遍历当前列表，并将任何值大于枢轴的节点重新定位到尾部之后。如果节点的值较低，则应保留在其当前位置。
最后，我们将返回作为枢轴的节点。
我们将在枢轴的左侧找到链表的尾节点，并对链表的左侧重复此操作。
同样，在左侧之后，对枢轴节点右侧的链表重复此操作。
由于整个链表现在已排序，因此在连接左链表和右链表后返回链表的头节点。
示例
// 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);
时间和空间复杂度
上述代码的时间复杂度不是恒定的，完全取决于给定的输入，但平均而言，上述代码的时间复杂度为 O(N*log(N))，这也是当前排序算法的最佳情况。快速排序算法的最坏情况是 O(N*N)，这是无效的。
由于递归栈，上述代码的空间复杂度为 O(N)。
结论
在本教程中，我们实现了一个在单链表上进行快速排序的 JavaScript 程序。单链表是一种由节点组成的线性数据结构。快速排序是一种使用递归实现的排序算法或技术，其最佳和平均时间复杂度为 O(N * log(N))，递归是快速排序算法的先决条件。上述代码的时间复杂度最坏情况为 O(N*N)。
240 次浏览
