这里有新鲜出炉的 Javascript 教程,程序狗速度看过来!
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
这篇文章主要介绍了基于 JavaScript 实现的快速排序算法, 分析了快速排序的原理并结合实例形式给出了 javascript 快速排序的操作步骤与相关实现技巧, 需要的朋友可以参考下
本文实例讲述了基于 JavaScript 实现的快速排序算法。分享给大家供大家参考,具体如下:
首先要介绍一下冒泡排序,冒泡排序的过程很简单,首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个关键字交换,然后比较第二个和第三个,直到最后一个比较完成。这是第一趟冒泡,其结果使得关键字最大的记录被安置到最后一个位置上了。然后对序列前 n-1 个元素进行第二次冒泡,将倒数第二个选出。以此类推直到所有被选出,冒泡结束。
通过分析可以得出,冒泡排序的时间复杂度为 O(n2)。
快速排序是对冒泡排序的一种改进,它是处理大数据集最快的排序之一,通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列,不断重复该过程直到所有数据都是有序的。这个算法首先要选择一个基准值,围绕基准值进行。
示例如下:
算法思想如下:
选择一个基准元素,将列表分为两个子序列;
对列表重新排序,将所有小于基准元素的元素放前面,大的放后面;
分别对较小元素的子序列和较大元素的子序列重复上面两个步骤。
我们通过 js 实现代码如下:
- <!DOCTYPE html>
- <html lang="en">
- <head>
- <meta charset="UTF-8">
- <title>
- JavaScript快速排序
- </title>
- </head>
- <body>
- <script type="text/javascript">
- function qSort(nums) { //快速排序
- if (nums.length == 0) {
- return [];
- }
- var lesser = [];
- var greater = [];
- var pivot = nums[0]; //选择基准元素
- for (var i = 1; i < nums.length; i++) {
- if (nums[i] < pivot) { //分成两个之序列
- lesser.push(nums[i]);
- } else {
- greater.push(nums[i]);
- }
- }
- return qSort(lesser).concat(pivot, qSort(greater)); //递归
- }
- function show(nums) { //显示数组
- for (var i = 0; i < nums.length; i++) {
- document.write(nums[i] + ' ');
- }
- document.write('<br>');
- }
- var nums = [68, 80, 12, 80, 95, 70, 79, 27, 88, 93];
- show(nums); //newNums
- var newNums = qSort(nums); //希尔排序
- show(newNums); //0 0 2 3 4 5 5 6 8 9
- </script>
- </body>
- </html>
就平均时间而言,快速排序是目前被认为最好的一种内部排序方法。快速排序非常适用于大型数据集合,在处理小数据集时性能反而会下降。其时间复杂度为 O(nlog2n)
希望本文所述对大家 JavaScript 程序设计有所帮助。
(adsbygoogle = window.adsbygoogle || []).push({});
来源: http://www.phperz.com/article/17/0701/334041.html