本文共 6494 字，大约阅读时间需要 21 分钟。
今天讲一道前端开发的笔试题,题目如下: 编写快速排序和冒泡排序,并简单对比分析.
看到题目愣了一下,知道冒泡排序,可什么是快速排序呢？
下面先来看一下冒泡排序：
方法一: 每一次对比相邻两个数据的大小，小的排在前面，如果前面的数据比后面的大就交换这两个数的位置
var arr = [90,0,-10,88,999,100,102,2,3,20]; function sortArr1(arr){ var count = 0; //统计循环次数 for (let i=0;i arr[j+1]){ var temp = arr[j+1]; //如果前面的数大于后面的则交换 arr[j+1]=arr[j]; arr[j]=temp; } document.write("第"+(++count)+"次排序后："+arr); } } return arr; } console.log(sortArr1(arr)); //[-10, 0, 2, 3, 20, 88, 90, 100, 102, 999] 方法1执行过程中输出的结果为:
第1次排序后：0,90,-10,88,999,100,102,2,3,20 第2次排序后：0,-10,90,88,999,100,102,2,3,20 第3次排序后：0,-10,88,90,999,100,102,2,3,20 第4次排序后：0,-10,88,90,999,100,102,2,3,20 第5次排序后：0,-10,88,90,100,999,102,2,3,20 第6次排序后：0,-10,88,90,100,102,999,2,3,20 第7次排序后：0,-10,88,90,100,102,2,999,3,20 第8次排序后：0,-10,88,90,100,102,2,3,999,20 第9次排序后：0,-10,88,90,100,102,2,3,20,999 第10次排序后：-10,0,88,90,100,102,2,3,20,999 第11次排序后：-10,0,88,90,100,102,2,3,20,999 第12次排序后：-10,0,88,90,100,102,2,3,20,999 第13次排序后：-10,0,88,90,100,102,2,3,20,999 第14次排序后：-10,0,88,90,100,102,2,3,20,999 第15次排序后：-10,0,88,90,100,2,102,3,20,999 第16次排序后：-10,0,88,90,100,2,3,102,20,999 第17次排序后：-10,0,88,90,100,2,3,20,102,999 第18次排序后：-10,0,88,90,100,2,3,20,102,999 第19次排序后：-10,0,88,90,100,2,3,20,102,999 第20次排序后：-10,0,88,90,100,2,3,20,102,999 第21次排序后：-10,0,88,90,100,2,3,20,102,999 第22次排序后：-10,0,88,90,2,100,3,20,102,999 第23次排序后：-10,0,88,90,2,3,100,20,102,999 第24次排序后：-10,0,88,90,2,3,20,100,102,999 第25次排序后：-10,0,88,90,2,3,20,100,102,999 第26次排序后：-10,0,88,90,2,3,20,100,102,999 第27次排序后：-10,0,88,90,2,3,20,100,102,999 第28次排序后：-10,0,88,2,90,3,20,100,102,999 第29次排序后：-10,0,88,2,3,90,20,100,102,999 第30次排序后：-10,0,88,2,3,20,90,100,102,999 第31次排序后：-10,0,88,2,3,20,90,100,102,999 第32次排序后：-10,0,88,2,3,20,90,100,102,999 第33次排序后：-10,0,2,88,3,20,90,100,102,999 第34次排序后：-10,0,2,3,88,20,90,100,102,999 第35次排序后：-10,0,2,3,20,88,90,100,102,999 第36次排序后：-10,0,2,3,20,88,90,100,102,999 第37次排序后：-10,0,2,3,20,88,90,100,102,999 第38次排序后：-10,0,2,3,20,88,90,100,102,999 第39次排序后：-10,0,2,3,20,88,90,100,102,999 第40次排序后：-10,0,2,3,20,88,90,100,102,999 第41次排序后：-10,0,2,3,20,88,90,100,102,999 第42次排序后：-10,0,2,3,20,88,90,100,102,999 第43次排序后：-10,0,2,3,20,88,90,100,102,999 第44次排序后：-10,0,2,3,20,88,90,100,102,999 第45次排序后：-10,0,2,3,20,88,90,100,102,999
方法二:
var times=0; function sortArr2(arr){ for(var i=0;i arr[j]){ var temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } console.log("第"+(++times)+"次排序后："+arr); } } return arr; } console.log(sortArr2(arr)); //[-10, 0, 2, 3, 20, 88, 90, 100, 102, 999] 方法2执行过程中的结果:
第1次排序后：0,90,-10,88,999,100,102,2,3,20
第2次排序后：-10,90,0,88,999,100,102,2,3,20 第3次排序后：-10,90,0,88,999,100,102,2,3,20 第4次排序后：-10,90,0,88,999,100,102,2,3,20 第5次排序后：-10,90,0,88,999,100,102,2,3,20 第6次排序后：-10,90,0,88,999,100,102,2,3,20 第7次排序后：-10,90,0,88,999,100,102,2,3,20 第8次排序后：-10,90,0,88,999,100,102,2,3,20 第9次排序后：-10,90,0,88,999,100,102,2,3,20 第10次排序后：-10,0,90,88,999,100,102,2,3,20 第11次排序后：-10,0,90,88,999,100,102,2,3,20 第12次排序后：-10,0,90,88,999,100,102,2,3,20 第13次排序后：-10,0,90,88,999,100,102,2,3,20 第14次排序后：-10,0,90,88,999,100,102,2,3,20 第15次排序后：-10,0,90,88,999,100,102,2,3,20 第16次排序后：-10,0,90,88,999,100,102,2,3,20 第17次排序后：-10,0,90,88,999,100,102,2,3,20 第18次排序后：-10,0,88,90,999,100,102,2,3,20 第19次排序后：-10,0,88,90,999,100,102,2,3,20 第20次排序后：-10,0,88,90,999,100,102,2,3,20 第21次排序后：-10,0,88,90,999,100,102,2,3,20 第22次排序后：-10,0,2,90,999,100,102,88,3,20 第23次排序后：-10,0,2,90,999,100,102,88,3,20 第24次排序后：-10,0,2,90,999,100,102,88,3,20 第25次排序后：-10,0,2,90,999,100,102,88,3,20 第26次排序后：-10,0,2,90,999,100,102,88,3,20 第27次排序后：-10,0,2,90,999,100,102,88,3,20 第28次排序后：-10,0,2,88,999,100,102,90,3,20 第29次排序后：-10,0,2,3,999,100,102,90,88,20 第30次排序后：-10,0,2,3,999,100,102,90,88,20 第31次排序后：-10,0,2,3,100,999,102,90,88,20 第32次排序后：-10,0,2,3,100,999,102,90,88,20 第33次排序后：-10,0,2,3,90,999,102,100,88,20 第34次排序后：-10,0,2,3,88,999,102,100,90,20 第35次排序后：-10,0,2,3,20,999,102,100,90,88 第36次排序后：-10,0,2,3,20,102,999,100,90,88 第37次排序后：-10,0,2,3,20,100,999,102,90,88 第38次排序后：-10,0,2,3,20,90,999,102,100,88 第39次排序后：-10,0,2,3,20,88,999,102,100,90 第40次排序后：-10,0,2,3,20,88,102,999,100,90 第41次排序后：-10,0,2,3,20,88,100,999,102,90 第42次排序后：-10,0,2,3,20,88,90,999,102,100 第43次排序后：-10,0,2,3,20,88,90,102,999,100 第44次排序后：-10,0,2,3,20,88,90,100,999,102 第45次排序后：-10,0,2,3,20,88,90,100,102,999总结分析:上面两种方法都实现了冒泡排序,比较的方式不一样,但是排序次数是一样的,10个数要对比45次。
---------------------------------------------此处是分割线----------------------------------------------
讲完冒泡排序，下面一起来了解一下什么是快速排序，何谓快速？就是比较更少的次数得到一样的结果。
方法一：先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点的数字比较，
如果比它小，放左边；反之，放右边。分别用一个空数组去存储比较后的数据。最后递归执行上述操作，直到数组长度<=1;
var arr = [90,0,-10,88,99,1,102,2,3,200]; var times=0; var quickSort=function(arr){ //如果数组长度小于等于1无需判断直接返回即可 if(arr.length<=1){ return arr; } var midIndex=Math.floor(arr.length/2);//取基准点 var midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1] var left=[];//存放比基准点小的数组 var right=[];//存放比基准点大的数组 //遍历数组，进行判断分配 for(var i=0;i 经过测试,随便变换数组的数,比较的次数也会改变,比如上面的数组,比较了25次。
而换成[90,0,-10,88,999,1,102,2,3,200],比较了22次,结果是[-10, 0, 1, 2, 3, 88, 90, 102, 200, 999]。
再换成[90,0,-10,88,99,1,102,2,3,20] ,比较了30次,结果是[-10, 0, 1, 2, 3, 20, 88, 90, 99, 102]。
方法二:直接利用数组的排序方法sort来实现
var count=0; function sortNumber(a,b){ //定义排序规则 console.log(count++); return a-b; } console.log(arr.sort(sortNumber)); //数组排序方法sort 同样的,经过测试,随便变换数组的数,比较的次数也会改变,比如上面的数组[90,0,-10,88,99,1,102,2,3,200];,比较了21次。
而换成[90,0,-10,88,999,1,102,2,3,200],比较了23次,结果是[-10, 0, 1, 2, 3, 88, 90, 102, 200, 999]。
再换成[90,0,-10,88,99,1,102,2,3,20] ,比较了25次,结果是[-10, 0, 1, 2, 3, 20, 88, 90, 99, 102]。
总结分析:以上两种快速排序方法的比较次数都相对少,但是随着排序的数不一样,比较的次数也会不一样.
最后对冒泡排序与快速排序两种方法进行对比分析:
以上两种快速排序方法都比上面的冒泡排序的比较次数少,效率高。
但是冒泡排序简单实用易于理解,而直接使用数组方法则更加简单快捷高效率的解决排序问题.
以上仅代表个人的见解,如果不对的地方希望大家指出.或者有更好的解决方法也希望可以分享出来学习.
转载地址：http://gpgyb.baihongyu.com/