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

資訊專欄INFORMATION COLUMN

冒泡、選擇與快速排序（js）

codeKK / 1297人閱讀

摘要：冒泡排序冒泡排序算法的運(yùn)作如下比較相鄰的元素。交換次數(shù)比冒泡排序少多了快速排序快速排序算法的運(yùn)作如下找一個(gè)數(shù)，對數(shù)組進(jìn)行掃描，小于這個(gè)數(shù)的放在這個(gè)數(shù)的左側(cè)，大于它的放在數(shù)組右側(cè)在對左右兩側(cè)的數(shù)組分別進(jìn)行剛才的操作，直到數(shù)組長度為時(shí)結(jié)束。

1.冒泡排序 1.1 冒泡排序算法的運(yùn)作如下： 
1.比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3.針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4.持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
1.2 javaScript中的實(shí)現(xiàn) 
    var arr = [9,8,7,6,5,4,3,2,1,0];
    
    //交換arr[i]和arr[j]
    function swap(arr,i,j){
        var temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //冒泡排序
    function bubbleSort(arr){
        var leap = 0;
        if(arr.length==0)
            return;
        for(var i = 0 ; i < arr.length ; i++){
            leap = 0;
            for(var j = 1 ; j < arr.length ; j++){
                if(arr[j-1] > arr[j]){
                    swap(arr,j-1,j);
                    leap = 1;
                }
            }
            //如果沒有交換，即排序正確，提前結(jié)束
            if(leap == 0){
                return;
            }
        }
        return arr;
    }

    console.log(bubbleSort(arr));  // arr = [0,1,2,3,4,5,6,7,8,9]

冒泡排序總的平均時(shí)間復(fù)雜度為Q(n^2)。

2.選擇排序 2.1 選擇排序算法的思想： 
循環(huán)arr.length次，從i=0開始，第i次循環(huán)將比較得到的最?。ɑ蜃畲螅┑臄?shù)與a[i]交換位置，即每次循環(huán)拿出最值放到其應(yīng)該在的位置，并且將其踢出下次循環(huán)。
2.2 javaScript中的實(shí)現(xiàn) 
//選擇排序
    function selectionSort(arr){
        var min;
        if(arr.length <= 1)
            return;

        for(var i = 0 ; i < arr.length-1 ; i++){
            min=i;
            for(var j = i+1 ; j < arr.length ; j++)
            {       
                if(arr[j] < arr[min]){
                    min = j;
                }
            }

            swap(arr,i,min);

        }
        return arr;
    }

     console.log(selectionSort(arr));  // arr = [0,1,2,3,4,5,6,7,8,9]

比較次數(shù)O(n^2），比較次數(shù)與關(guān)鍵字的初始狀態(tài)無關(guān)，總的比較次數(shù)N=(n-1）+(n-2）+...+1=n*(n-1）/2。交換次數(shù)O(n），最好情況是，已經(jīng)有序，交換0次；最壞情況交換n-1次，逆序交換n/2次。交換次數(shù)比冒泡排序少多了

3.快速排序 3.1 快速排序算法的運(yùn)作如下： 
1.找一個(gè)數(shù)，對數(shù)組進(jìn)行掃描，小于這個(gè)數(shù)的放在這個(gè)數(shù)的左側(cè)，大于它的放在數(shù)組右側(cè)
2.在對左右兩側(cè)的數(shù)組分別進(jìn)行剛才的操作，直到數(shù)組長度為1時(shí)結(jié)束。
3.2 javaScript中的實(shí)現(xiàn) 
    //快速排序
    function fastSort(arr,begin,end){  
        //當(dāng)end <= begin時(shí)結(jié)束遞歸
        if(end <= begin){
            return ;  
        } 

        var t = begin;
        var i = begin+1;
        var j = end;  
        var v = arr[begin]; 

        while (i <= j){  
            //通過選定的軸和其后一個(gè)值進(jìn)行比較，如后一個(gè)值比他小則交換并且兩個(gè)同時(shí)加一并且再比較，如比他大則a[i]和a[j]進(jìn)行交換并且再比較a[begin]和a[i]的值
            if  (arr[i] <= v){  
                swap(arr, t++, i++); 
           
            }else if(arr[i] > v){  
                swap(arr, i, j--);  
            
            }
           
        }
        fastSort(arr, begin, t-1);  
        fastSort(arr, j+1, end);  
    }  
   
    fastSort(arr,0,arr.length-1);
    console.log(arr);  //arr = [0,1,2,3,4,5,6,7,8,9]

此快速排序是優(yōu)化過的，能否再優(yōu)化以后再試試看。

以上代碼有部分是借鑒的,如有不足請指教^_^

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

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

相關(guān)文章

  • js實(shí)現(xiàn)冒泡排序,快速排序,選擇排序

    摘要：用冒泡排序快速排序選擇排序冒泡排序冒泡排序是比較經(jīng)典的排序方法，是一種用時(shí)間換空間的排序方法。找到并交換的時(shí)候，指針位置不變。選擇排序沒趟都會(huì)產(chǎn)生最小值，它不是相鄰元素的比較而是在該元素設(shè)置一個(gè)索引。選擇排序循環(huán)找到從開始到最后的最小的數(shù) 用js冒泡排序,快速排序,選擇排序 1.冒泡排序 冒泡排序是比較經(jīng)典的排序方法，是一種用時(shí)間換空間的排序方法。我總結(jié)了一下它的特點(diǎn)：（1）它的時(shí)間復(fù)...

    bbbbbb 評論0 收藏0

  • JS數(shù)據(jù)結(jié)構(gòu)與算法_排序和搜索算法

    摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法樹寫在前面這是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的最后一篇博客，也是在面試中常常會(huì)被問到的一部分內(nèi)容排序和搜索。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_樹 寫在前面 這是《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》的最后一篇博客，也是在面試中常常會(huì)被問到的一部分內(nèi)容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...

    姘擱『 評論0 收藏0

  • 溫故js系列（2）-快速排序&插入排序&選擇排序&冒泡排序算法&優(yōu)化

    摘要：優(yōu)化當(dāng)待排序序列長度時(shí)，使用插入排序，可以加速排序。插入排序原理通過構(gòu)建有序序列，對于未排序元素，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。 前端學(xué)習(xí)：教程&開發(fā)模塊化/規(guī)范化/工程化/優(yōu)化&工具/調(diào)試&值得關(guān)注的博客/Git&面試-前端資源匯總 歡迎提issues斧正：排序算法 JavaScript-排序算法及簡易優(yōu)化 快速...

    ningwang 評論0 收藏0

  • JS中可能用得到的全部的排序算法

    本篇有7k+字, 系統(tǒng)梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復(fù)雜的排序?qū)崿F(xiàn)，如果喜歡請點(diǎn)贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導(dǎo)讀 排序算法可以稱得上是我的盲點(diǎn), 曾幾何時(shí)當(dāng)我知道Chrome的Array.prototype.sort使用了快速排序時(shí), 我的內(nèi)心是奔潰的(啥是快排, 我只知道...

    verano 評論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 冒泡排序、插入排序、選擇排序

    摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，...

    canger 評論0 收藏0

發(fā)表評論

0條評論

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