前言
校招已经开始 的了。。前端不知道算法会考查到什么地步，但是常见的排序算法是必须要掌握的！
网络上查到很多都是JAVA,phython写的。js的版本有的写的很晦涩。所以我自己来写一遍吧
冒泡排序
思路：将数组从头开始，两两比较，如果左边的比右边大，则交换。
这样一来，一轮下来，最右边的就会是最大的数组元素啦！
然后我们把循环次数减一，再换一遍。然后数组的倒数第二个又是最大的啦！
直到循环的次数减为1，数组的排序就完成啦！
接下来是代码环节！
function bubbleSort(arr) {
var len = arr.length - 1;
//循环次数每次减一，直到0，跳出循环
while(len) {
for(var i = 0; i < len; i++) {
if(arr[ i ] > arr[ i + 1 ]) swap(arr,i,i+1);
}
len -= 1;
}
//swap，交换数组的index1与index2项 在排序中swap函数很常见
function swap(arr,index1,index2) {
var tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
}
选择排序
思路：把数组中的最大元素放到数组的最后，数组的长度减一，然后如此往复，最后数组排序就完成啦。
function selectSort(arr) {
var result = [];
while(arr.length) {
var min = Math.min.apply(null,arr);
var index = arr.indexOf(min);
//找到最小元素然后把它从数组中移除
arr.splice(index,1);
result.push(min);
}
return result;
}
插入排序
思路：把数组第一个元素取出，然后将第二个元素与第一个比较排序，接下来将第三个元素取出插入到之前那排序的两个元素中。如此往复，完成排序。
代码：
function insertSort(arr) {
var result = [];
//先把第一个元素放进数组
result.push(arr[0]);
//然后从第二个数字开始往我们的result里插入
for(var i = 0; i < arr.length - 1; i ++ ) {
insert(result,arr[i+1]);
}
return result;
function insert(arr,num) {
var index;
for(var i = 0; i < arr.length; i++) {
//等于时也往同样的位置插入
if( num >= arr[i] && num <= arr[i+1]) {
index = i+1;
}
}
if(num > Math.max.apply(null,arr)) index = arr.length;
if(num < Math.min.apply(null,arr)) index = 0;
arr.splice(index,0,num);
}
}
非常遗憾，我们的插入排序确实思路很简单。但是这样子写开辟了额外的数组空间。同时，如果我们要进行希尔排序。这样写会造成麻烦。。
这里重新用比较常见的写法来写一遍：
代码：
function insertSort(arr){
for(var i = 1; i < arr.length; i++){
var tmp = arr[i];
var j = i - 1;
arr[i] = arr[j]；
while(j >= 0 && tmp < arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = tmp;
}
}
这样写的精妙之处在于，我们也是先把第一项排除，然后把第二项往前插。但是，这里我们直接取j为我们的前一项，i为当前项。我们直接将当前项变成我们的前一项。然后开始插入，当然，插入的数字我们先要保存下来，那就是当前项的值。（此时数组中没有当前项。。）从j开始往前比较，如果比当前元素小，那么很正常。。还要往前找，这时候把当前项赋给后一项。如果比当前元素大，那么久把tmp赋给j+1处的元素。这样一来，既不需要申请新的空间，也能进行插入了！
好了在此基础之上，我们来写希尔排序。
希尔排序
思路： 希尔排序，是对插入排序的优化。我们先取一个gap，为arr.len除以2取整数。我们根据gap进行分组，对组内的元素进行插入排序。然后gap除以2，再次分组，继续对组内插入排序。当gap=1时，只有一组，最后完成我们的排序。这样子分组，使得插入排序的交换次数大大的减少。但是由于gap的存在，算法不稳定。
代码：
function shellSort(arr) {
var len = arr.length;
var gap = Math.floor(len/2);
while(gap >= 1) {
for(var i = gap; i < arr.length; i++) {
var temp = arr[i];
var j;
for( j = i - gap; j >= 0 && temp < arr[j]; j -= gap) {
arr [ j+gap ] = arr[j];
}
arr[ j+gap ] = temp;
}
gap = Math.floor(gap / 2);
}
}
可以看到，之前是对整个数组进行遍历，而这里，我们循环时，不是每次-1,而是-gap值，当然之前插入排序中的1都是gap啦~
在外层循环中，我们从gap开始，这样子就能对整个数组进行分组啦。
快速排序
思路：快速排序其实思路比较简单，数组中找一个枢轴，这个元素影响我们的排序的复杂程度，选择中间数当然是最佳。然后把比他大的放在右边，比他小的放在左边，然后把三者合起来。当然左边与右边的数组要递归处理。
代码：
function quickSort(arr) {
if(arr.length) {
var pivotIndex = Math.floor(arr.length/2);
var pivot = arr[pivotIndex];
var bigArr = [];
var smallArr = [];
var sameArr = [];
for(var i = 0; i < arr.length; i ++ ) {
if(arr[ i ] > pivot) {
bigArr.push(arr[i]);
}else if(arr[ i ] < pivot) {
smallArr.push(arr[i]);
}else{
//因为可能有重复元素，所以用三路快排
sameArr.push(arr[i]);
}
}
var sortLeft = quickSort(smallArr);
var sortRight = quickSort(bigArr);
return sortLeft.concat(sameArr).concat(sortRight);
}else{
//其实快排也算是分治思想的运用如果没有元素则返回空
return [];
}
}
归并排序
思路：归并排序是分治思想的运用。同时也运用到了递归。
代码：
function mergeSort(arr) {
if(arr.length == 1) {
//若只有一个元素则直接返回
return arr;
}else{
var midIndex = Math.floor(arr.length/2);
var leftPart = arr.slice(0,midIndex);
var rightPart = arr.slice(midIndex);
//若有两个我们将其合并，当然需要递归处理子数组
return merge( mergeSort(leftPart), mergeSort(rightPart));
}
}
function merge(arr1,arr2) {
var result = [];
//知道其中一个数组内元素完全被推出，则合并完毕
while(arr1.length && arr2.length) {
if(arr1[0] < arr2[0]) {
result.push(arr1.shift());
}else {
result.push(arr2.shift());
}
}
//我们并不知道哪个为空，所以都concat
return result.concat(arr1,arr2);
}
堆排序
思路：堆排序需要借助堆这个数据结构。堆是一个完全二叉树，且堆的父节点的值比子节点要大（大根堆）。
我们先利用数组来构建大根堆（父大于子，父小于子是小根堆），然后首位互换数组长度减一后再次调整堆。知道完成排序。
代码：
//调整函数，将数组调整为大根堆，从所选的节点，递归调整其所有的子节点
function adjustHeap(arr, i, len){
//首先假设传入的index节点的值最大
var maxIndex = i;
// 根据树的结构，右节点是 2(i+1),做节点比又节点小一
var right = 2 * ( i + 1 );
var left = right - 1;
//传入节点可能没有子节点，没有右节点，或者有左右子节点
//如果没有子节点那么maxIndex = i
//如果有左节点，若他比较大，那么maxIndex替换为left，否则不变
if( left < len && arr[left] > arr[i] ) {
maxIndex = left;
}
//然后如果有右节点，与之前的大的节点比较，若大于maxIndex
//替换为right。否则不变
if( right < len && arr[right] > arr[maxIndex] ) {
maxIndex = right;
}
//如果maxIdex被替换了，说明要对无序数组进行调整来构建堆
if( maxIndex !== i ) {
//swap函数，排序中常用
swap(arr, maxIndex, i);
//替换完后由于原先maxIndex处的节点发生变化，所以要重新调整
//它自己的子节点。故递归处理
adjustHeap(arr, maxIndex, len);
}
}
function swap(arr,index1,index2){
var temp=arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
}
//构建堆，这里的lastTrunkIndex很重要，他是最后一个树单元的父序号
//从它开始往前，依次进行调整，最终构建整个堆
function buildHeap(arr){
var lastTrunkIndex = Math.floor(arr.length / 2) - 1;
for(var i = lastTrunkIndex ; i >= 0; i--){
adjustHeap(arr, i, arr.length);
}
}
function heapSort(arr){
buildHeap(arr);
//构建完堆以后，进行换位于换位后堆的调整，由于顶部发生了变化所以传入0调整整个堆
for(var i = arr.length-1; i > 0; i--){ //从数组的尾部进行调整 尾部的序号当然是len - 1啦~
var swap = arr[i];
arr[i] = arr[0];
arr[0] = swap;
adjustHeap(arr, 0, i); //将最大的元素进行调整，将最大的元素调整到堆顶
}
}
计数排序
思路：计数排序不是比较排序。他的思路如下：获得数组中的最大数，将其加一。构建数组，每一位为0。表示，该位无数字。
之后遍历我们的数组，往直前的数组中填充。
之后直前的数组中，有数字的表示，该位有数字，个数为填充数。
代码：
function countSort(arr) {
//构建技术的数组
var countArr = [];
var result = [];
var max = Math.max.apply(null,arr);
for(var i = 0; i <= max; i++ ) {
countArr.push(0);
}
for(var i = 0; i < arr.length; i ++) {
var item = arr[i];
countArr[item] += 1;
}
for(var i = 0; i < countArr.length; i++) {
var hasItem = countArr[i] !== 0 ? true : false;
var isDuplicate = countArr[i] !== 1 ? true : false;
if(hasItem) {
if(!isDuplicate) {
result.push(i);
}else{
//如果该位大于1，则重复推入
for(var j = 0; j < count[i]; j ++) {
result.push(i);
}
}
}
}
return result;
}
桶排序
思路： 桶排序是计数排序的变种，我们自己设定桶的个数。也就是采集数组的个数，如果把桶的个数细分为最大数+1，那么与计数排序无异了。
下面以四通为例：（每个桶的内部可以采用其他排序方式，这里我们用快排）
代码：
function bucketSort(arr,bucketNum) {
var bucketNum = bucketNum;
var bigBucket = [];
for(var i = 0; i < bucketNum; i++) {
bigBucket[i] = [];
}
var max = Math.max.apply(null,arr);
var min = Math.min.apply(null,arr);
//计算每个桶的范围
var range = ( max - min + 1 ) / bucketNum;
for(var i = 0; i < arr.length; i++) {
//计算自己该丢到哪个桶内
var bucketIndex = Math.floor( (arr[i] - min) / range );
bigBucket[bucketIndex].push(arr[i]);
}
var blank = [];
for(var i = 0; i < bucketNum; i++) {
//merge所有桶内的元素。
var result = blank.concat(quickSort(bigBucket[i]));
blank = result;
}
console.log(result);
return result;
}
基数排序
思路：基数排序是桶排序的变种。我们以数字的位来让数字入桶。
LSD是从小的位开始，往高位来，每次入桶后，merge，然后再入桶，直到最高位。然后merge,完成排序。
而MSD是从高位开始，入桶后，遍历每个桶，对每个桶内的数组再次使用桶排序，递归结束的条件是，每个桶内的元素个数为1或者0，则返回merge。
我们把所有的merge合并，最后得到排序好的数组。
代码： （LSD）
function radixSort(arr) {
var bucket = new Array(10);
//初始化桶，桶的每一位置0
initBucket();
//数组入桶，按个位
splitArr(arr,-1);
//合并
mergeBucket();
//再次初始化桶
initBucket();
//入桶
splitArr(arr,-2,-1);
//合并
mergeBucket();
//往复，知道百位入桶
initBucket();
splitArr(arr,-3,-2);
//合并
mergeBucket();
//得到结果
return arr;
function splitArr(arr,index1,index2) {
for(var i = 0; i < arr.length; i++) {
var num = getLoc(arr[i], index1, index2);
bucket.forEach(function(item,index) {
if(num == index) bucket[index].push(arr[i]);
});
}
}
function mergeBucket() {
var blank = [];
for(var i = 0; i < 10; i++) {
var result = blank.concat(bucket[i]);
blank = result;
}
arr = blank;
}
function getLoc(number,index1,index2) {
var numArr = number.toString().split('');
var result = numArr.slice(index1,index2);
return Number(result);
}
function initBucket() {
for(var i = 0; i < 10; i++) {
bucket[i] = [];
}
}
}
MSD：
function radixSort2(arr) {
var result = [];
splitArr(arr,3,result);
console.log(result);
return result;
}
function splitArr(arr,pos,result) {
//每次都初始化一个10位桶
var bucket = initBucket();
for(var i = 0; i < arr.length; i++) {
var num = getLoc(arr[i], pos);
bucket.forEach(function(item,index) {
if(num == index) bucket[index].push(arr[i]);
});
}
var isFinish = bucket.every(function(item) {
return item.length == 1 || item.length == 0;
});
//如果桶的每一位为0或1则递归结束，往result上push我们的item，此处用concat会导致错误
if(isFinish) {
var newArr = mergeBucket(bucket);
newArr.forEach(function(item) {
result.push(item);
});
}else{
//如果递归未结束,那么取出不为1和0的桶内数组再次桶排序，但是这次位数要-1，当然Pos必须大于1.
bucket.forEach(function(item) {
if(item.length >= 1) {
if(pos > 1) splitArr(item,pos - 1,result);
}
});
}
}
function initBucket() {
var bucket = [];
for(var i = 0; i < 10; i++) {
bucket[i] = [];
}
return bucket;
}
function getLoc(number,pos) {
var result;
var numArr = number.toString().split('');
if(pos == 1) {
result = numArr.slice(-1);
}else if(pos == 2) {
result = numArr.slice(-2,-1);
}else if(pos == 3) {
result = numArr.slice(-3,-2);
}
return Number(result);
}
function mergeBucket(bucket) {
var blank = [];
for(var i = 0; i < 10; i++) {
var result = blank.concat(bucket[i]);
blank = result;
}
return blank;
}
结语
下一篇讨论算法的复杂度。不废话over!