JavaScript 排序算法

原生 sort 方法实现方式

各个浏览器的实现方式会有不同, 火狐中使用的是归并排序,Chrome 是插入排序和快速排序结合的排序算法。数组长度不超过 10 时，使用插入排序。长度超过 10 使用快速排序。在数组较短时插入排序更有效率 参看文章

1. 冒泡排序

算法描述

算法实现

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) { //相邻元素两两对比
                var temp = arr[j+1]; //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

2. 快速排序

算法描述

算法实现

var quickSort = function (arr) {
    if (arr.length <= 1) {
        return arr;
    }
    var pivotIndex = Math.floor(arr.length / 2);
    var pivot = arr.splice(pivotIndex, 1)[0];
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
};

var devide_Xin = function (array, start, end) {
    if (start >= end) return array;
    var baseIndex = Math.floor((start + end) / 2), // 基数索引
        i = start,
        j = end;
    while (i <= j) {
        while (array[i] < array[baseIndex]) {
            i++;
        }
        while (array[j] > array[baseIndex]) {
            j--;
        }
        if (i <= j) {
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }
    return i;
};

var quickSort_Xin = function (array, start, end) {
    if (array.length < 1) {
        return array;
    }
    var index = devide_Xin(array, start, end);
    if (start < index - 1) {
        quickSort_Xin(array, start, index - 1);
    }
    if (end > index) {
        quickSort_Xin(array, index, end);
    }

    return array;
};

const quickSort_New = function (arr, left, right) {
    if (left >= right) {
        return arr;
    }

    let i = left;
    let j = right;
    base = arr[left];

    while (i < j) {
        // 从右边起，寻找比基数小的数
        while (i < j && arr[j] >= base) {
            j--;
        }
        // 从左边起，寻找比基数大的数
        while (i < j && arr[i] <= base) {
            i++;
        }
        if (i < j) {
            var temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[left] = arr[i];
    arr[i] = base;
    quickSort_New(arr, left, i - 1);
    quickSort_New(arr, i + 1, right);
    return arr;
};

3. 选择排序

算法描述

算法实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}