JavaScript實現(xiàn)基礎(chǔ)排序算法的示例詳解

更新時間：2022年06月30日 14:26:35 作者：Serendipity

這篇文章主要為大家詳細(xì)介紹了如何利用JavaScript實現(xiàn)基礎(chǔ)排序算法，如：冒泡排序、選擇排序、插入排序和快速排序，感興趣的可以了解一下

前言

文本來總結(jié)常見的排序算法，通過 JvavScript 來實現(xiàn)

正文

1、冒泡排序

算法思想：比較相鄰兩個元素的大小，如果第一個比第二個大，就交換它們。從頭遍歷到尾部，當(dāng)一輪遍歷完后，數(shù)組最后一個元素是最大的。除去最后一個元素，對剩下的元素重復(fù)執(zhí)行上面的流程，每次找出剩余元素中最大的，遍歷完后，數(shù)組是升序的

算法分析：總共需要進(jìn)行l(wèi)ength * (length - 1) / 2 次比較，所以時間復(fù)雜度為O(n^2)，因為只需要有一個存放常量的空間，元素本身在原數(shù)組上進(jìn)行交換，所以空間復(fù)雜度為O(1)

function bubbleSort(array) {
            if (!Array.isArray(array)) {
                throw new Error('參數(shù)必須為數(shù)組');
                return;
            }
            var n = 0, m = 0 // n表示趟數(shù),m表示比較次數(shù)
            for (let i = array.length - 1; i > 0; i--) { // 外層for表示遍歷的趟數(shù)
                for (let j = 0; j < i; j++) { // 內(nèi)層for表示每趟需要比較的 j 和 j+1 對應(yīng)的數(shù)
                    if (arr[j] > arr[j + 1]) {
                        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
                    }
                    m++
                }
                n++
            }
            console.log("遍歷趟數(shù)" + n, "比較次數(shù)" + m);//遍歷趟數(shù)8 比較次數(shù)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]

我們在每一輪循環(huán)中，可以記住最后一次交換的元素，這之后的元素就肯定是已經(jīng)排完序的，這樣可以減少總的循環(huán)次數(shù)

function bubbleSort2(array) {
            if (!Array.isArray(array)) {
                throw new Error('參數(shù)必須為數(shù)組');
                return;
            }
            var n = 0, m = 0 // n表示趟數(shù),m表示比較次數(shù)
            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("遍歷趟數(shù)" + n, "比較次數(shù)" + m);//遍歷趟數(shù)6 比較次數(shù)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、選擇排序

實現(xiàn)思路

（1）從頭遍歷到尾部，找出所有項中最大的一個元素

（2）將這個元素和第一個元素交換

（3）對剩下的元素重復(fù)進(jìn)行上面的操作，每次找出剩余中最大的最后的數(shù)組是降序排列的

（4）算法分析

總共需要進(jìn)行l(wèi)ength * (length - 1) / 2 次比較，所以時間復(fù)雜度為O(n^2)，因為只需要有兩個存放常量的空間，元素本身在原數(shù)組上進(jìn)行交換，所以空間復(fù)雜度為O(1)

function selectSort(array) {
            if (!Array.isArray(array)) {
                throw new Error('參數(shù)必須為數(shù)組');
                return;
            }
            for (let i = 0; i < array.length; i++) {
                var maxIndex = i, maxValue = array[i] // 設(shè)置i為最大元素下標(biāo)
                // 找出剩下元素中的最大值,第一次循環(huán)找出最大值
                for (let j = i + 1; j < array.length; j++) {
                    if (array[j] > maxValue) {
                        maxIndex = j
                        maxValue = array[j]
                    }
                }
                // 如果剩下的元素中最大值下標(biāo)大于i則發(fā)生交換
                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、插入排序

實現(xiàn)思路

（1）將數(shù)組前面部分看做有序數(shù)組

（2）每次將后面部分的第一個與已排序數(shù)組作比較，插入到合適的位置

（3）有序數(shù)組初始狀態(tài)有1個數(shù)字

（4）算法分析

（5）時間復(fù)雜度為O(n^2)

function insertSort(array) {
            if (!Array.isArray(array)) {
                throw new Error('參數(shù)必須為數(shù)組');
                return;
            }
            for (var i = 1; i < array.length; i++) {
                var temp = array[i] //當(dāng)前值
                for (var j = i; j > 0 && temp < array[j - 1]; j--) {
                    // 當(dāng)前值和之前的每個值進(jìn)行比較，發(fā)現(xiàn)有比當(dāng)前值小的值就進(jìn)行重新賦值
                    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、快速排序

算法思想：將數(shù)組的第一個數(shù)字作為基準(zhǔn)，最后使得基準(zhǔn)數(shù)字位于數(shù)組中間某個位置，它的左邊的數(shù)字都比它小，它的右邊的數(shù)字都比它大。

算法實現(xiàn)：設(shè)置兩個分別指向數(shù)組頭部和尾部的指針i和j，首先向左移動j，使得array[j] 小于基準(zhǔn)。然后向右移動i，使得array[i] 大于基準(zhǔn)，交換這兩個元素。當(dāng)i 和j 的值相等時，交換基準(zhǔn)與位置i上的元素，然后對i左邊以及右邊的元素分別進(jìn)行快速排序。

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] // 定義基準(zhǔn)數(shù)據(jù)

                while (i < j) { // 把所有比基準(zhǔn)數(shù)
                    while (j > i && arr[j] >= pivot) { //找到一個比基準(zhǔn)值小的數(shù)位置為j
                        j--
                    }
                    arr[i] = arr[j] // 將j的值給了i位置的元素，此時j位置還是原來的數(shù)
                    while (i < j && arr[i] < pivot) {
                        i++
                    }
                    arr[j] = arr[i] // 將i位置的值給了j位置的元素，此時i的位置還是原來的數(shù)
                }
                // 本次交換完畢，此時ij兩個指針重合,把基準(zhǔn)值賦值給i即可
                arr[i] = pivot
                sort(arr, left, j - 1) // 將左邊的無序數(shù)組重復(fù)上面的操作
                sort(arr, j + 1, right) // 將右邊的無序數(shù)組重復(fù)上面的操作
            }
            const newArr = array.concat() // 為了保證這個函數(shù)是純函數(shù)拷貝一次數(shù)組
            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]

到此這篇關(guān)于JavaScript實現(xiàn)基礎(chǔ)排序算法的示例詳解的文章就介紹到這了,更多相關(guān)JavaScript排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: