用js实现各种排序

1. 冒泡排序

冒泡排序的思想就是不断进行相邻交换，较小的数字如同气泡般慢慢浮到上面。
优化：如果在排第i个元素时，没有交换任何元素，则排序已完成，无需继续遍历

function mSort(array){
    var flag=true;   //是否还要继续排序，排序优化
    for(var i=0;i<array.length-1 && flag;i++){
        flag=false;
        for(var j=array.length-2;j>=i;j--){
            if(array[j]>array[j+1]){
                var temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                flag=true;
            }
        }
    }
}

最好情况：O(n)
最坏情况：O(n^2)
平均情况：O(n^2)

2. 选择排序

选择排序的思想是每次遍历找到最小的元素，然后和相应位置的元素交换位置。

function sSort(array){
    for(var i=0;i<array.length-1;i++){
        //查找最小的元素
        var min=i;
        for(var j=i+1;j<array.length;j++){
            if(array[j]<array[min]){
                min=j;
            }
        }

        //交换位置
        var temp=array[i];
        array[i]=array[min];
        array[min]=temp;
    }
}

最好情况：O(n^2)
最坏情况：O(n^2)
平均情况：O(n^2)
略优于冒泡排序。

3.插入排序

插入排序的主要思想是将一个记录插入到已经安排好的有序表中，需要一个辅助空间来存放这个记录，以方便前面的元素进行右移。

function iSort(array){
    for(var i=1;i<array.length;i++){
        var temp=array[i];
        //将前面大于其的元素右移
        for(var j=i-1;array[j]>temp && j>=0;j--){
            array[j+1]=array[j];
        }
        //将记录插入对应位置
        array[j+1]=temp;
    }
}

最好情况：O(n)
最坏情况：O(n^2)
平均情况：O(n^2)
插入排序比冒泡和简单选择排序的性能要好。

4.快速排序

快速排序的主要思想是，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分的关键字都比另一部分的关键字小，则可以对这两部分继续进行排序，以达到整个序列有序的状态。
最主要的就是要实现一个partition函数，可以选取一个枢轴，并将其放在一个合适的位置，使其左侧值都比它小，右侧值都比它大。

    //快速排序
    function qSort(array,low,high){
        if(low<high){
            var pivot=partition(array,low,high);

            //递归排序低子表和高子表
            qSort(array,low,pivot-1);
            qSort(array,pivot+1,high);
        }
    }

    //选取一个关键字，放置到合适的位置，左侧值都比其小，右侧值都比其大
    function partition(array,low,high){
        //设置枢值为第一个元素
        var pivotkey=array[low];

        //交替向中间扫描，直到两个指针指向同一个位置，即为枢值的位置
        while(low<high){
            while(high>low && array[high]>=pivotkey){
                high--;
            }
            swap(array,low,high);

            while(low<high && array[low]<=pivotkey){
                low++;
            }
            swap(array,low,high);
        }
        return low;
    }

    //交换数组中a和b的位置
    function swap(array,a,b){
        var temp=array[a];
        array[a]=array[b];
        array[b]=temp;
    }

    var array=[5,4,3,2,1];
    qSort(array,0,array.length-1);
    console.log(array);

快速排序的时间性能取决于其快速排序递归的深度，一般partition每次划分都比较均匀时，其递归树的深度为log2n+1，而每次partition划分时，需要对数组的部分做扫描，每一层的时间复杂度为n，所以其时间复杂度为O（nlogn）。
由于关键词的比较和交换时跳跃进行的，因此，快速排序是一种不稳定的排序方法。

5.归并排序

基本思想为分治策略，先将数组进行划分，然后再进行合并，关键点是实现两个数组的合并

//合并两个数组
function merge(left,right){
    var res=[];
    while(left.length>0 && right.length>0){
        if(left[0]<=right[0]){
            res.push(left.shift());
        } else {
            res.push(right.shift());
        }
    }
    return res.concat(left).concat(right);
}

//归并排序
function sort(arr){
    //直到数组的长度为1，则终止递归
    if(arr.length===1){
        return arr;
    }

    var mid=Math.floor(arr.length/2);
    var left=arr.slice(0,mid);
    var right=arr.slice(mid);
    return merge(sort(left),sort(right));
}