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

排序

1、快速排序

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

具体步骤如下

  1. 选择基准元素:从待排序序列中选择一个元素作为基准元素(通常选择第一个最后一个元素)。

  2. 分割操作:通过一趟排序,将待排序序列分割两部分,使得左边的元素都小于等于基准元素,右边的元素都大于等于基准元素。在分割过程中,可以使用两个指针(称为i和j),分别从序列的两端开始,然后向中间移动,直到i遇到大于基准元素的元素,j遇到小于基准元素的元素,然后交换这两个元素,重复这个过程直到i和j相遇。

  3. 递归排序:对基准元素左右两部分的子序列分别进行递归排序,直到每个子序列只包含一个元素或为空

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

// 快速排序
const quickSort = (nums) => {
    // 以中间值作为标准。
    if (nums.length <= 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 < nums.length; i++) {
        const ele = nums[i];
        if (ele > 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));

2、归并排序

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

具体步骤如下

  1. 分割操作:将待排序序列递归分割成两个子序列,直到每个子序列只包含一个元素或为空

  2. 合并操作:将分割后的子序列两两合并,通过比较元素的大小,按顺序将它们合并成一个有序序列。重复这个过程,直到所有子序列合并成一个完整的有序序列。

在合并操作中,需要创建一个临时数组来存储合并后的有序序列,然后按照顺序从两个子序列中选择较小的元素放入临时数组中,直到一个子序列中的所有元素都被选择完毕,然后将另一个子序列中剩余的元素依次放入临时数组中。

归并排序的时间复杂度是O(nlogn),其中n是待排序序列的长度。它是一种稳定的排序算法,不会改变相等元素的相对顺序。归并排序的缺点是需要额外空间来存储临时数组,空间复杂度为O(n)。然而,由于归并排序的递归特性,其空间复杂度可以通过优化算法实现降低到O(1)。

// 归并排序
const mergeSort = (nums) => {
    // 分割操作:将待排序序列递归地分割成两个子序列,直到每个子序列只包含一个元素或为空。
    if (nums.length < 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 = []) => {
        let arr = [];
        while (leftArr.length && 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));

3、插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法,其原理是将待排序序列分为已排序和未排序两部分,然后从未排序部分中选择一个元素,插入到已排序部分中的正确位置,使得已排序部分仍保持有序。

具体步骤如下

  1. 第一个元素开始,认为该元素已经被排序。

  2. 取出未排序部分的第一个元素,在已排序部分中从后向前扫描,找到该元素应该插入的位置

  3. 将已排序部分中该位置以后的所有元素后移一位,然后将该元素插入到正确位置

  4. 重复步骤2-3,直到所有元素都被插入到已排序部分中。

插入排序过程中,为了将一个元素插入到正确位置需要比较它和已排序部分中的元素大小。如果已排序部分中的元素比它大,则将该元素后移一位,否则将该元素插入到该位置。这样,每次插入一个元素后,已排序部分的长度增加1,未排序部分的长度减少1,最终将所有元素按照从小到大顺序插入到已排序部分中。

插入排序时间复杂度取决于输入序列的初始状态,最好情况下时间复杂度为O(n),即输入序列已经有序,每个元素只需要比较一次。最坏情况下时间复杂度为O(n^2),即输入序列是逆序的,每个元素需要比较n-1次。平均情况下时间复杂度为O(n^2)。插入排序是一种稳定的排序算法,相等元素的相对顺序不会改变。它的空间复杂度为O(1),不需要额外空间来存储数据

// 插入排序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));

4、冒泡排序

冒泡排序(Bubble Sort)是一种简单直观的排序算法,其原理多次遍历待排序序列,每次比较相邻的两个元素,如果它们的顺序不正确,则交换这两个元素的位置,直到整个序列有序。

具体步骤如下

  1. 从序列的第一个元素开始,依次比较相邻的两个元素,如果它们的顺序不正确,则交换它们的位置。

  2. 继续遍历序列,重复上述操作,直到最后一个元素,此时最后一个元素已经排好序。

  3. 对除最后一个元素外的所有元素重复上述操作,直到整个序列有序。

冒泡排序过程中,每次遍历都会将当前未排序部分的最大元素“浮”到未排序部分的最后,因此称为“冒泡”。通过多次遍历,每次将未排序部分的最大元素放置到正确的位置,最终得到整个序列有序。

冒泡排序的时间复杂度为O(n^2),其中n是待排序序列的长度。它是一种稳定的排序算法,相等元素的相对顺序不会改变。冒泡排序的缺点是排序速度较慢,不适合处理大规模数据

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));

5、选择排序

选择排序(Selection Sort)是一种简单直观的排序算法,其原理是每次从待排序序列中选择最小(或最大)的元素,将其放置在已排序部分的末尾(或开头),直到整个序列有序。

具体步骤如下

  1. 在未排序部分中找到最小(或最大)的元素。

  2. 将该最小(或最大)元素与未排序部分的第一个元素交换位置,将其放置在已排序部分的末尾(或开头)。

  3. 扩大已排序部分的范围,继续执行步骤1-2,直到整个序列有序。

在选择排序的每一次遍历中,都会确定一个元素的最终位置。通过多次遍历,每次选择未排序部分的最小(或最大)元素放置到已排序部分的末尾(或开头),最终得到整个序列有序。

选择排序的时间复杂度为O(n^2),其中n是待排序序列的长度。无论输入序列的初始状态如何,每次遍历都需要找到最小(或最大)元素,因此需要进行n-1次遍历。选择排序是一种不稳定的排序算法,相等元素的相对顺序可能会发生改变。选择排序的优点是简单易实现,不需要额外空间,只需要进行元素的比较和交换即可。然而,选择排序的缺点是每次遍历都需要找到最小(或最大)元素,效率相对较低,不适合处理大规模数据

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));

原文地址:https://blog.csdn.net/ggbee_/article/details/134750469

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_25826.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注