基本排序算法

wupengyu 發(fā)布于2019-08-23 14:10 / 3019人閱讀

摘要：基本排序算法在計(jì)算機(jī)科學(xué)中，一個排序算法是一種能將一串?dāng)?shù)據(jù)依照特定的排列方式進(jìn)行排列的一種算法。畢竟他們的效率都不太理想在實(shí)際應(yīng)用中，應(yīng)該選擇高級排序算法快速排序在隨機(jī)生成數(shù)據(jù)測試的時(shí)候，發(fā)現(xiàn)很多時(shí)候，插入排序要快于冒泡排序以及選擇排序。

基本排序算法

在計(jì)算機(jī)科學(xué)中，一個排序算法是一種能將一串?dāng)?shù)據(jù)依照特定的排列方式進(jìn)行排列的一種算法。

這里簡單的介紹三種最基本的排序，分別是：冒泡排序、選擇排序以及插入排序

排序的過程中，經(jīng)常要用到交換元素位置，故抽離為公共函數(shù) swap。

// 交換位置
export function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

冒泡排序

冒泡排序是最簡單的排序，一一對比相鄰的兩個數(shù)，順序不對就交換過來，這樣子，每一輪最大的值總會慢慢的被交換到最右側(cè)。所以才會叫冒泡排序

描述

假設(shè)數(shù)組長度為 n

比較相鄰的兩個數(shù)，如果第 1 個大于第 2 個，就交換位置

重復(fù)第 1 步，一輪下來最大值被交換到第 n 個位置，也就是最右側(cè)

開啟新一輪，重復(fù) 1~2 步，最大值會被冒泡到第 n-1 個位置

重復(fù)上述步驟，直到所有都排序好

例子：

對 3, 1, 5, 2, 4 進(jìn)行排序

1,3,5,2,4  3 > 1 ,交換位置
1,3,5,2,4  3 < 5 ,不變
1,3,2,5,4  5 > 2 ,交換位置
1,3,2,4,5  5 > 4 ,交換位置,第一輪結(jié)束
1,3,2,4,5  1 < 3 ,不變
1,2,3,4,5  3 > 2 ,交換位置
1,2,3,4,5  ...依次對比
1,2,3,4,5  ...
1,2,3,4,5  ... 結(jié)束

代碼實(shí)現(xiàn)

// 冒泡排序
export function bubbleSort(array) {
    for (let i = array.length - 1; i >= 1; i--) {
        let hasSwap = false;
        for (let j = 0; j <= i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                hasSwap = true;
            }
        }
        if (!hasSwap) {
            // 這里用于優(yōu)化，如果某一輪之后，沒有進(jìn)行任何交換，說明已經(jīng)排序完成了，所以退出循環(huán)
            break;
        }
    }
}

效果演示

https://global.chen4342024.co...

注意打開開發(fā)者工具，切換到移動端模式

小結(jié)

冒泡算法是比較慢的排序之一，也是最容易實(shí)現(xiàn)的算法之一。

復(fù)雜度

穩(wěn)定性：穩(wěn)定

時(shí)間復(fù)雜度：平均 O(n^2) 、最壞 O(n^2) 、最好 O(n)

額外空間復(fù)雜度 O(1)

選擇排序

選擇排序是指每一輪從數(shù)組中取出最小值，然后跟第一個元素交換位置。然后再找出第二個最小值，跟第二個元素交換位置，。。。以此類推。直到倒數(shù)第二個位置

例子

對 3, 1, 5, 2, 4 進(jìn)行排序

// 這里只展示每一輪的結(jié)果
3 1 5 2 4   //開始
1 3 5 2 4   //第 1 輪
1 2 5 3 4   //第 2 輪
1 2 3 5 4   //第 3 輪
1 2 3 4 5   //第 4 輪

代碼實(shí)現(xiàn)

// 選擇排序從開頭開始，找出最小的值，放在第一個位置
// 有點(diǎn)類似打撲克拍的時(shí)候，抽取每一張最小的放在最左邊
export function selectSort(array) {
    for (let i = 0; i < array.length - 1; i++) {
        let minIndex = i;
        let min = array[i];
        for (let j = i + 1; j < array.length; j++) {
            if (array[j] < min) {
                min = array[j];
                minIndex = j;
            }
        }
        swap(array, i, minIndex);
    }
}

效果演示

https://global.chen4342024.co...

注意打開開發(fā)者工具，切換到移動端模式

復(fù)雜度

穩(wěn)定性：不穩(wěn)定

時(shí)間復(fù)雜度： O(n^2)

額外空間復(fù)雜度 O(1)

插入排序

插入排序的思想是，依次從數(shù)組中未排序的部分，取出數(shù)據(jù)，然后插入到已排序的部分。直到清空未排序的部分

描述

假設(shè)數(shù)組長度為 n , 從第 2 項(xiàng)開始

從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序；

取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；

如果該元素大于新元素，將該元素移到下一位置；

重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置；

將新元素插入到該位置后；

重復(fù)步驟 2~5。

代碼實(shí)現(xiàn)

export function insertSort(array) {
    for (let i = 0; i < array.length; i++) {
        let temp = array[i];
        let j = i;
        while (j > 0 && array[j - 1] > temp) {
            // 將所有大于temp的往右移
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
}

效果演示

https://global.chen4342024.co...

注意打開開發(fā)者工具，切換到移動端模式

復(fù)雜度

穩(wěn)定性：穩(wěn)定

時(shí)間復(fù)雜度：平均 O(n^2) 、最壞 O(n^2) 、最好 O(n)

額外空間復(fù)雜度 O(1)

效果演示（匯總）

https://global.chen4342024.co...

注意打開開發(fā)者工具，切換到移動端模式

總結(jié)

這三種最基本的排序算法的復(fù)雜度非常相似，從理論上來說，它們的執(zhí)行效率也應(yīng)該差不多。

在實(shí)際使用中，如果需要排序的數(shù)據(jù)比較多，是不推薦使用這 3 種排序的。畢竟他們的效率都不太理想

在實(shí)際應(yīng)用中，應(yīng)該選擇高級排序算法：快速排序 ...

在隨機(jī)生成數(shù)據(jù)測試的時(shí)候，發(fā)現(xiàn)很多時(shí)候，插入排序要快于冒泡排序以及選擇排序。大概是冒泡/選擇排序的快 1 倍

這是因?yàn)?插入排序需要比較的次數(shù)是 1+2+3+..+n = n * (n-1) /2,這是最壞的情況，大部分時(shí)候并不需要全部比較，所以平均下來只需要 n*(n-1)/4

而冒泡/選擇排序都需要n * (n-1)/2,所以平均下來，插入排序大概是冒泡/選擇排序的快 1 倍

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/100206.html

發(fā)表評論

登陸后可評論

0條評論

wupengyu

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow

閱讀 3092·2023-04-26 00:53
騰訊云基礎(chǔ)網(wǎng)絡(luò)產(chǎn)品下線通知：2022年1月31日停止基礎(chǔ)網(wǎng)絡(luò)產(chǎn)品創(chuàng)建

閱讀 3543·2021-11-19 09:58
工作5年后我才發(fā)現(xiàn)：90%的技術(shù)問題，可以解決

閱讀 1705·2021-09-29 09:35
RangCloud：慶國慶活動,香港CN2+BGP線路VPS七折優(yōu)惠;1核/1G套餐月付13.8元起

閱讀 3293·2021-09-28 09:46
如何搭建虛擬主機(jī)-如何在虛擬主機(jī)上搭建一個網(wǎng)站？

閱讀 3873·2021-09-22 15:38
前端常用屬性/方法/命令積累

閱讀 2700·2019-08-30 15:55
基本排序算法

閱讀 3020·2019-08-23 14:10
isNaN的理解

閱讀 3834·2019-08-22 18:17

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

基本排序算法

復(fù)雜度

復(fù)雜度

復(fù)雜度

相關(guān)文章

使用JS實(shí)現(xiàn)三種基本的排序算法以及三種算法的比較