JavaScript之常见算法排序

冒泡排序

冒泡 排序 即从头到尾依次比较相邻两数的大小，不符合顺序则交换位置，一直循环直到排序完成；

但方便程序编写的做法是，从第一个到最后一个数，每个数分别与排在后面每个数进行比较和交换位置；

// 输入值 arr 为需要排序的数组
// 后面的代码类似
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                let tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    return arr;
}

选择排序

选择排序与冒泡排序类似，从第一个数到最后一个数，分别与排在后面的每个数进行比较，只不过不用每次比较都交换位置，一次遍历记录一个最小值或最大值，此次遍历结束后再与记录的极值交换位置；

function selectSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let min = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) min = j;
        }
        let tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
    return arr;
}

插入排序

插入排序即从第二个到最后一个数，每个数分别与排在前面的每个数进行比较，然后插入合适的位置使其有序；

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let tmp = arr[i];
        for (let j = i; j > 0; j--) {
            if (tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                
            } else {
                arr[j] = tmp;
                break;
            }
        }
    }
    return arr;
}

快速排序

快速排序在数组中任选一个数（下面选第一个数）作中间值，然后将余下的数分别与其比较，比中间值小则放到左边，否则放右边，然后再进行递归，将放在左边和右边的数组分别作为新数组进行同样的排序操作，直到数组不能再分，最后将所有排序结果合并；

function quickSort(arr) {
    if (ar.length === 0) {
        return arr;
        
    } else {
        let mid = arr[0],
            left = [],
            right = [];
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < mid) {
                left.push(arr[i]);
                
            } else {
                right.push(arr[i]);
            }
        }
        return quickSort(left).
            concat(mid).
            concat(quickSort(right));
    }
}

归并排序

归并排序递归地将数组分割为两个部分（左数组与右数组），直到不能再分，然后再定义一个合并函数，负责将两部分合并为一个有序数组作为返回值；

合并函数其实会是合并两个有序的数组，合并方法便是分别将两数组第一个数取出（删除）放入返回数组中，至于两个数先放哪一个，可以通过比较大小来确定；

function mergeSort(arr) {
    if (arr.length < 2) {
        return arr;
        
    } else {
        let mid = Math.ceil(arr.length / 2);
        let left = arr.slice(0, mid);
        let right = arr.slice(mid);

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

function merge(left, right) {
    let result = [];
    while (left.length + right.length > 0) {
        if (!left[0]) {
            result = result.concat(right);
            right = [];
            
        } else if (!right[0]) {
            result = result.concat(left);
            left = [];
            
        } else {
            if (left[0] < right[0]) {
                result = result.concat(left.shift());
                
            } else {
                result = result.concat(right.shift());
            }
        }
    }
    return result;
}