JavaScript 对由0、1和2组成的链表进行排序
在本教程中,我们将学习使用JavaScript编写对由0、1和2组成的链表进行排序的程序。排序算法对于任何编程语言来说都是必不可少的,JavaScript也不例外。对由0、1和2组成的链表进行排序是开发人员在编程面试和实际应用中常遇到的问题。
下面让我们深入研究一下如何使用JavaScript编程对由0、1和2组成的链表进行排序。
什么是排序
排序是将元素按特定顺序排列的过程,可以是升序或降序。排序是计算机科学中的基本操作,在现实生活中有无数的应用场景。排序算法用于组织数据以进行高效搜索,减少冗余,并优化空间和时间复杂度。
下面是JavaScript中一些排序的示例:
示例1 - 对一个数字数组按升序进行排序:
Input: ar[]= [5, 3, 8, 1, 2, 9]
Output: [1, 2, 3, 5, 8, 9]
示例2 − 对字符串数组按字母顺序排序:
Input: ['apple', 'banana', 'orange', 'grape']
Output: ['apple', 'banana', 'grape', 'orange']
什么是链表
链表是一种线性数据结构,由指针连接在一起的节点组成。每个节点包含一个数据元素和对链表中下一个节点的引用。链表通常用于数据大小经常变化的动态数据结构。
问题描述
目标是对一个包含0、1、2的链表进行排序和显示。让我们通过示例来理解:
示例
Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL
Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL
Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL
将链表中的0、1和2排序的算法
使用计数排序算法对链表中的0、1和2进行排序的步骤如下:
步骤1 - 定义一个函数sortList(head),将链表的头部作为输入。
步骤2 - 初始化一个大小为3的计数数组count[],将所有元素都设为0。
步骤3 - 遍历链表并增加计数数组中相应索引处的节点数据的计数。
步骤4 - 再次遍历链表,并将节点数据替换为计数大于0的最小索引值。
步骤5 - 对每次替换的节点数据进行计数减少。
步骤6 - 打印排序前后的链表。
现在让我们通过一个使用JavaScript实现这个算法的示例来理解上述算法。
示例
下面的JavaScript程序使用计数排序算法对包含0、1和2的链表进行排序。该算法首先计算列表中0、1和2的频率,然后根据每个值的计数更新列表中的节点值。
/* Link list node */
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
push(new_data) {
const new_node = new Node(new_data);
new_node.next = this.head;
this.head = new_node;
}
printList() {
let currentNode = this.head;
let value = "";
while (currentNode !== null) {
value += currentNode.data + " -> ";
currentNode = currentNode.next;
}
console.log(value + "null");
}
sortList() {
const count = [0, 0, 0]; // Initialize count of '0', '1' and '2' as 0
let ptr = this.head;
while (ptr !== null) {
count[ptr.data] += 1;
ptr = ptr.next;
}
ptr = this.head;
let i = 0;
while (ptr !== null) {
if (count[i] === 0) {
++i;
} else {
ptr.data = i;
--count[i];
ptr = ptr.next;
}
}
}
}
const linkedList = new LinkedList();
linkedList.push(0);
linkedList.push(1);
linkedList.push(0);
linkedList.push(2);
linkedList.push(1);
linkedList.push(1);
linkedList.push(2);
linkedList.push(1);
linkedList.push(2);
console.log("Before sorting:");
linkedList.printList();
linkedList.sortList();
console.log("After sorting:");
linkedList.printList();
结论
总体而言,以上的Javascript程序展示了一种有效的方法来对只包含0、1和2的链表进行排序,使用计数技术。该算法的时间复杂度为O(n),空间复杂度为O(1),使其成为这个特定排序问题的最佳解决方案。