亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

wh469012917 / 787人閱讀

摘要：介紹排序算法是算法中最常見(jiàn)的算法之一，我這里要介紹的是排序算法中的三種基本算法冒泡排序選擇排序插入排序，在文章的后面我會(huì)對(duì)三種算法的速度進(jìn)行對(duì)比。

1.介紹

排序算法是算法中最常見(jiàn)的算法之一，我這里要介紹的是排序算法中的三種基本算法：冒泡排序、選擇排序、插入排序，在文章的后面我會(huì)對(duì)三種算法的速度進(jìn)行對(duì)比。

2.冒泡排序

冒泡排序其名來(lái)源與其算法實(shí)現(xiàn)，會(huì)使得數(shù)組中的元素一個(gè)個(gè)從數(shù)組一端漂到另一端而故這樣命名。下面我們實(shí)現(xiàn)的是對(duì)數(shù)組就行升序排列的冒泡：

function bubbleSort(arr){
    if(!arr instanceof Array){
        return;
    }
    if(arr.length == 0 || arr.length == 1){
        return arr;
    }
    for(let outer = arr.length; outer >= 2; outer--){
        for(let inner = 0; inner <= outer - 1; inner++){
            if(arr[inner] > arr[inner + 1]){
                let temp = arr[inner];
                arr[inner] = arr[inner + 1];
                arr[inner + 1] = temp;    
            }
        }
    }
    return arr;
}
3.選擇排序

選擇排序我們也需要用到嵌套循環(huán)，算法思路如下：
從數(shù)組的第一個(gè)元素開(kāi)始，將第一個(gè)元素逐個(gè)與其他元素比較，檢查完所有元素后，最小的元素會(huì)放到最前面。然后從第二個(gè)元素繼續(xù)，重復(fù)這一過(guò)程，直到進(jìn)行到數(shù)組倒數(shù)第二個(gè)元素，排序并完成了。

外循環(huán)從數(shù)組的第一個(gè)元素移動(dòng)到倒數(shù)第二個(gè)元素； 內(nèi)循環(huán)從第二個(gè)數(shù)組元素移動(dòng)到最后一個(gè)元素， 查找比當(dāng)前外循環(huán)所指向的元素小的元素。 每次內(nèi)循環(huán)迭代后， 數(shù)組中最小的值都會(huì)被賦值到合適的位置。

function selectionSort(arr){
    if(!arr instanceof Array){
        return;
    }
    if(arr.length == 0 || arr.length == 1){
        return arr;
    }
    let min;
    for(let outer = 0; outer <= arr.length - 2; outer++){
        min = outer;
        for(let inner = outer + 1; inner <= arr.length - 1; inner++){
            if(arr[inner] < arr[min]){
                min = inner;
            }
        }
         let temp = arr[outer];
         arr[outer] = arr[min];
         arr[min] = temp;
    }
    return arr;
}
4.插入排序

插入排序有兩個(gè)循環(huán)。 外循環(huán)將數(shù)組元素挨個(gè)移動(dòng)， 而內(nèi)循環(huán)則對(duì)外循環(huán)中選中的元素及它后面的那個(gè)元素進(jìn)行比較。 如果外循環(huán)中選中的元素比內(nèi)循環(huán)中選中的元素小， 那么數(shù)組元素會(huì)向右移動(dòng)， 為內(nèi)循環(huán)中的這個(gè)元素騰出位置。

function insertionSort(arr){
    if(!arr instanceof Array){
        return;
    }
    if(arr.length == 0 || arr.length == 1){
        return arr;
    }
    let temp,inner;
    for(let outer = 0; outer < arr.length; outer++){
        temp = arr[outer];
        inner = outer;
        while(inner > 0 && (arr[inner - 1] >= temp)){
            arr[inner] = arr[inner - 1];
            --inner;
        }
        arr[inner] = temp;
    }
    return arr; 
}
5.三種排序算法速度的比較

首先我們實(shí)現(xiàn)一個(gè)生成隨機(jī)數(shù)組的函數(shù)：

function createArr(n){
    let arr = [];
    if(typeof n !== "number"){
        return;
    }
    if(n === 0){
        return arr;
    }
    for(let i = 0; i < n ; i++){
        arr[i] = Math.floor(Math.random() * (n + 1));
    }
    return arr;
}

我們通過(guò)獲取當(dāng)前的時(shí)間戳和運(yùn)行算法后時(shí)間戳進(jìn)行對(duì)比來(lái)比較，主要比較數(shù)組的大小為100， 1000， 10000時(shí)來(lái)觀察三種算法。

//數(shù)組為100的情況
let arr = createArr(100);
let start = Date.now();
bubbleSort(arr);
let stop = Date.now();
cosnole.log(`冒泡排序用時(shí)${stop - start}`);
    start = Date.now();
selectionSort(arr);
    stop = Date.now();
cosnole.log(`選擇排序用時(shí)${stop - start}`);    
    start = Date.now();
insertionSort(arr);
    stop = Date.now();
cosnole.log(`插入排序用時(shí)${stop - start}`);

最后得出的結(jié)果為

說(shuō)明數(shù)組大小為100時(shí)，三種排序算法速度之間沒(méi)有什么太大的差別。
我把數(shù)組擴(kuò)大為1000得到的結(jié)果如下：

現(xiàn)在我們可以看到選擇排序和插入排序比冒泡排序都快了很多。
接著我把數(shù)據(jù)增大為10000，得到的結(jié)果為：

現(xiàn)在我們可以很明顯的看出三種排序算法的速度誰(shuí)快誰(shuí)慢了，特別是我們處理比較大的數(shù)據(jù)時(shí)，對(duì)算法的選擇影響到程序的性能。

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/85212.html

相關(guān)文章

  • 基本排序算法

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

    wupengyu 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法——希爾、歸并、快速排序

    摘要：今天再來(lái)看看另外三種時(shí)間復(fù)雜度都是的排序算法，分別是希爾排序歸并排序和快速排序。三數(shù)取中法求將放到數(shù)組的末尾總結(jié)這三種排序算法的平均時(shí)間復(fù)雜度都是，歸并排序和快速排序的應(yīng)用更廣泛。 1. 回顧 前面說(shuō)完了三種較為簡(jiǎn)單的排序算法，分別是冒泡排序，選擇排序和插入排序，它們的平均情況時(shí)間復(fù)雜度都是 O(n2)，比較的高，適合小規(guī)模的數(shù)據(jù)排序，其中插入排序的效率稍高，所以更推薦使用插入排序。今...

    hersion 評(píng)論0 收藏0

  • js數(shù)值排序中冒泡算法的4種簡(jiǎn)單實(shí)現(xiàn)

    摘要：實(shí)現(xiàn)數(shù)組排序的算法很多其中冒泡算法是比較簡(jiǎn)單的冒泡的基本原理是相鄰的兩個(gè)數(shù)進(jìn)行比較按照排序的條件進(jìn)行互換例如對(duì)數(shù)值從小到大排序隨著不斷的互換最大的那個(gè)值會(huì)慢慢冒泡到數(shù)組的末端基于這個(gè)原理我們就可以寫(xiě)冒泡排序了為了簡(jiǎn)單起見(jiàn)下面的例子都是對(duì)數(shù)值 實(shí)現(xiàn)數(shù)組排序的算法很多,其中冒泡算法是比較簡(jiǎn)單的冒泡的基本原理是相鄰的兩個(gè)數(shù)進(jìn)行比較,按照排序的條件進(jìn)行互換,例如對(duì)數(shù)值從小到大排序,隨著不斷的互...

    wean 評(píng)論0 收藏0

  • js數(shù)值排序中冒泡算法的4種簡(jiǎn)單實(shí)現(xiàn)

    摘要：實(shí)現(xiàn)數(shù)組排序的算法很多其中冒泡算法是比較簡(jiǎn)單的冒泡的基本原理是相鄰的兩個(gè)數(shù)進(jìn)行比較按照排序的條件進(jìn)行互換例如對(duì)數(shù)值從小到大排序隨著不斷的互換最大的那個(gè)值會(huì)慢慢冒泡到數(shù)組的末端基于這個(gè)原理我們就可以寫(xiě)冒泡排序了為了簡(jiǎn)單起見(jiàn)下面的例子都是對(duì)數(shù)值 實(shí)現(xiàn)數(shù)組排序的算法很多,其中冒泡算法是比較簡(jiǎn)單的冒泡的基本原理是相鄰的兩個(gè)數(shù)進(jìn)行比較,按照排序的條件進(jìn)行互換,例如對(duì)數(shù)值從小到大排序,隨著不斷的互...

    zacklee 評(píng)論0 收藏0

  • js數(shù)值排序中冒泡算法的4種簡(jiǎn)單實(shí)現(xiàn)

    摘要：實(shí)現(xiàn)數(shù)組排序的算法很多其中冒泡算法是比較簡(jiǎn)單的冒泡的基本原理是相鄰的兩個(gè)數(shù)進(jìn)行比較按照排序的條件進(jìn)行互換例如對(duì)數(shù)值從小到大排序隨著不斷的互換最大的那個(gè)值會(huì)慢慢冒泡到數(shù)組的末端基于這個(gè)原理我們就可以寫(xiě)冒泡排序了為了簡(jiǎn)單起見(jiàn)下面的例子都是對(duì)數(shù)值 實(shí)現(xiàn)數(shù)組排序的算法很多,其中冒泡算法是比較簡(jiǎn)單的冒泡的基本原理是相鄰的兩個(gè)數(shù)進(jìn)行比較,按照排序的條件進(jìn)行互換,例如對(duì)數(shù)值從小到大排序,隨著不斷的互...

    zzzmh 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

wh469012917

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<