怎么用JavaScript实现七种排序算法

发布时间:2022-05-17 11:31:38 作者:zzz
来源:亿速云 阅读:111

本篇内容介绍了“怎么用JavaScript实现七种排序算法”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

冒泡排序

冒泡排序是入门级的算法,但也有一些有趣的玩法。通常来说,冒泡排序有三种写法:

一边比较一边向后两两交换,将最大值 / 最小值冒泡到最后一位;
经过优化的写法:使用一个变量记录当前轮次的比较是否发生过交换,如果没有发生交换表示已经有序,不再继续排序;

基础算法

空间复杂度为 O(1),时间复杂度为 O(n2)

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

最外层的 for 循环每经过一轮,剩余数字中的最大值就会被移动到当前轮次的最后一位,中途也会有一些相邻的数字经过交换变得有序。总共比较次数是 (n-1)+(n-2)+(n-3)+…+1(n−1)+(n−2)+(n−3)+…+1。

第二种写法是在基础算法的基础上改良而来的:

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len - 1; i++) {
        let isSwap = false
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                isSwap = true
            }
        }
        if (!isSwap) {
            break;
        }
    }
    return arr;
};

空间复杂度为O(1);时间复杂度为 O(n2)-最好为O(n);

最外层的 for 循环每经过一轮,剩余数字中的最大值仍然是被移动到当前轮次的最后一位。这种写法相对于第一种写法的优点是:如果一轮比较中没有发生过交换,则立即停止排序,因为此时剩余数字一定已经有序了。

选择排序

选择排序的思想是:双重循环遍历数组,每经过一轮比较,找到最小元素的下标,将其交换至首位。

基础算法

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

二元选择排序-优化

选择排序算法也是可以优化的,既然每轮遍历时找出了最小值,何不把最大值也顺便找出来呢?这就是二元选择排序的思想。

使用二元选择排序,每轮选择时记录最小值和最大值,可以把数组需要遍历的范围缩小一倍。

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len / 2; i++) {
        let minIndex = i;
        let maxIndex = i;
        for (let j = i + 1; j < len-i; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
            if (arr[maxIndex] < arr[j]) {
                maxIndex = j;
            }
        }
        if (minIndex === maxIndex) break;
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        if (maxIndex === i) {
            maxIndex = minIndex;
        }
        const lastIndex = len - i - 1;
        [arr[maxIndex], arr[lastIndex]] = [arr[lastIndex], arr[maxIndex]];
    }
    return arr; 
};

插入排序

插入排序的思想非常简单,生活中有一个很常见的场景:在打扑克牌时,我们一边抓牌一边给扑克牌排序,每次摸一张牌,就将它插入手上已有的牌中合适的位置,逐渐完成整个排序。

插入排序有两种写法:

交换法插入排序

const sort = (arr) => {
    for (let i = 1, len = arr.length; i < len; i++) {
        let j = i;
        while (j >= 1 && arr[j] < arr[j - 1]) {
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            j--
        }
    }
    return arr;
};

当数字少于两个时,不存在排序问题,当然也不需要插入,所以我们直接从第二个数字开始往前插入。

移动法

我们发现,在交换法插入排序中,每次都要交换数字。但实际上,新插入的这个数字并不一定适合与它交换的数字所在的位置。也就是说,它刚换到新的位置上不久,下一次比较后,如果又需要交换,它马上又会被换到前一个数字的位置。

由此,我们可以想到一种优化方案:让新插入的数字先进行比较,前面比它大的数字不断向后移动,直到找到适合这个新数字的位置后再插入。

这种方案我们需要把新插入的数字暂存起来,代码如下:

const sort = (arr) => {
    for (let i = 1, len = arr.length; i < len; i++) {
        let j = i-1;
        let cur = arr[i];
        while (j >= 0 && cur < arr[j]) {
            arr[j+1] = arr[j]
            j--;
        }
        arr[j+1] = cur
    }
    return arr;
};

希尔排序

1959 年 77 月,美国辛辛那提大学的数学系博士 Donald Shell 在 《ACM 通讯》上发表了希尔排序算法,成为首批将时间复杂度降到O(n2)以下的算法之一。虽然原始的希尔排序最坏时间复杂度仍然是O(n2),但经过优化的希尔排序可以达到O(n1.3)甚至 O(n7/6)。

希尔排序本质上是对插入排序的一种优化,它利用了插入排序的简单,又克服了插入排序每次只交换相邻两个元素的缺点。它的基本思想是:

第一遍(5 间隔排序):按照间隔 5 分割子数组,共分成五组,分别是[8, 1, 23],[3, 44],[34, 45],[6, 43],[4, 2]。对它们进行插入排序,排序后它们分别变成:[1, 8, 23],[3, 44],[34, 45],[6, 43],[2, 4],此时整个数组变成 [1, 3, 34, 6, 2, 8, 44, 45, 43, 4, 23]

第二遍(2 间隔排序):按照间隔 2 分割子数组,共分成两组,分别是[1, 34, 2, 44, 43, 23],[3, 6, 8, 45, 4]。对他们进行插入排序,排序后它们分别变成:[1, 2, 23, 34, 43, 44],[3, 4, 6, 8, 45],此时整个数组变成[1, 3, 2, 4, 23, 6, 34, 8, 43, 45, 44]。这里有一个非常重要的性质:当我们完成 2 间隔排序后,这个数组仍然是保持 5 间隔有序的。也就是说,更小间隔的排序没有把上一步的结果变坏。

第三遍(11 间隔排序,等于直接插入排序):按照间隔 1 分割子数组,分成一组,也就是整个数组。对其进行插入排序,经过前两遍排序,数组已经基本有序了,所以这一步只需经过少量交换即可完成排序。排序后数组变成[1, 2, 3, 4, 6, 8, 23, 34, 43, 44, 45],整个排序完成。

const sort = arr => {
    const len = arr.length;
    if (len < 2) {
        return arr;
    }
    let gap = Math.floor(len / 2);
    while (gap > 0) {
        for (let i = gap; i < len; i++) {
            let j = i;
            let cur = arr[i];
            while (j >= 0 && cur < arr[j - gap]) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = cur;
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
}

堆排序

堆排序过程如下:

  1. 用数列构建出一个大顶堆,取出堆顶的数字(放到待排序数组的最后);

  2. 调整剩余的数字,构建出新的大顶堆,再次取出堆顶的数字;

  3. 循环往复,完成整个排序。

function sort(arr) {
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length)
    }
    for (let j = arr.length - 1; j > 0; j--) {
        [arr[0], arr[j]] = [arr[j], arr[0]]
        adjustHeap(arr, 0, j)
    }
}

function adjustHeap(arr, i, length) {
    let tmp = arr[i]
    for (let k = i * 2 + 1; k < length; k = k * 2 + 1) {
        if (k + 1 < length && arr[k] < arr[k + 1]) {
            k++;
        }
        if (arr[k] > tmp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
        arr[i] = tmp;
    }
}

快速排序

快速排序算法由 C. A. R. Hoare 在 1960 年提出。它的时间复杂度也是 O(nlogn),但它在时间复杂度为 O(nlogn) 级的几种排序算法中,大多数情况下效率更高,所以快速排序的应用非常广泛。再加上快速排序所采用的分治思想非常实用,使得快速排序深受面试官的青睐,所以掌握快速排序的思想尤为重要。

快速排序算法的基本思想是:

  1. 从数组中取出一个数,称之为基数(pivot)

  2. 遍历数组,将比基数大的数字放到它的右边,比基数小的数字放到它的左边。遍历完成后,数组被分成了左右两个区域

  3. 将左右两个区域视为两个数组,重复前两个步骤,直到排序完成

  4. 事实上,快速排序的每一次遍历,都将基数摆到了最终位置上。第一轮遍历排好 1 个基数,第二轮遍历排好 2 个基数(每个区域一个基数,但如果某个区域为空,则此轮只能排好一个基数),第三轮遍历排好 4 个基数(同理,最差的情况下,只能排好一个基数),以此类推。总遍历次数为 logn~n 次,每轮遍历的时间复杂度为 O(n),所以很容易分析出快速排序的时间复杂度为 O(nlogn) ~O(n2),平均时间复杂度为 O(nlogn)。

const partition = (arr, start, end) => {
    let pivot = arr[start]; // 取第一个数为基数
    let left = start + 1; // 从第二个数开始分区
    let right = end; // 右边界
    // left、right 相遇时退出循环
    while (left < right) {
        // 找到第一个大于基数的位置
        while (left < right && arr[left] <= pivot) left++;
        // 交换这两个数,使得左边分区都小于或等于基数,右边分区大于或等于基数
        if (left != right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            right--;
        }
    }
    // 如果 left 和 right 相等,单独比较 arr[right] 和 pivot
    if (left == right && arr[right] > pivot) right--;
    // 将基数和中间数交换
    if (right != start) [arr[left], pivot] = [pivot, arr[left]];
    // 返回中间值的下标
    return right;
}

const quickSort = (arr, start, end) => {
    if (start >= end) return;
    const middle = partition(arr, start, end)
    quickSort(arr, start, middle - 1);
    quickSort(arr, middle + 1, end);
}

const sort = arr => {
    quickSort(arr, 0, arr.length -1);
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

算法描述

const merge = (left, right) => {
    let result = [];
    while (left.length > 0 && right.length > 0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length) result.push(left.shift());
    while (right.length) result.push(right.shift());
    return result;
}

const sort = (arr) => {
    let len = arr.length;
    if (len < 2) {
        return arr;
    }
    const middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(sort(left), sort(right));
};

“怎么用JavaScript实现七种排序算法”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

推荐阅读:
  1. javascript中的排序算法介绍
  2. JavaScript实现的九种排序算法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

javascript

上一篇:javascript通配符指的是什么

下一篇:JavaScript中的Object有什么作用

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》