資料結構
網路
關係資料庫管理系統 (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 次瀏覽
