文档章节

js常用排序之冒泡排序、快速排序

会写代码的husky
 会写代码的husky
发布于 2017/03/15 10:24
字数 543
阅读 34
收藏 1

     一、冒泡排序

       原理:每一次比较数组中相邻的两个数据大小,如果前一个数据大于后一个数据,就交换这两个数据的位置。

        特点:简单易于理解,但比较次数多,效率差。 

var times = 0;  // 用于计算排序次数
var bubbleSort = function(arr) {
	var temp;
	for(var i = 0; i < arr.length - 1; i++){
		for(var j = i+1; j < arr.length; j++){
			if(arr[i] > arr[j]) {
				/* 如果前者大于后者,则先将前者存储于一个变量中,
				 * 然后将后者放置于前者的位置,再将变量中的数据
				 * 放于后者的位置,达到交换的目的
				*/
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				times++;
			}
		}
	}
	return arr;
}
bubbleSort(arr);     // arr数组长度为1000
console.log(times);  // 250855 排序次数

        结果:长度为1000的数组,冒泡排序的次数为250855次

 

     二、快速排序

        原理:取一个数组的中部为基准点,将数组中每一个数据与基准点比较,比它小的放进左边的一个空数组,比它大的放进右边的一个空数组,然后对左右数组进行递归操作,直至数组长度 <=1。

        特点:效率好,常用,但递归一次就要另外声明两个数组,占用了内存。

var times = 0;  // 用于计算排序次数
var quickSort = function(arr) {
	// 如果递归数组至长度为1,就停止排序返回
	if(arr.length <= 1) {
		return arr;
	}
	// 取数组基准点
	var midIndex = Math.floor(arr.length/2);
	var midValue = arr.splice(midIndex,1);
	// 用左右两个空数组接收小于基准点的数据与大于基准点的数据
	var leftArr = [];
	var rightArr = [];
	for(var i=0; i < arr.length; i++){
		if(arr[i] < midValue) {
			leftArr.push(arr[i]);
		}else {
			rightArr.push(arr[i]);
		}
		times++;
	}
	// 递归操作
	return quickSort(leftArr).concat(midValue,quickSort(rightArr));
};

quickSort(arr);
console.log(times); // 10260 排序次数

        结果:长度1000的数组,快速排序次数为10260次。

 

      总结:同样为长度1000的数组,快速排序的性能比冒泡排序的性能高了二十多倍。但是随着数组长度的缩小,这个比例也会缩小,但就效率来说,快速排序始终是比冒泡排序快的。

© 著作权归作者所有

共有 人打赏支持
会写代码的husky
粉丝 6
博文 23
码字总数 17052
作品 0
北京
程序员
私信 提问
六种排序算法的JavaScript实现以及总结

最近几天在系统的复习排序算法,之前都没有系统性的学习过,也没有留下过什么笔记,所以很快就忘了,这次好好地学习一下。 首先说明为了减少限制,以下代码通通运行于Node V8引擎而非浏览器,...

DM.Zhong
2018/05/24
0
0
JavaScript 排序算法

基础构造函数 以下几种排序算法做为方法放在构造函数里。 1. 冒泡排序 代码 图解 2. 选择排序 代码 图解 3. 插入排序 代码 图解 4. 归并排序 代码 图解 5. 快速排序 代码 图解 6. ECMAScrip...

唯情
2017/10/27
0
0
JavaScript数据结构与算法(排序算法)

比较排序算法一般有三个指标 时间复杂度, 算法执行完成所需要的时间 空间复杂度, 算法执行完成所需要的空间 稳定性,当二个元素的值相同的时候,排序之后二个元素的前后位置是否发生改变 ...

fiveoneLei
2018/07/17
0
0
[算法研究]の快速排序算法--javascript实现

快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部...

FRED丶DON
2015/11/08
0
0
js实现数据结构及算法之排序算法

冒泡排序 冒泡排序是最慢的排序算法之一,数据值会像起跑一样从数组的一端漂浮到另一端 动画演示 js实现 选择排序 从数组的开头开始,将第一个元素和其他元素相比,最小的元素放在第一个位置...

eternalless
2018/09/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ShxViewer_SHX字体查看

ShxViewe 是一款非常实用的SHX字型浏览软件。从CAD里面的字体浏览软件分离出来,帮助我们预览shx字体。 程序长这个样子: 分别打开txt.shx、hztxt.shx、ltypeshp.shx这几个形文件,可以了解一...

一个小妞
19分钟前
0
0
Jenkins的初步使用

Jenkins真是个宝藏软件,今天大概安装使用了一下,感觉还有好多维度可以探索。 1)安装:在Windows上使用的,在https://jenkins.io/download/下载Windows安装包,解压后是一个msi文件,默认安...

莫在全
30分钟前
0
0
技术复习-分布式事务

一、分布式事务解决方案 1.两阶段提交 two phase commit 角色分为协调者、参与者。协调者负责协调所有的参与者。 第一阶段 prepare 协调者发送prepare请求,参与者锁定资源之后返回ready或者...

Lubby
40分钟前
1
0
jenkins安装

https://my.oschina.net/u/593517/blog/1797968 jenkins 安装 https://my.oschina.net/u/593517/blog/3028175 GIT 安装 https://my.oschina.net/u/593517/blog/3028179 maven 安装 插件安装 ......

Gm_ning
50分钟前
2
0
小言服务端解决方案-监控

框架保证方向,整体包容细节 为保证服务端运行平稳正常,owner应使得系统应保有相应的监控:系统监控,业务监控。而服务运行的平稳高效是否有保障跟监控粒度又成直接的正比关系。本文仅针对开...

重城重楼
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部