javascript - 快速排序 Lomuto 算法
问题描述
我正在运行基于以下内容的 Lomuto Quicksort 算法的实现:https ://en.wikipedia.org/wiki/Quicksort
为了测试它,我尝试了几个数组来查看排序算法是否正确实现。
测试用例:
Array # 1: [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]
Array # 2: [11,8,14,3,6,2,7]
根据我对 Lomuto 算法的理解,这是来自 wikipedia 的代码:
function quickSort(array) {
// change code below this line
var n = array.length;
var low, hii;
low = 0;
hii = n - 1;
// console.log(sub_qs(array, low, hii));
array = sub_qs(array, low, hii);
console.log(array);
/***** Lomuto Algorithm Scheme *****/
function sub_qs(arr, lo, hi) {
if (lo < hi) {
var p = partition(arr, lo, hi);
sub_qs(arr, lo, p - 1);
sub_qs(arr, p + 1, hi)
}
return arr;
}
function partition(a, l, h) {
var pivot = a[h];
var i = l;
for (var j = l; j < h - 1; j++) {
if (a[j] < pivot) {
var temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
}
var temp_1 = a[i];
a[i] = a[h];
a[h] = temp_1;
}
return i;
}
/***** Lomuto Algorithm Scheme *****/
// change code above this line
return array;
}
运行程序后,我的结果是:
Results # 1: [1, 1, 8, 2, 32, 2, 63, 43, 55, 43, 123, 4, 92, 345, 123, 234, 5643]
Results # 2: [3, 6, 8, 7, 11, 2, 14]
有什么不对劲。我可能做错了什么?
解决方案
在您的分区中,第二个交换应该在for
循环之外,并且for
循环需要包含h - 1
因此使用for (var j = l; j < h; j++)
或for (var j = l; j <= h -1; j++)
:
function quickSort(array) {
// change code below this line
var n = array.length;
var low, hii;
low = 0;
hii = n - 1;
array = sub_qs(array, low, hii);
/***** Lomuto Algorithm Scheme *****/
function sub_qs(arr, lo, hi) {
if (lo < hi) {
var p = partition(arr, lo, hi);
sub_qs(arr, lo, p - 1);
sub_qs(arr, p + 1, hi)
}
return arr;
}
function partition(a, l, h) {
var pivot = a[h];
var i = l;
for (var j = l; j < h; j++) { // << need to be j < h not h - 1
if (a[j] < pivot) {
var temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
}
}
// this swap should be outside the above for loop <---
var temp_1 = a[i];
a[i] = a[h];
a[h] = temp_1;
return i;
}
/***** Lomuto Algorithm Scheme *****/
// change code above this line
return array;
}
let array1 = [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]
let array2 = [11, 8, 14, 3, 6, 2, 7]
console.log(quickSort(array1).join(','))
console.log(quickSort(array2).join(','))
推荐阅读
- android - 像 TikTok (XML) 这样的长按录制按钮动画?
- linux - 如何设置一个端口,以便当有人 netcats 到它时运行一个脚本
- javascript - Excel 公式到 javascript
- python - Dlib cuda 人脸检测 .dat 模型在 GTX 1650 上崩溃,而在许多其他 gpu 设备上表现良好
- python - 如何从缺少一些观察的索引中推断频率?
- android - 同时通过wifi(无互联网)和移动数据发送数据
- c# - 无法将值 NULL 插入到列“SchoolID”、表“TDC.dbo.SWprjectPart”中,这是从属下拉列表
- rest - 如何通过 gerrit rest api 获取访问具有特定组的 gerrit 项目?
- c# - 从 C# 中的 WSDL 生成的代码无法解析具有时区的日期
- javascript - Javascript/jQuery - 更改对象数据属性不会停止在 Chrome 中播放视频