SOURCE

// 冒泡排序
/*
  思想: 让数组中的当前项，和后一项进行比较
  时间复杂度是：O(n^2)
*/
const bubblesort = (sortArr) => {
    let temp;
    // 外层循坏控制比较的次数
    for (let i = 0; i < sortArr.length; i++) {
        // 里层循环控制每一轮比较的次数
        let count = 0;
        for (let j = 0; j < sortArr.length - 1; j++) {
            if (sortArr[j] > sortArr[j + 1]) {
                // temp = sortArr[j];
                // sortArr[j] = sortArr[j + 1];
                // sortArr[j + 1] = temp;
                [sortArr[j], sortArr[j + 1]] = [sortArr[j + 1], sortArr[j]]
            };
            console.log(sortArr);
            count += 1;
        };
        console.log(`第${i + 1}轮结束，共比较${count}次`)
    };

    return sortArr;
};

// console.log(bubblesort([23, 54, 67, 57, 87, 798, 56, 1, 2, 2, 4]));

// 选择排序
/*
  思想: 让数组中的当前项，和后一项进行比较
        然后再从剩余的元素中寻找最小的元素，然后放到已排序序列的末尾。以此类推，直到排序完成。
*/
function selectionSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        let minIndex = i; // 假设当前位置为最小值
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小值位置
            }
        }
        if (minIndex !== i) {
            // 如果当前位置不是最小值，则交换当前位置和最小值位置
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

// console.log(selectionSort([23, 54, 67, 57, 87, 798, 56, 1, 2, 2, 4]))

// 快速排序
/*
  思想: 将原数组分为两个子数组，递归地对子数组进行排序，最终将子数组排序合并成有序的数组
  实现：
    选择一个基准元素（pivot），一般选择数组第一个元素或者随机选择一个元素。
    所有小于基准元素的放到左边，大于基准元素的放到右边。
    对左右两个小数组递归进行快速排序。
*/
// 快速排序（递归）
function quickSort(arr) {
    // 如果数组长度小于等于1，直接返回
    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), pivot, ...quickSort(right)];
}

console.log(quickSort([23, 54, 67, 57, 87, 798, 56, 1, 2, 2, 4]));