插入排序

假设第一项已经排序好了，将它和第二项作比较，判断第二项是否和它交换位置，以此类推来完成排序。

源码：

import {
    defaultCompare
} from "../utils/index.js";

function insertSort(array, compareFn = defaultCompare) {
    let temp;
    for (let index = 1; index < array.length; index++) {
        let key = index;
        temp = array[index];
        while (key > 0 && compareFn(array[key - 1], temp) === 1) {
            array[key] = array[key - 1]
            key--;
        }
        array[key] = temp;
    }

    return array;
}

const arr = [3, 5, 2, 1, 3, 7, 0]
console.log(insertSort(arr))

代码的循环体中的index是从1开始的，因为第0项我们已经假设它排序好了，直接把它和第二项作比较。

归并排序

JavaScript中的Array类定义了一个sort函数【Array.prototype.sort】，用来排序JavaScript数组，这里面它没有说明用的是哪一种排序算法，所以浏览器厂商可以自己实现算法。比如火狐浏览器使用了归并排序作为Array.prototype.sort的实现，而谷歌【V8引擎】使用了一个快速排序的变体。

归并排序是一种分而治之的算法，思路是将原数组拆分为比较小的数组，直到每个小数组只有一个位置，再将小数组归并成比较大的数组，最后只有一个排序完成的数组。

归并排序也是使用了递归的方式，首先要定义两个函数，一个负责将大数组拆分为小数组的函数，一个是调用用来排序的辅助函数

代码：

function mergeSort(array, compareFn = defaultCompare) {
    if (array.length > 1) {
        const {
            length
        } = array;
        const middle = Math.floor(array.length / 2);
        const left = mergeSort(array.slice(0, middle), compareFn);
        const right = mergeSort(array.slice(middle, length), compareFn);

        array = merge(left, right, compareFn)
    }
    return array;
}

辅助排序函数：merge

function merge(left, right, compareFn) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(compareFn(left[i], right[j]) === -1 ? left[i++] : right[j++]);
    }

    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

快速排序

快速排序也是分而治之的算法，同样也是将数组拆分为多个较小的数组，它和归并排序不同的是拆分数组的方式不同。

思路：

1、从数组中选择一个值作为pivot，也就是数组中的那个值

2、创建两个指针，左指针指向数组的第一个值，右指针指向数组的最后一个值。移动左指针一直找到比pivot大的值，然后交换它们。重复这个流程直到左指针超过了右指针。最后把比pivot小的值排在pivot前面，比pivot大地值排在pivot后面。

import {
    swap,
    defaultCompare
} from "../utils/index.js";

function quickSort(array, compareFn = defaultCompare) {
    // left指向数组首位，right指向数组末位
    return quick(array, 0, array.length - 1, compareFn)
}

function quick(array, left, right, compareFn) {
    let index;
    if (array.length > 1) {
        index = partition(array, left, right, compareFn);
        if (left < index - 1) {
            quick(array, left, index - 1, compareFn);
        }

        if (index < right) {
            quick(array, index, right, compareFn)
        }
    }
    return array
}

// 划分
function partition(array, left, right, compareFn) {
    const pivot = array[Math.floor(right + left) / 2];
    let i = left;
    let j = right;
    while (i <= j) {
        while (compareFn(array[i], pivot) === -1) {
            i++;
        }
        while (compareFn(array[j], pivot) === 1) {
            j--;
        }
        if (i <= j) {
            swap(array, i, j);
            i++;
            j--;
        }
    }
    return i
}

这样在JavaScript中很容易超出最大调用栈。

计数排序

计数排序是一个分布式排序，使用已经组织好的辅助数据结构，然后进行合并，完成排序任务。

 function findMaxValue(array) {     let max = array[0];     for (let index = 0; index < array.length; index++) {         if (array[index] > max) {             max = array[index]         }     }     return max; } function countSort(array) {     if (array.length < 2) {         return array     }     const maxValue = findMaxValue(array);     const counts = new Array(maxValue + 1);     array.forEach(item => {         if (!counts[item]) {             counts[item] = 0;         }         counts[item]++;     });     let sortIndex = 0;     counts.forEach((item, i) => {         while (item > 0) {             array[sortIndex++] = i;             item--;         }     })     return array }

桶排序

也是将元素分解为多个较小的数组，然后再使用一个简单的排序算法对每一个桶进行排序，最后合并所有的桶

/** * 桶排序 */import {    insertSort} from "./insertSort.js";function bucketSort(array, size = 5) {    if (array.length < 2) {        return array;    }    const buckets = createBuckets(array, size);    return sortBuckets(buckets);}// 创建桶const createBuckets = (arr, size) => {    let minValue = arr[0];    let maxValue = arr[0];    arr.forEach((item, key) => {        if (arr[key] < minValue) {            minValue = arr[key];        } else if (arr[key] > maxValue) {            maxValue = arr[key]        }    });    // 桶的基数    const bucketCount = Math.floor((maxValue - minValue) / size) + 1;    const buckets = [];    for (let index = 0; index < bucketCount; index++) {        buckets[index] = [];    }    arr.forEach((item, index) => {        const bucketIndex = Math.floor((arr[index] - minValue) / size);        buckets[bucketIndex].push(arr[index]);    })    return buckets}// 对桶进行排序const sortBuckets = (buckets) => {    const sortArray = [];    buckets.forEach((item, index) => {        if (buckets[index] != null) {            insertSort(buckets[index]);            sortArray.push(...buckets[index])        }    })    return sortArray}console.log(bucketSort([43,65,2,1,678,3,54,0]))

基数排序

基数排序是依据数字的有效位，将整数分布到桶中去。

/** * 基数排序 */function radixSort(arr, radixBase = 10) {    if (arr.length < 2) {        return arr;    }    const minValue = findMinValue(arr);    const maxValue = findMaxValue(arr);    let significantDigit = 1;    while ((maxValue - minValue) / significantDigit >= 1) {        arr = countSortForRadix(arr, radixBase, significantDigit, minValue);        significantDigit *= radixBase;    }    return arr;}// 有效位【基数】排序function countSortForRadix(arr, radixBase, significantDigit, minValue) {    let bucketsIndex;    const buckets = [];    const aux = [];    for (let index = 0; index < radixBase; index++) {        buckets[index] = 0;    }    for (let index = 0; index < arr.length; index++) {        bucketsIndex = Math.floor(((arr[index] - minValue) / significantDigit) % radixBase);        buckets[bucketsIndex]++;    }    for (let i = 1; i < radixBase; i++) {        buckets[i] += buckets[i - 1]    }    for (let index = arr.length - 1; index >= 0; index--) {        bucketsIndex = Math.floor(((arr[index] - minValue) / significantDigit) % radixBase);        aux[--buckets[bucketsIndex]] = arr[index];    }    for (let index = 0; index < arr.length; index++) {        arr[index] = aux[index];    }    return arr}function findMaxValue(array) {    let max = array[0];    for (let index = 0; index < array.length; index++) {        if (array[index] > max) {            max = array[index]        }    }    return max;}function findMinValue(array) {    let min = array[0];    for (let index = 0; index < array.length; index++) {        if (array[index] < min) {            min = array[index]        }    }    return min;}console.log(radixSort([324,32,0,21,6,343,256,23,10]))

现在使用的基数是10，在排序中将使用10个桶来分布元素，并且首先基于个位数进行排序，然后是十位数，然后是百位数，这样往后推。