排序算法

2016-09-11

最近需要写一个排序算法，很久没写发现有些生疏了，抽时间用JavaScript实现了几种常用的排序算法，以备不时之需。

一、快速排序

步骤：

在数据集之中，选择一个元素作为”基准”（pivot）。
所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

/**
 * 快速排序
 * @param arr
 * @returns Array
 */
var count = 0;
var arr   = [55,1,22,77,99,11,88,33,66,44];
function quickSort(arr){
    //递推跳出
    if (arr.length <= 1) { return arr; }
    //首先定义“基准”左右数据的数组
    var left    = [];
    var right   = [];
    //选择第一个元素作为基准元素(基准元素可以为任意一个元素)
    var pivot   = arr[0];
    var len     = arr.length;
    //由于取了第一个元素，所以从第二个元素开始循环
    for(var i=1;i<len;i++){
        var item = arr[i];
        //大于基准的放右边，小于基准的放左边
        item>pivot ? right.push(item) : left.push(item);
        count++;
    }
    //递归左右数组
    return quickSort(left).concat([pivot],quickSort(right));
}
console.log(quickSort(arr));
console.log(count);  //21

二、插入排序

步骤：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果被扫描的元素（已排序）大于新元素，将该元素后移一位
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

/**
 * 插入排序
 * @param arr
 * @returns Array
 */
var count = 0;
var arr   = [55,1,22,77,99,11,88,33,66,44];
function insertSort(arr){
    var sorted  = [];
    //把数组中的第一个元素定义为已排序元素
    sorted.push(arr[0]);
    //不断取未排序的元素插入到已排序元素中
    var len = arr.length;
    for(var i= 1;i<len;i++){
        var item        = arr[i];
        //在已经排序的元素序列中从后向前扫描
        var flag    = true;
        var j       = sorted.length-1;
        for(j;j>=0;j--){
            //直到比自己小的元素，就把自己放在该元素后面
            if(item>sorted[j]){
                //插入到元素之后
                sorted.splice(j+1,0,item);
                flag = false;
                break
            }
            count++;
        }
        //自己最小，直接放到第一个位置
        if(flag){sorted.splice(0,0,item);}
    }
    return sorted;
}
console.log(insertSort(arr));
console.log(count);  //19

排序演示：

三、冒泡排序

步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

/**
 * 冒泡排序
 * @param arr
 * @returns Array
 */
var count = 0;
var arr   = [55,1,22,77,99,11,88,33,66,44];
function bubbleSort(arr){
    var len = arr.length;
    var temp= [];
    for(var i=0;i<len;i++){
        //每一次的最后结果都是最大的元素放到了最后
        for(var j=0;j<len-i-1;j++){
            if(arr[j]>arr[j+1]){
                temp    = arr[j];
                arr[j]  = arr[j+1];
                arr[j+1]= temp;
            }
            count++;
        }
    }
    return arr;
}
console.log(bubbleSort(arr));
console.log(count);  //45

四、时间复杂度

来自于这里