排序算法

通用交换元素位置的代码

function swap(a, b) {
    const temp = a;
    a = b;
    b = temp;
}

冒泡排序（Bubble Sort）

details

冒泡排序是最简单的排序算法之一，它的基本思想是从数组的左边开始，两两比较相邻的元素，如果左边的元素比右边的元素大，则交换它们的位置。每一轮比较都可以把最大的元素交换到数组的右侧，因此称之为冒泡排序。

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

时间复杂度

最优时间复杂度：$O(n)$ （当数组已经有序时） 最坏时间复杂度：$O(n^2)$ 平均时间复杂度：$O(n^2)$ 空间复杂度：$O(1)$

选择排序（Selection Sort)

选择排序的基本思想是从数组的左侧开始，依次找到最小的元素，将它和数组的第一个元素交换位置。然后从数组的第二个元素开始，依次找到剩下元素中最小的元素，将它和数组的第二个元素交换位置。以此类推，直到整个数组排序完成。

function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

插入排序（Insertion Sort）

插入排序的基本思想是将数组分为已排序和未排序两个部分，从未排序部分依次取出元素，插入到已排序部分的合适位置，直到整个数组排序完成。

function insertionSort(arr) {
    const n = arr.length;
    for (let i = 1; i < n; i++) {
        const key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

快速排序（Quick Sort）

快速排序是一种基于分治思想的排序算法，它的基本思想是选取一个基准元素，将数组分为左右两部分，左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于基准元素。然后递归地对左右两部分进行排序，最终完成整个数组的排序。 快速排序的时间复杂度为 O(nlog n)，在大多数情况下表现比插入排序、冒泡排序和选择排序要好。

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

归并排序（Merge Sort）

归并排序也是一种常用的排序算法，它将待排序数组分成两部分，分别对这两部分进行排序，然后再将它们合并成一个有序数组。归并排序是一种稳定的排序算法，其时间复杂度为 O(nlogn)

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const midIndex = Math.floor(arr.length / 2);
    const left = arr.slice(0, midIndex);
    const right = arr.slice(midIndex);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

堆排序 (Heap Sort)

它的时间复杂度为 O(nlogn)，其中 n 是待排序元素的数量。堆排序的核心思想是先将待排序的数据构建成一个堆，然后重复从堆中取出最大元素并删除，直到堆为空，取出的元素就是排序好的结果。

// 交换数组中两个元素的位置
function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 构建最大堆
function buildMaxHeap(arr) {
    // 从最后一个非叶子节点开始向上构建最大堆
    for (let i = ((arr.length - 2) / 2) >> 0; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
}

// 堆化
function heapify(arr, i, len) {
    let largest = i; // 初始化最大元素为当前节点
    const left = 2 * i + 1; // 左子节点
    const right = 2 * i + 2; // 右子节点

    // 如果左子节点比当前节点大，则更新最大元素为左子节点
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点比最大元素大，则更新最大元素为右子节点
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大元素不是当前节点，则交换当前节点和最大元素的位置，并递归地对交换后的子树进行堆化
    if (largest !== i) {
        swap(arr, i, largest);
        heapify(arr, largest, len);
    }
}

// 堆排序
function heapSort(arr) {
    buildMaxHeap(arr); // 构建最大堆
    console.log('arr is ', arr);
    // 从堆中依次取出最大元素并删除，直到堆为空，取出的元素就是排序好的结果
    for (let i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i); // 将最大元素移动到数组末尾
        heapify(arr, 0, i); // 对剩余元素进行堆化
    }

    return arr;
}

// 示例
const arr = [6, 2, 8, 5, 9, 1];
console.log(heapSort(arr)); // [1, 2, 5, 6, 8, 9]