JS 排序算法

冒泡排序：

核心思想：从第一个开始遍历数组，遍历完成后，让最小的值放在第一位；然后从第二个开始遍历数组，遍历完成后将最小值放在第二位；以此类推，所有位的数组遍历完成后就排序完成。

var arr = [3, 12, 53, 32, 26, 7, 1];

var len = arr.length;

for (var i = 0; i < len; i++) {

    for (var j = i+1; j < len; j++) {

        if (arr[i] > arr[j]) {

            var tmp = arr[i];

            arr[i] = arr[j];

            arr[j] = tmp;

        }

    }

}

插值法排序：
核心思想：创建一个新数组，将原数组的元素一个个放到新数组中，每次放入的时候和已放入新数组的元素进行遍历比较，遇到比他大的就放那个元素前面，没遇到比他大的就放在最后。新数组即为排序后的数组。

var arr = [12, 3, 56, 2, 32, 9];

var arr2 = [];

arr2[0] = arr[0];

var len = arr.length;

var flag = 0;  // 用于记录是否遇到比他大的数

for (var i = 1; i < len; i++) {

    var len2 = arr2.length;

    flag = 0;  // 每次遍历的时候先重置标志

    for (var j = 0; j < len2; j++) {

        // 当遇到比他大的数，则插入到那个数前面，并将标志记为1

        if (arr[i] < arr2[j]) {

            arr2.splice(j, 0, arr[i]);

            flag = 1;

            break;

        }

    }

    // 如果标志为0，说明没遇到比他大的，则放在最后

    if (flag === 0) {

        arr2.push(arr[i]);

    }

}

二分法排序：
核心思想：将数组中的每个元素取出，往新数组中插入，与插入排序不同之处在于：插入排序是一个个的遍历，如果数据量较大，影响效率；二分法则不用一个个遍历，而是在插入的时候与新数组中的中间点进行比较，如果比中间点大，则又和后半截的中间点进行比较，直到找到合适的位置插入。

var arr = [43, 12, 5, 64, 23, 95, 6, 34, 72, 60];

var arr2 = [];

arr2[0] = arr[0];

var len = arr.length;

var left = 0;  // 左边界

var right = 0;  // 右边界

var middle = 0;  // 中间点

for (var i = 1; i < len; i++) {

    left = 0;

    len2 = arr2.length;

    right = len2;

    // 这里可以使用 while(true)，这样写是为了安全起见

    for (var j = 0; j < len2; j++) {

        middle = Math.floor((left + right) / 2);

        // 判断中间点的数与插入的数的大小，移动 left 或 right

        if (arr2[middle] < arr[i]) {

            left = middle + 1;

        } else {

            right = middle;

        }

        // 当 left 等于 right 的时候，则找到插入的点

        if (left === right) {

            arr[2].splice(left, 0, arr[i]);

            break;

        }

    }

}

快速排序：

采用了二分法排序的思想，使用递归的方式进行排序。

function quickSort(arr){

    if(arr.length<=1){  //数组长度小于等于1，则不用排序，返回结果

        return arr;

    }

    var num=Math.floor(arr.length/2);  //找到基准点

    var numValue=arr.splice(num,1);  //取出基准点

    var left=[];

    var right=[];

    for(var i=0;i<arr.length;i++){

        if(arr[i]<numValue){

            left.push(arr[i]);

        }else{

            right.push(arr[i]);

        }

    }

    return quickSort(left).concat([numValue],quickSort(right));  //对左边进行递归排序的结果+基准点+对右边进行递归排序的结果，就是排序完成的结果，返回

}

巴特西

JS 排序算法

最新文章

热门文章