排序算法

• 一般用来对乱序数组的值的大小（偶尔可能是对象的某个权重属性）进行排序。

• 排序的稳定性：稳定性是指排序算法在排序过程中能够保持相等元素的相对位置不变。换句话说，如果原始数组中存在两个相等的元素 a 和 b，且在排序后，a 仍然在 b 的前面，那么这个排序算法就是稳定的。

• V8引擎是 “插入排序和快速排序结合”。数组长度不超过10时，使用插入排序。长度超过10使用快速排序。在数组较短时插入排序更有效率。

冒泡排序(稳定)

• 依次比较相邻的元素，如果顺序不对就交换它们，直到没有需要交换的元素为止
• 但是某个数到达最终位置之前存在很多的交换
• 较高的时间复杂度

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

选择排序

• 每次从未排序的部分选择最小（或最大）的元素，并将其与未排序部分的第一个元素交换位置
• 较高的时间复杂度

function selectionSort(arr) {
    const len = arr.length
    for (let i = 0; i < len; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j
            }
        }
        // 相同不交换，如果不加这句话，排序就存在不稳定性，同时有很多无意义的交换
        if (arr[minIndex] !== arr[i]) {
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
        }
    }
    return arr
}

插入排序(稳定)

• 将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素插入到已排序部分的正确位置
• 插入以后所有的后续子项都要往后挪动一位
• 如果数组的大部分元素已经有序，插入排序仍然需要逐个比较和移动元素，导致性能下降

function insertionSort(){
    const len = arr.length

    for (let i = 1; i < len; i++) {
        // 插入位置，或者说排序与未排序项之间的分界线
        let insetIndex = i - 1;
        // 当前待定插入的值，因为不存的话，一会排序挪动的时候就丢失了
        let curVal = arr[i];
        while (insetIndex >= 0 && curVal < arr[insetIndex]) {
            arr[insetIndex + 1] = arr[insetIndex];
            insetIndex--;
        }
        // 结束出来说明insetIndex的值已经为-1或者arr[insetIndex]比curVal要小了
        // 所以在insetIndex + 1位置放入
        arr[insetIndex + 1] = curVal;
    }
    return arr
}

希尔排序(插入排序改良)

• 通过将整个数组分为若干个子序列，并对每个子序列进行插入排序，逐渐减小子序列的长度，最终完成整个数组的排序
• 通常为O(n logn)到O(n^2)之间。在实践中，希尔排序的平均时间复杂度约为O(n^1.3)

function shellSort(arr) {
    let len = arr.length;
    // 初始步数
    let gap = len >> 1;
    // 逐渐缩小步数
    while (gap) {
        // 从第gap个元素开始遍历
        for (let i = gap; i < len; i++) {
            // 逐步其和前面其他的组成员进行比较和交换
            while ( j >= 0&&arr[j] > arr[j + gap] ) {
                [arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
                j -= gap
            }
        }
        gap = gap >> 1;
    }
    return arr
}

快速排序

• 通过选取一个基准值，将数组分为左右两部分，左边的元素都小于基准值，右边的元素都大于基准值，然后递归地对左右两部分进行排序
• 平均时间复杂度为 (O(n * log n))，原地排序，但最坏情况下时间复杂度为 (O(n^2))
• 当数据量较小时，快速排序的性能可能会比较差。这是因为快速排序的递归深度较大，而且在小规模数据上，其他排序算法如插入排序可能更有效率

function quickSort(arr) {
    function helper(arr) {
        const len = arr.length;
        if (len < 2) return arr
        const mid = 0; // mid取谁都一样
        const left = [], right = [];
        for (let i = 0; i < len; i++) {
            // 这里注意一定要把mid提出来，否则对于[1,2,2]这种会陷入死循环
            // 这里配合len<2可以结束循环
            // 如果使用splice方法取出mid，但是会带来一个O(n)的开销用来移动数组子项
            if (i != mid)
                arr[i] > arr[mid] ?
                    right.push(arr[i]) :
                    left.push(arr[i])
        }
        return [...helper(left), arr[mid], ...helper(right)]
    }
    return helper(arr)
}

归并排序(稳定)

• 将数组分为两个子数组，分别对子数组进行排序，然后合并两个有序子数组
• 递归上述这个过程，即可实现
• 时间复杂度为 (O(n * log n))，稳定排序算法，但需要额外的空间来合并子数组

// 定义在外面防止每次递归mergeSort都重新定义一次merge
const merge = (left, right) => {
    const result = [];
    let leftIndex = 0, rightIndex = 0;
    // 每次从取两个数组中较小值放进result
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] > right[rightIndex]) {
            result.push(right[rightIndex]);
            rightIndex++;
        } else {
            result.push(left[leftIndex]);
            leftIndex++;
        }
    }
    while (leftIndex < left.length) {
        result.push(left[leftIndex++])
    }
    while (rightIndex < right.length) {
        result.push(right[rightIndex++])
    }
    return result
}
function mergeSort(arr) {
    const len = arr.length;
    if (len < 2) return arr
    const mid = len >> 1;
    return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}

堆排序

• 利用堆这种数据结构进行排序，首先构建一个最大堆或最小堆，然后依次将堆顶元素与堆底元素交换并调整堆，直到整个堆有序
• 实际上数组是一个天然的堆，或者看做成一棵树，保证每个树父节点比子节点大
• 时间复杂度为 (O(n * log n))，原地排序

解释上文：

每个数字表示数组的序号，可以看到每个树的父节点如果是n，子节点分别是2n+1和2n+2

function heapSort(arr) {
    function swap(i, j) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    function max_heapify(start, end) {
        let son = start * 2 + 1;
        // 这句话用来限制堆访问的深度，防止对已经排序的又做了替换
        if (son >= end) return
        // 如果左孩子小于右孩子，最大值取右孩子
        if (son + 1 < end && arr[son] < arr[son + 1]) {
            son++;
        }
        if (arr[son] > arr[start]) {
            swap(son, start);
            // 一旦发生了交换则这个son可能不是包括左孩子和右孩子的最大值
            max_heapify(son, end);
        }
    }
    const len = arr.length
    const mid = len >> 1;
    // 这里要从下往上，同时只需要取中点就可以一次遍历到所有的值
    for (let i = mid - 1; i >= 0; i--) {
        max_heapify(i, len);
    }
    // 这个时候arr[0]已经是最大值了
    for (let j = len - 1; j > 0; j--) {
        // 把最大值排到堆的最下方
        swap(0, j)
        // 重新构建堆
        max_heapify(0, j)
    }
    return arr
}

计数排序(稳定)

• 适用于已知数据范围的整数排序，统计每个元素出现的次数，然后根据统计信息重新生成排序后的数组(leetcode常见的hash题)
• 时间复杂度为 (O(n + k))，其中 (k) 是数据范围的大小，但需要额外空间
• 劣势很明显，如果数组中的maxValue太大了，就很影响性能

function countingSort(){
    const max = Math.max(...arr);
    const count = new Array(max + 1).fill(0);
    for (let i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }
    const res = [];
    for (let i = 0; i <= max; i++) {
        while (count[i]--) {
            res.push(i);
        }
    }
    return res;
}

桶排序

• 是一种分布排序算法，它将待排序的元素分散到有限数量的桶中，每个桶再分别进行排序，最后将所有的桶中的元素按顺序合并起来，从而得到排好序的序列
• 桶排序通常适用于待排序元素均匀分布在一个范围内的情况下，它的效率在这种情况下会比较高
• 换句话说，当min与max差距很大的时候，桶排序会极大的消耗内存空间
• 桶排序的稳定性取决于对每个非空桶中的元素进行排序时所选用的排序算法

个人感觉这个排序是没啥用的,别看了

function bucketSort(arr, bucketSize = 5) {
    if (arr.length === 0) {
        return arr;
    }
    // 找出最大值和最小值
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    // 计算桶的数量
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;
    const buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }
    // 将元素分配到桶中
    for (let i = 0; i < arr.length; i++) {
        const index = Math.floor((arr[i] - min) / bucketSize);
        buckets[index].push(arr[i]);
    }
    // 对每个桶进行排序，并将结果合并
    const res = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i].length) {
            // 这里用什么排序都可以，取决于数组的特性
            const sortedBucket = insertSort(buckets[i]);

            for (let j = 0; j < sortedBucket.length; j++) {
                res.push(sortedBucket[j]);
            }
        }
    }
    return res;
}
function insertSort(arr) {
    let len = arr.length
    if (len < 2) return arr
    for (let i = 1; i < len; i++) {
        let preIndex = i - 1
        let curNode = arr[i]
        while (preIndex >= 0 && curNode < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex]
            preIndex--
        }
        arr[preIndex + 1] = curNode
    }
    return arr
}