常用排序算法 | Hongxu's Blog

对于JS实现排序的 功能 来说本不需要什么算法。就用自带的函数
Array.sort() 然后指定处理函数就好了。
如下：

arr.sort(function (i, j){
    return i - j;
});

冒泡排序

function bubbleSort(arr) {
    var len = arr.length,
    i, j, tmp;
    for (i = 0; i < len; i++) {
        for (j = 0; j < len - 1 - i; j++) {
             if (arr[j+1] < arr[j]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
    return arr;
}

进化版

function bubbleSort(arr) {
    var i = arr.length - 1,
    j, pos, tmp;
    while (i > 0) {
        pos = 0;
        for (j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                pos = j;
                tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    return arr;
}

选择排序

每次循环找出当前最小的数字

function selectionSort(arr) {
    var  len = arr.len,
    i, j, minNumIndex;
    for (i = 0 ; i < len; i++) {
        minNumIndex = i;
        for ( j = i + 1; j < len; j++) {
            if (arr[j] < arr[minNumIndex]) {
                minNumIndex = j;
            }
        }
        tmp = arr[j];
        arr[i] = arr[minNumIndex];
        arr[minNumIndex] = tmp;
    }
    return arr;
}

插入排序

function insertionSort(arr) {
    var len = arr.length,
    i, j, key;
    for (i = 1; i < leng; i++) {
        key = arr[i];
        j = i - 1;
        while (arr[j + 1] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

二分插入排序

function instertionSortDichotomy(arr) {
    var len = arr.length,
    i, j, tmp, low, high, mid;
    for ( i = 1; i < len; i++) {
        tmp = arr[i];
        low = 0;
        high = i - 1;
        while (low <= high) {
            mid = parseInt((low + high) / 2, 10);
            if (tmp < arr[mid]){
                hight = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for(j = i - 1; j >= high + 1; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = tmp;
    }
    return arr;
}

希尔排序

先将整个待排序记录序列分割成若干个子序列
在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

function shellSort() {
    var len = arr.length,
    gap = parseInt(len / 2),
    i, j, tmp,

    while (gap > 0) {
        for (i = gap; i < len; i++) {
            tmp = arr[i];
            j = i - gap;
            while (j >= 0 && tmp < arr[j]) {
                arr[j + gap] = arr[j];
                j = j - gap;
            }
            arr[j + gap] = tmp;
        }
        gap = parseInt(gap / 2);
    }
    return arr;
}

归并排序

function mergeSort(arr) {
    var len = arr.length,
    middle, left, right;
    if (len < 2) {
        return arr;
    }
    middle = Math.floor(len / 2);
    left = arr.slice(0, middle);
    right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];
    while(left.length && right.length) {
        if(left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while(left.length) {
        result.push(left.shift());
    }
    while(right.length) {
        result.push(reight.shift());
    }

    return result;
}

快速排序

function quickSort(arr, left, right) {
    var x, i, j, tmp;
    if (left < right) {
        x = arr[right];
        i = left - 1;
        for (j = left; j <= right; j++) {
            if (arr[j] <= x) {
                i++
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
    return arr;
}

形象版快速排序

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;
    }
    var pivotIndex = Math.floor(arr.length / 2),
    pivot = arr.splice(pivotIndex, 1)[0],
    left = [],
    right = [],
    i;
    for (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));
}

疑惑？

为什么把 arr.length 改为 var len = arr.length; 然后用 len 统一替换就会出现溢出 Maximum call stack size exceeded