黄金城官方网站-gc8.me
  咨询电话:15112111218

hjc黄金城手机主页

传统的三种排序以及冒泡排序的优化算法

   今天听到leader说面试的事,说问一个有两年工作经验的人,传统的三种排序可以手写吗都手写不出来。让我心中也是一颤,其实想想,工作了这么久,对于原生js这块儿真的有些淡忘了,在工作中平时都是用的框架来搞事情,直接拿来就可以用,想想当初刚入这行的时候,那时候就觉得js真的很神奇,可是随着工作时间越来越久,一些东西都是直接拿来用,对于底层的原理也不那么深究了,之前还好,还看看,现在都已经麻木了。今天leader说的这番话,其实你如果说让我手写这三种排序我还是可以写出来的,但是我觉得对于原生js这块儿确实忘了一些,学无止境,不是新的东西就是好的东西,不能忘记最底层的实现,嗯~,写博客写博客,不闲聊了。  对于我们leader今天说的话,我也引入了另外一个知识点,多少和性能优化沾一点边,冒泡排序我们都知道,可你知不知道它还可以进行优化呢,今天我们就来聊一聊传统的三种基本排序算法(选择排序、快排、冒泡)以及关于冒泡排序如何进行优化的三种优化方案

  因为这三种基本的排序算法原理都很简单,所以在思路这块我就不做过多的解释了,我们把重点放在最后的冒泡排序如何优化上面

 一、选择排序

选择排序的思路:比如一个数组arr=[9,6,2,5,10,20,1]进行从小到大排序,我们让每一个数字都和后面的数字进行比较,比自己小的就交换位置,比自己大的就进行下一个比较,将这个数放到相应的位置,下面是代码的实现:

function selectSort(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; } } } return arr;}

 二、快速排序

  快速排序的思路:从一个数组中任意的挑选一个元素(通常来说我们会选择中间的那个元素),将这个元素作为中轴元素,然后把剩下的元素以这个中轴元素的大小作为标准,比中轴元素小的放到左边,比中轴元素大的放到右边,然后把左边和右边的都作为一个数组,重复以上操作,知道子元素的元素个数小于等于1的时候,就证明全部的元素都已经从小到大排好序了(因为只有一个元素的数组一定是有序的,已经不需要再继续排序了),在这个算法中我们主要是用到了了一个递归算法(递归算法不了解的建议可以先去看下这方面的知识),以下是代码的实现:

function quickSort(arr){ if(arr.length<=1){ return arr; } //获取下标 var midIndex = arr.length%2 == 0?arr.length/2:(arr.length+1)/2; //取中间值 var mid = arr[midIndex]; //定义左边的数组 var left = []; //定义右边的数组 var right = []; for(var i=0;i<arr.length;i++){ if(i != midIndex && arr[i]<=mid){ left.push(arr[i]); } if(i != midIndex && arr[i]>mid){ right.push(arr[i]); } } return quickSort(left).concat(mid).concat(quickSort(right))}

 

    三、冒泡排序

  冒泡排序的思路:顾名思义,冒泡排序,就像冒泡一样,从小往大冒,由于逻辑过于简单,在这里我就直接贴出代码了:

function bubbleSort(arr){ var temp; for(var i=0;i<arr.length;i++){ for(var j=0;j<arr.length-i;j++){ if(arr[j]>arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } return arr;}

  通过上面的代码可以看出来,通过两次简单的for循环,并且不加任何判断语句的形式的算法注定是低效的,以下是对冒泡排序算法的三种优化


 (1)、当我们对一个数组arr=[9,1,2,3,4,5,6]进行排序的时候,我们正常冒泡排序的话,还是会每个数字都排一次,但事实上我们第一次排序进行完之后,数组就已经变成[1,2,3,4,5,6,9],已经达到我们想要的效果了,所以已经不需要再进行其他元素的排序了,所以我们要对这种传统的冒泡排序算法做一个优化,思路大概是这样的:我们定义一个flag,当某一次排序中没有发生元素的交换的话,设置flag为false,当flag为false的时候直接结束后面的循环,这样的话数组就不会再进行后面的无意义的排序了,代码实现:

var arr = [9,1,2,3,4,5,6] function bubbleSort(arr){ var temp; var flag; //定义flag,用来判断数组是否已经有序 for(var i=0;i<arr.length;i++){ flag = true //我们设置flag初始值为true for(var j=0;j<arr.length-i;j++){ if(arr[j]>arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; flag = false; //我们自己规定flag为false的时候说明数组需要继续排序 } } if(flag){ //我们可以规定如果某次循环后flag依然为true的话,表明这次没有进行重新的元素交换,也就是说没有进行重新排序,那么此时数组中元素已经有序了,所以我们可以直接break跳出循环,return出数组 break; } } return arr;}

(2)、第二种优化是从另一个角度来考虑的,并且也是基于第一次优化的思想,我们每次排序后,数组的后面有一部分已经有序了,所以我们也不需要再和后面已经排好序的元素再进行比较了,我们可以这样做,用一个变量来记录下最后一次发生交换的位置,后面没有发生交换的其实已经有序了,所以可以用这个值来作为一一次我们比较结束时的位置,将会减少很多次没必要的排序过程,代码实现如下:

var arr = [9,1,10,5,6,3,0] function bubbleSort(arr){ var temp; var flag; //定义flag,用来判断数组是否已经有序 var lastindex = 0; //定义lastindex,用来判记录每次排好序时的最后一次交换的位置 var k = arr.length-1; //用来和lastindex配合,作为每次循环的边界值,实现不会进行没必要排序的效果 for(var i=0;i<arr.length;i++){ flag = true //我们设置flag初始值为true for(var j=0;j<k;j++){ if(arr[j]>arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; flag = false; //我们自己规定flag为false的时候说明数组需要继续排序 lastindex = j; //来记录最后一次交换元素的下标 } } k = lastindex if(flag){ //我们可以规定如果某次循环后flag依然为true的话,表明这次没有进行重新的元素交换,也就是说没有进行重新排序,那么此时数组中元素已经有序了,所以我们可以直接break跳出循环,return出数组 break; } } return arr;}

    在这里我只写了两种优化的方法,可我为什么说有三种呢,是我觉得肯定还会有第三种第四种等等很多,等待着我们后续的思考,做了前端也快三年了,性能优化这块儿在各个方面都有很多,还有原生js也不能丢,我就是说一说自己的一些想法:),希望同行们(为梦想奋斗中的我们),在使用框架或者一些类库来工作的同时,最底层最原理的东西也不能丢,我自己都不知道我现在在说什么,就是感觉我们不能丢了最原始的东西,好了,今天就到这里了,各位晚安,勿忘初心,方得始终~~~