前言

　　文本来总结常见的排序算法，通过 JvavScript 来实现

正文

　　1、冒泡排序

　　算法思想：比较相邻两个元素的大小，如果第一个比第二个大，就交换它们。从头遍历到尾部，当一轮遍历完后，数组最后一个元素是最大的。除去最后一个元素，对剩下的元素重复执行上面的流程，每次找出剩余元素中最大的，遍历完后，数组是升序的

　　算法分析：总共需要进行length * (length - 1) / 2 次比较，所以时间复杂度为O(n^2)，因为只需要有一个存放常量的空间，元素本身在原数组上进行交换，所以空间复杂度为O(1)

        function bubbleSort(array) {

            if (!Array.isArray(array)) {

                throw new Error('参数必须为数组');

                return;

            }

            var n = 0, m = 0 // n表示趟数,m表示比较次数

            for (let i = array.length - 1; i > 0; i--) { // 外层for表示遍历的趟数

                for (let j = 0; j < i; j++) { // 内层for表示每趟需要比较的 j 和 j+1 对应的数

                    if (arr[j] > arr[j + 1]) {

                        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]

                    }

                    m++

                }

                n++

            }

            console.log("遍历趟数" + n, "比较次数" + m);//遍历趟数8 比较次数36

            return array

        }

        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]

        console.log(bubbleSort(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]

　　我们在每一轮循环中，可以记住最后一次交换的元素，这之后的元素就肯定是已经排完序的，这样可以减少总的循环次数

        function bubbleSort2(array) {

            if (!Array.isArray(array)) {

                throw new Error('参数必须为数组');

                return;

            }

            var n = 0, m = 0 // n表示趟数,m表示比较次数

            for (var i = array.length - 1; i > 0;) { // 用来表示遍历 n-1 趟

                var cursor = 0;  // 用来记录本轮最后一次交换的元素位置

                for (var j = 0; j < i; j++) {

                    if (array[j] > array[j + 1]) {

                        cursor = j;

                        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]

                    }

                    m++

                }

                n++

                i = cursor;

            }

            console.log("遍历趟数" + n, "比较次数" + m);//遍历趟数6 比较次数29

            return array

        }

        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]

        console.log(bubbleSort2(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]

　　2、选择排序

　　实现思路

（1）从头遍历到尾部，找出所有项中最大的一个元素

（2）将这个元素和第一个元素交换

（3）对剩下的元素重复进行上面的操作，每次找出剩余中最大的最后的数组是降序排列的

（4）算法分析

　　总共需要进行length * (length - 1) / 2 次比较，所以时间复杂度为O(n^2)，因为只需要有两个存放常量的空间，元素本身在原数组上进行交换，所以空间复杂度为O(1)

        function selectSort(array) {

            if (!Array.isArray(array)) {

                throw new Error('参数必须为数组');

                return;

            }

            for (let i = 0; i < array.length; i++) {

                var maxIndex = i, maxValue = array[i] // 设置i为最大元素下标

                // 找出剩下元素中的最大值,第一次循环找出最大值

                for (let j = i + 1; j < array.length; j++) {

                    if (array[j] > maxValue) {

                        maxIndex = j

                        maxValue = array[j]

                    }

                }

                // 如果剩下的元素中最大值下标大于i则发生交换

                if (maxIndex > i) {

                    [array[i], array[maxIndex]] = [array[maxIndex], array[i]]

                }

            }

            return array

        }

        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]

        console.log(selectSort(arr)); //[45, 24, 9, 8, 7, 6, 3, 1, 0]

　　3、插入排序

　　实现思路

　　（1）将数组前面部分看做有序数组

　　（2）每次将后面部分的第一个与已排序数组作比较，插入到合适的位置

　　（3）有序数组初始状态有1个数字

　　（4）算法分析

　　（5）时间复杂度为O(n^2)

        function insertSort(array) {

            if (!Array.isArray(array)) {

                throw new Error('参数必须为数组');

                return;

            }

            for (var i = 1; i < array.length; i++) {

                var temp = array[i] //当前值

                for (var j = i; j > 0 && temp < array[j - 1]; j--) {

                    // 当前值和之前的每个值进行比较，发现有比当前值小的值就进行重新赋值

                    array[j] = array[j - 1];

                }

                array[j] = temp;

            }

            return array;

        }

        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]

        console.log(insertSort(arr)); //[45, 24, 9, 8, 7, 6, 3, 1, 0]

　　4、快速排序：

　　算法思想：将数组的第一个数字作为基准，最后使得基准数字位于数组中间某个位置，它的左边的数字都比它小，它的右边的数字都比它大。

　　算法实现：设置两个分别指向数组头部和尾部的指针i和j，首先向左移动j，使得array[j] 小于基准。然后向右移动i，使得array[i] 大于基准，交换这两个元素。当i 和j 的值相等时，交换基准与位置i上的元素，然后对i左边以及右边的元素分别进行快速排序。

        function quickSort(array) {

            const sort = function (arr, left = 0, right = arr.length - 1) {

                if (left >= right) {// 递归退出条件

                    return

                }

                let i = left, j = right // 定义两个指针

                let pivot = arr[i] // 定义基准数据

                while (i < j) { // 把所有比基准数

                    while (j > i && arr[j] >= pivot) { //找到一个比基准值小的数位置为j

                        j--

                    }

                    arr[i] = arr[j] // 将j的值给了i位置的元素，此时j位置还是原来的数

                    while (i < j && arr[i] < pivot) {

                        i++

                    }

                    arr[j] = arr[i] // 将i位置的值给了j位置的元素，此时i的位置还是原来的数

                }

                // 本次交换完毕，此时ij两个指针重合,把基准值赋值给i即可

                arr[i] = pivot

                sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作

                sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作

            }

            const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组

            sort(newArr)

            return newArr

        }

        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]

        console.log(quickSort(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]

写在最后

　　以上就是本文的全部内容，希望给读者带来些许的帮助和进步，方便的话点个关注，小白的成长之路会持续更新一些工作中常见的问题和技术点。

巴特西

js--js实现基础排序算法

前言

正文

1、冒泡排序

2、选择排序

3、插入排序

4、快速排序：

写在最后

最新文章

热门文章