今天讲一道前端开发的笔试题,题目如下: 编写快速排序和冒泡排序,并简单对比分析.
看到题目愣了一下,知道冒泡排序,可什么是快速排序呢？
下面先来看一下冒泡排序：
方法一: 每一次对比相邻两个数据的大小，小的排在前面，如果前面的数据比后面的大就交换这两个数的位置
var arr = [90,0,-10,88,999,100,102,2,3,20]; function sortArr1(arr){ var count = 0; //统计循环次数 for (let i=0;i<arr.length;i++) { //遍历数组,从左往右,相邻两个元素进行比较,把大的数往后面排 for (let j=0;j<arr.length-1-i;j++) { if(arr[j]>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.length-1;i++){ //遍历数组,获得当前的数arr[i]与它后面的数依次对比 for(var j=i+1;j<arr.length;j++){ if(arr[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<arr.length;i++){ if(arr[i]<midIndexVal){ left.push(arr[i]);//比基准点小的放在左边数组 console.log(left); } else{ right.push(arr[i]);//比基准点大的放在右边数组 console.log(right); } console.log("第"+(++times)+"次排序后："+arr); } //递归执行以上操作,对左右两个数组进行操作，直到数组长度为<=1； return quickSort(left).concat(midIndexVal,quickSort(right)); }; console.log(quickSort(arr)); //[-10, 0, 1, 2, 3, 88, 90, 99, 102, 200]
经过测试,随便变换数组的数,比较的次数也会改变,比如上面的数组,比较了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]。
总结分析:以上两种快速排序方法的比较次数都相对少,但是随着排序的数不一样,比较的次数也会不一样.
最后对冒泡排序与快速排序两种方法进行对比分析:
以上两种快速排序方法都比上面的冒泡排序的比较次数少,效率高。
但是冒泡排序简单实用易于理解,而直接使用数组方法则更加简单快捷高效率的解决排序问题.
以上仅代表个人的见解,如果不对的地方希望大家指出.或者有更好的解决方法也希望可以分享出来学习.