传统的三种排序以及冒泡排序的优化算法
今天听到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也不能丢，我就是说一说自己的一些想法:)，希望同行们（为梦想奋斗中的我们），在使用框架或者一些类库来工作的同时，最底层最原理的东西也不能丢，我自己都不知道我现在在说什么，就是感觉我们不能丢了最原始的东西，好了，今天就到这里了，各位晚安，勿忘初心，方得始终~~~