JS 排序学习记录_代码007(未授权)

本文介绍: 分割操作：通过一趟排序，将待排序序列分割成两部分，使得左边的元素都小于等于基准元素，右边的元素都大于等于基准元素。在分割过程中，可以使用两个指针（称为i和j），分别从序列的两端开始，然后向中间移动，直到i遇到大于基准元素的元素，j遇到小于基准元素的元素，然后交换这两个元素，重复这个过程直到i和j相遇。在合并操作中，需要创建一个临时数组来存储合并后的有序序列，然后按照顺序从两个子序列中选择较小的元素放入临时数组中，直到一个子序列中的所有元素都被选择完毕，然后将另一个子序列中剩余的元素依次放入临时数组中。

快速排序（Qui c k So rt）是一种常用的排序算法，其原理基于分治策略。快速排序的基本思想是通过选择一个基准元素（pivot），将待排序序列分割成两部分，一部分所有元素小于等于基准元素，另一部分所有元素大于等于基准元素，然后对这两部分分别进行递归排序，最终得到有序序列。

具体步骤如下：

快速排序的平均时间复杂度为O(nlogn)，其中n是待排序序列的长度。它是一种原地排序算法，不需要额外的空间开销。然而，最坏情况下的时间复杂度为O(n^2)，即当待排序序列已经有序或近乎有序时。为了改进最坏情况下的性能，可以采用随机选择基准元素或者三数取中法来选择基准元素。

// 快速排序
const quickSort = (nums) =&gt; {
    // 以中间值作为标准。
    if (nums.length &lt;= 1) return nums;
    const mid = Math.floor(nums.length / 2), aim = nums.splice(mid, 1)[0];
    // console.log(aim, mid);
    let left = [], right = [];

    for (let i = 0; i &lt; nums.length; i++) {
        const ele = nums[i];
        if (ele &gt; aim) {
            right.push(ele)
        } else {
            left.push(ele);
        }
    }
    
    // console.log(left, right, aim);
    return quickSort(left).concat([aim], quickSort(right))
}


const arr = [2, 34, 21, 23, 44, 9]
console.log(quickSort(arr));

归并排序（Merge Sort）是一种基于分治策略的排序算法，其原理是将待排序序列不断地分割成较小的子序列，然后将这些子序列合并成一个有序序列。

具体步骤如下：

// 归并排序
const mergeSort = (nums) =&gt; {
    // 分割操作：将待排序序列递归地分割成两个子序列，直到每个子序列只包含一个元素或为空。
    if (nums.length &lt; 2) return nums;
    const mid = Math.floor(nums.length / 2)
    const left = nums.slice(0, mid);
    const right = nums.slice(mid)
    // 合并操作：将分割后的子序列两两合并，通过比较元素的大小，按顺序将它们合并成一个有序序列。重复这个过程，直到所有子序列合并成一个完整的有序序列。
    const merge = (leftArr = [], rightArr = []) =&gt; {
        let arr = [];
        while (leftArr.length &amp;&amp; rightArr.length) {
            arr.push(leftArr[0] < rightArr[0] ?
                leftArr.shift()
                :
                rightArr.shift()
            )
        }
        return arr.concat(leftArr, rightArr);
    }
    return merge(mergeSort(left), mergeSort(right))
}
const arr = [2, 34, 21, 23, 1, 44, 9]
console.log(mergeSort(arr));

// 插入排序。
const insertSort = (nums) => {
    const len = nums.length;
    for (let i = 1; i < len; i++) {
        const ele = nums[i];
        let j = i - 1;
        while (j >= 0 &amp;&amp; nums[j] < ele) {
            nums[j + 1] = nums[j]
            j--;
        }
        nums[j + 1] = ele;
    }
    return nums;
}
const arr = [2, 34, 21, 23, 1, 44, 9]
console.log(insertSort(arr));

const bubbleSort = (nums) => {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = 0; j < nums.length - 1 - i; j++) {
            if (nums[j + 1] < nums[j]) {
                const temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
    return nums;
}
const arr = [2, 34, 21, 23, 1, 44, 9]
console.log(bubbleSort(arr));

const selectSort = (nums) => {
    for (let i = 0; i < nums.length - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < nums.length - 1; j++) { // 选择最小值的索引
            if (nums[minIndex] > nums[j]) {
                minIndex = j;
            }
        }
        let temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
    }
    return nums;
}
const arr = [2, 34, 21, 23, 1, 44, 9]
console.log(bubbleSort(arr));