快速排序(Quicksort)的Javascript实现
日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。
这个周末,我就用它当做教材,好好学习了一下各种排序算法。
排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题之一。要想成为合格的程序员,就必须理解和掌握各种排序算法。
目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的。
"快速排序"的思想很简单,整个排序过程只需要三步:
(1)在数据集之中,选择一个元素作为"基准"(pivot)。
(2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。
(3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
举例来说,现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50},怎么对其排序呢?
第一步,选择中间的元素45作为"基准"。(基准值可以任意选择,但是选择中间的值比较容易理解。)
第二步,按照顺序,将每个元素与"基准"进行比较,形成两个子集,一个"小于45",另一个"大于等于45"。
第三步,对两个子集不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
下面参照网上的资料(这里和这里),用Javascript语言实现上面的算法。
首先,定义一个quickSort函数,它的参数是一个数组。
var quickSort = function(arr) {
};
然后,检查数组的元素个数,如果小于等于1,就返回。
var quickSort = function(arr) {
if (arr.length = 1) { return arr; }
};
接着,选择"基准"(pivot),并将其与原数组分离,再定义两个空数组,用来存放一左一右的两个子集。
var quickSort = function(arr) {
if (arr.length = 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2) ;
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
};
然后,开始遍历数组,小于"基准"的元素放入左边的子集,大于基准的元素放入右边的子集。
var quickSort = function(arr) {
if (arr.length = 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2) ;
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i arr.length; i++){
if (arr[i] pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
};
最后,使用递归不断重复这个过程,就可以得到排序后的数组。
var quickSort = function(arr) {
if (arr.length = 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i arr.length; i++){
if (arr[i] pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
使用的时候,直接调用quickSort()就行了。
(完)
前端工程师学 docker 看这个就够了 虽然是做前端的,但是有时候也会做一些和前端不太相关的事儿。 最近在工作中用到了 docker,配合运维同学为自己的node项目创建了一个 docker 镜像。
JavaScript高级函数之排序sort 排序算法作为各学校算法入门的必修课程,一定给各位留下过深刻的印象。不论是经典的冒泡排序、选择排序,还是当今最高效的快速排序,亦或者是比较有趣的栈排序、桶排序,都凝聚了前人过人的智慧和创造力。 不过随着高级语言的出现,似乎当今使用来看我们并不需要每次都自己手码排序算法。像python语言,内置的sorted函数和sort方法允许使用者直接调用来给选定序列排序,并且内部是用c语言基于快速排序编写的,运行效率和占用情况都大大高于我们手码排序算法。 JS也是这样一门高级语言,其带有sort函数可以直接给指定序列排序 今天就让我们一起了解一下js的sort有什么有趣的地方吧——
阮一峰 阿里技术专家。著名技术博客作者,技术方向为 React + Node,自由软件运动的支持者
相关文章
- 关于JavaScript的数组随机排序
- Javascript算法系列之快速排序(Quicksort)
- javascript some()函数用法详解
- [Javascript] Object mental model
- [Javascript] Customize Behavior when Accessing Properties with Proxy Handlers
- [WASM Rust] Use the js-sys Crate to Invoke Global APIs Available in Any JavaScript Environment
- [Javascript] Required function arguments in Javascript
- [Javascript] Using console.count to Count Events
- [Javascript + rxjs] Introducing the Observable
- [Cypress] install, configure, and script Cypress for JavaScript web applications -- part3
- 6 个用于排序数组的 JavaScript 代码片段
- SAP Spartacus TypeScript和编译后的JavaScript命名规范
- JavaScript 里三个点 ... 的用法
- Atitit.javascript 实现类的方式原理大总结
- 希尔排序(又称缩小增量排序,增量递减排序,ShellSort)的一个JavaScript实现
- JavaScript数组的常用方法总结:遍历,复制,反转,排序,添加,删除(前端常见面试题必考必问)实例演示
- 已解决selenium.common.exceptions.JavascriptException: Message: javascript error: Cannot read properties
- JavaScript实现数字前补“0”的五种方法示例
- 【 华为OD机试 2023】字符串重新排序(C++ Java JavaScript Python)
- leetcode 077. 链表排序 JavaScript
- JavaScript字符串排序localeCompare()笔记
- JavaScript 冒号(:)详解
- JavaScript数组的常用方法总结:遍历,复制,反转,排序,添加,删除(前端常见面试题必考必问
- 开源?Highcharts JS 10.3.2 | Highcharts Javascript