如何在 Node.js 上编写快速排序
How to write quick sort on Node.js
我继续尝试在 Node 上写一个算法.js就像在 Algorithms, 4th ed. Sedgewick, Wayne 一书中一样。所有的例子都是用Java写的。
我有这个快速排序模块:
"use strict";
const _ = require('lodash');
module.exports = (function () {
function _partition(array, lo, hi) {
let i = lo;
let j = hi + 1;
let v = array[lo];
while (true) {
while (_less(array[++i], v)) {
if (i === hi) {
break;
}
}
while (_less(v, array[--j])) {
if (j === lo) {
break;
}
}
if (i >= j) {
break;
}
_exch(array, i, j);
}
_exch(array, lo, j);
return j;
}
function sort(array) {
_sort(array, 0, array.length - 1);
}
function _sort(array, lo, hi) {
if (hi <= lo) {
return null;
}
let j = _partition(array, lo, hi);
_sort(array, lo, j - 1);
_sort(array, j + 1, hi);
}
function _less(array, i, min) {
return array[i] < array[min];
}
function _exch(array, i, min) {
let temp = array[i];
array[i] = array[min];
array[min] = temp;
}
return {
sort: sort
};
})();
我使用摩卡和柴来测试这个函数:
function isSorted(array) {
for(let i = 1, size = array.length; i < size; i++) {
if (array[i] < array[i-1]) {
return false;
}
}
return true;
}
和快速排序不起作用。我需要与书中相同的实现,但在 js 上。
您可以在此处查看原始实现:Java 中的快速排序
这种实现很丑陋。
抱歉,我无法帮助您回答课程问题,但这是快速排序的功能递归版本的美妙之处。永远不要在javascript中使用上述内容。
在 ES6 中
功能递归快速排序。
const quicksort = ([head, ...tail]) => head === undefined ? [] :
[...quicksort([...tail.filter(a => a <= head)]), head, ...quicksort([...tail.filter(a => a > head)])];
用法
console.log(quicksort([1,3,1,0,6,8,9,12,15,22,54, 111,12,2,3,4,5,6,7,-1]));
你的函数_less
使用索引作为参数:
function _less(array, i, min) {
return array[i] < array[min];
但是你用数组元素值来调用它:
let v = array[lo];
while (_less(array[++i], v)
(并省略第一个参数array
- 在 JS 中合法吗?
<小时 />我能想到的最简单(最易读)的快速排序功能。
快速排序(可读性是重点)
<小时 />let quickSort = (items = [], left = [], right = []) => {
if (items.length <= 1) return items
let pivot = items.pop()
let pushToSide = item => (item < pivot ? left : right).push(item)
items.forEach(pushToSide)
return [...quickSort(left), pivot, ...quickSort(right)]
}
<小时 />注意:编写上述相同逻辑的另外两种方法如下
for 循环而不是 foreach
<小时 />let quickSort = (arr = [], left = [], right = []) => {
if (arr.length <= 1) return arr;
let pivot = arr.pop();
for (let i = 0; i < arr.length; i++)
(arr[i] < pivot ? left : right).push(arr[i]);
return [...quickSort(left), pivot, ...quickSort(right)];
}
<小时 />_ 在 items.forEach 中使用匿名回调函数进行快速排序,而不是传递callback_
变量
匿名ForEach
回调
<小时 /> let quickSort = (items = [], left = [], right = []) => {
if (items.length <= 1) return items;
let pivot = items.pop();
items.forEach(item => (item < pivot? left : right).push(item))
return [...quickSort(left), pivot, ...quickSort(right)];
}
<小时 />在js/node中创建的其他种类的简短列表.js以及对一些有用链接的引用
<小时 />
let sort = {
quick: (items = [], left = [], right = []) => {
if (items.length <= 1) return items
let pivot = items.pop()
let pushToSide = item => (item < pivot ? left : right).push(item)
items.forEach(pushToSide)
return [...sort.quick(left), pivot,...sort.quick(right)]
},
bubble: (items = []) => {
for (let passover = 0; passover < items.length; passover++)
{
for (let index = 0; index < items.length; index++)
{
if (items[index] > items[index + 1])
{
let temporary = items[index]
items[index] = items[index + 1]
items[index + 1] = temporary
}
}
}
return items;
},
select: (items = []) => {
for (let passes = 0; passes < items.length; passes++)
{
let min = passes
for (let i = passes; i < items.length; i++)
{
if (items[i] < items[min]) {
min = i
}
}
if (min !== passes) {
let temporary = items[passes]
items[passes] = items[min]
items[min] = temporary
}
}
return items
},
insert: (items = []) => {
for (let i = 1; i < items.length; i++)
{
let index = i-1
let temporary = items[i]
while (index >= 0 && items[index] > temporary)
{
items[index + 1] = items[index]
index--
}
items[index + 1] = temporary
}
return items
},
}
console.log('quick: ', sort.quick([0,43,3,2,3,4]))
console.log("select: ", sort.select([0,43,3,2,3,4]))
console.log("insert: ", sort.insert([0,43,3,2,3,4]))
console.log("bubble: ", sort.bubble([0,43,3,2,3,4]))
<ul>
<li>sort.quick O(n log n) avgerage time complexity</li>
<li>sort.bubble O(n^2) average time complexity</li>
<li>sort.insert O(n^2) average time complexity</li>
<li>sort.select O(n^2) average time complexity</li>
<li><a href="https://www.toptal.com/developers/sorting-algorithms">Watch how different sorting algorithms compare in real time</a></li>
<li>
<a href="https://bigocheatsheet.com">Time Complexity/Space Complexity cheat sheet</a></li>
</ul>
相关文章:
- 快速排序程序未正确输出
- 如何在节点中进行 Json 对象排序.js
- 为什么本机浏览器排序功能的工作速度比快速排序慢
- Javascript中的快速排序-错误过多的递归
- 无法确定 req.body.name 的值 - 快速节点 JS
- 可排序.js不起作用:列表项不可拖动
- 节点.js快速护照.js - 数据不会序列化
- Go 中的快速排序实现
- 有没有人有可以在对象上使用的 Javascript 快速排序
- 嵌套可排序.js toarray 不起作用
- 如何在 Node.js 上编写快速排序
- 如何根据本地存储中的变量快速排序
- Javascript Bug中的快速排序
- 对于我的快速排序算法,我如何使它对字符串和对象也进行排序
- Javascript快速排序算法实现
- 按特定字母排序JS字符串数组
- JavaScript 和 Java 中的快速排序
- 为什么这个功能版本的快速排序会中断?我该如何修复它
- JavaScript快速排序对象
- 如何在Redux中存储一个排序集,并根据不同的键对其快速排序