js排序 6种

[h476564406]

一. 冒泡排序

如果有n个数字，只用比较 n-1 次，就能得出n个数字里的最大数。
两次循环。
两两比较交换。

const arr = [5, 1, 3, 8, 2];

function bubbleSort(arr) {
            const len = arr.length;

            /*  外部for循环，每循环一次，就能排好一个最大数。
            for (var i = 0; i < len - 1; i++) {
                // 内部for循环，用来两两比较，直到把大数移到末尾。
                for (var j = 0; j < len - i - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        const temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }

            return arr;
        }

console.log('bubbleSort', bubbleSort(arr.slice()));

二.快速排序

1. 找到一个中位数， 把数组分为左右。 pivot left right
2. 遍历数组，只要元素<中位，就移入左数组，大于中位，就移入右数组。
3. 递归处理左数组，递归处理右数组， 合并左右数组。

 const arr = [5, 1, 3, 8, 2];

function quickSort(arr) {
    if (arr.length <= 1) { return arr; }
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr.splice(pivotIndex, 1)[0];
    const left = [];
    const right = [];
    for (let index = 0; index < arr.length; index++) {
        if (arr[index] < pivot) {
            left.push(arr[index]);
        } else {
            right.push(arr[index]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}
console.log('quickSort', quickSort(arr.slice()));

三. 选择排序

两次循环。
得出最小数arr[minIndex]，放置在首位。

function selectionSort(arr) {
    let len = arr.length;
    let minIndex;
    let temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        // i之后的数字都和arr[minIndex]比, 得到最小数的位置
        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;
}

console.log('selectionSort', selectionSort(arr.slice()));

四 . 合并排序

分成左右序列， left right
不断拆分成左(右)序列，
使每个子序列都有序,
合并左右序列。 res

function mergeSort(arr) {
    console.log('arr', arr);
    const len = arr.length;

    if (len < 2) {
        return arr;
    }

    const middle = Math.floor(len / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

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

function merge(left, right) {
    const res = [];

    while (left.length && right.length) {
        if (left[0] < right[0]) {
            res.push(left.shift());
        } else {
            res.push(right.shift());
        }
    }

    while (left.length) {
        res.push(left.shift());
    }

    while (right.length) {
        res.push(right.shift());
    }

    return res;
};

console.log('mergeSort', mergeSort(arr.slice()));

五. 插入排序
假设第一个数字是最小值。
两次循环。

function insertionSort(arr) {
    console.time('插入排序耗时：');
    for (var i = 1; i < arr.length; i++) {
        var key = arr[i];
        // 记录有序数列的最后一个位子
        var j = i - 1;
        // 如果当前数字比前面有序数列中的数字都要小， 有序数列的位置都顺延1， 值被插入到最前面即位置0。  arr[-1+ 1] = key;
       // 如果当前数字比前面有序数列中的某个位置要大，停止顺延，插入到这个位置之后。arr[j + 1] = key;
        while (j >= 0 && key < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    console.timeEnd('插入排序耗时：');
    return array;
}

console.log('insertionSort', insertionSort([10, 9, 1]));

六. 计数排序

function countingSort(arr) {
    let len = arr.length;
    // 排好序的数组
    const B = [];
   // 计数的数组
    const C = [];

    let min = arr[0];
    let max = arr[0];

    // 找出数组中的最大，最小值。对每个数值计数。
    for (var i = 0; i < len; i++) {
        min = min <= arr[i] ? min : arr[i];
        max = max >= arr[i] ? max : arr[i];
        C[arr[i]] = C[arr[i]] ? C[arr[i]] + 1 : 1;
    }

    console.log(min, max, 'C', C);

    // min和max之间的数字
    for (var j = min; j < max; j++) {
        // 计数包括等大的和比它小的数字。因此后面的计数值会越来越大或者相等。
        C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
    }
    
    for (var k = len - 1; k >= 0; k--) {
        // 该值的计数-1（因为0算一个位置）为在B中的索引位置。
        B[C[arr[k]] - 1] = arr[k];
        // 该值的计数-1， 表示该数值已经排好一个。以免有两值相等的时候重复占据B数组中的位置。
        C[arr[k]]--;
    }

    return B;
}

console.log('countingSort', countingSort([6, 2, 3, 18, 2]));

七. 堆排序