JavaScript 排序

• 出来混总是要还的，上学时候不认真学习，现在有时就懵圈了。
• 如果你能搜到我这篇文章，说明你也在懵圈中。哈哈，慢慢来吧！

以 arr 为例

var arr = [98, 14, 32, 54, 26, 62, 41, 77, 83];

一、sort() 方法

它只对数组内元素进行交换，不开辟新内存。

arr.sort();
// 自定义排序（a - b 为升序）
arr.sort(function(a,b) { return b - a; })

二、快速排序

中心思想如下：
1、在集合中选择一个元素作为基准 pivot；
2、遍历，将所有小于基准的元素移到基准的左边，大于的移到右边；
3、递归，对左右两个子集重复执行这一方法，直到子集中只存在一个元素位置。

function quickSort(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));
}

三、冒泡排序

简单粗暴，就是在遍历过程中，元素互换。

function bubbleSort(arr) {

    if (arr.length <= 1) { return arr; }

    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }

    return arr;
}

四、选择排序

和冒泡有点相似

function selectionSort(arr) {

    if (arr.length <= 1) { return arr; }

    var minIndex;

    for (var i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        var temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }

    return arr;
}

五、插入排序

怎么形容呢，你打过扑克么？

function insertionSort(arr) {

    if (arr.length <= 1) { return arr; }

    var preIndex, current;

    for (var i = 1; i < arr.length; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }

        arr[preIndex + 1] = current;
    }

    return arr;
}

未完待续（应该都能看懂，看不懂的枪毙5分钟）...