排序

JS之排序算法

在平时的工作中呢也用不到太多的算法，但是私认为算法还是挺锻炼一个程序员的逻辑思维的，写一下会的几种算法吧

冒泡排序：

function bubbleSort(arr){
        for(var i=0;i<arr.length;i++){
            for(var j=0;j<arr.length-i;j++){
                if(arr[j]>arr[j+1]){
                    var num = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = num;
                }
            }
            console.log(arr);
        }
        return arr
    }
    var num = [1,2,1,3,7,4,9,0];
    console.log(bubbleSort(num));

解析一下：

·第一遍外循环i=0时，j也是0，j<arr.length-i的话呢，就是遍历整个数组，里面的if判断呢就是两两比较，arr[j]和arr[j+1]哪个大，然后把大的放在后面，这样就把数组中最大的那个家伙放到的数组末尾啦

·第二遍外循环i=1时，j还是0，j<arr.length-i呢，内循环就不会遍历到数组的末尾了，就是最大的那个家伙呢不用参加这次遍历了，那么这次呢，又把数组里面第二大的家伙排到了倒数第二的位置了

·后面就是同上类推了，理解一下的话，就是冒泡一样，把最大的一遍一遍的冒泡到数组的末尾，退出整个函数的时候呢，整个数组就排好顺序了

快速排序：

function quickSort(arr){
        if(arr.length <= 1){
            return arr;
        }
        var index = Math.floor(arr.length/2);
        var middle = arr.splice(index,1);
        var left = [];
        var right = [];
        for(var i=0;i<arr.length;i++) {
            if(arr[i] < middle){
                left.push(arr[i])
            }else{
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat(middle,quickSort(right));
    }
 
    var aaa = [1,3,2,7,1,5,9,2];
    alert(quickSort(aaa));

解析：

·首先判断数组长度是否小于等于1，是的话直接return回去

·splice取出数组的中位数middle，整个数组里面没有middle这个数了哦

·新建两个left和right数组

·遍历整个数组，判断arr[i]是小于还是大于中位数middle，小于的push到left这个数组，大于的push到right这个数组里

·最后一句，将left和right两个数组当做参数递归调用quickSort函数。并且呢用concat连接起来，别忘了还有个中位数哦

·之后的递归就是回到第一步重复调用了，当left或者right数组长度为1时，就是排好顺序啦

整个快速排序算法的逻辑就是把数组对半，小的放左边，大的放右边，然后再把左右两边继续对半分，小的放左边，大的放右边，不断如此··········

拿写的aaa数组来说，中位数是7,那么left就是[1,3,2,1,5,2],right就是[9]，然后递归left，还是很好理解的吧

最后是JS的array对象的sort方法排序，我也不知叫什么名-。-

function ArraySort(){
        var tag = [];
        for(var i= 0;i<arguments.length;i++){
            tag.push(arguments[i]);
        }
        tag.sort(function(compare1,compare2){
            return compare1 - compare2
        })
        return tag
    }
    console.log(ArraySort(1,2,5,1,2,3,9,7,8));

解析：

·sort方法传入两个参数compare1,compare2，两两进行比较，如果compare1-compare2小于0呢，两两之间就不换位置，反之就调换位置

·当然可以这样写 return compare2 - compare1，这样呢就是倒序排列了