国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JavaScript實現的幾種排序

piapia / 2874人閱讀

摘要:冒泡排序原理冒泡排序的過程就是將數組中相鄰的兩個元素進行比較,如果前面的元素比后面的元素要大交換位置,否則位置不變舉個栗子有數組第一輪循環和比較,小于兩者位置不變,接下來和比較,大于,兩者交換位置,接著和比較,兩者交換位置,繼續和比較兩者交

1.冒泡排序

原理:冒泡排序的過程就是將數組中相鄰的兩個元素進行比較,如果前面的元素比后面的元素要大交換位置,否則位置不變;舉個栗子:有數組 arr = [3,5,4,2,1];
第一輪循環:3和5比較,3小于5兩者位置不變,接下來5和4比較,5大于4,兩者交換位置,接著5和2比較,5>2兩者交換位置,繼續5和1 比較 5>1兩者交換位置,一輪后得到的數組是[3,4,2,1,5];把大的元素放到數組的最末尾,這種就像水泡樣一層一層的像后移動,就是冒泡排序了;
代碼實現:

    // 記錄循環次數
    let count = 0 
   // 位置交換函數
    const change = function (arr, n1, n2) {
         // 用es6的實現交換
         [arr[n1], arr[n2]] = [arr[n2], arr[n1]]
        //let temp = arr[n1]
        //arr[n1] = arr[n2]
        //arr[n2] = temp
    }
    // 冒泡排序
    const bubbleSort = function (soucre) {
        let len = soucre.length
        for (let i = 0;i < len - 1; i++) {
            for (let j = 0; j < len - 1 - i;j++) {
                count ++
                if (soucre[j] > soucre[j+1]) {
                   change(soucre, j, j+1)
                }
            }
        }
        return soucre
    }
    //驗證
    console.log(bubbleSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9]
    console.log(count) // 21
2.選擇排序

選擇排序和冒泡排序類似也是依次對相鄰的數進行兩兩比較。不同之處在于,他不是每次兩兩相鄰比較后交換位置,他是先找出最大(最小)將它放到正確的位置,然后再尋找次最大(最小)放在正確的位置;
舉個栗子:有數組 arr = [3,5,4,2,1];
先假設第一個元素是最小值,并定義一個minidx=0變量記錄最小(最大)值的位置,for循環和其他元素進行比較,3和5進行比較,5>3此時不做處理,4也是一樣處理,當3和2比較時,3>2,此時將minidx賦值為2的位置,接下來用arr[minidx]和剩余的元素比較遇到比他小的就用minidx記錄小值的位置;最后將最小的位置值和初始給的值位置進行互換(當然是初始的值和一輪循環下來的minidx位置不一樣才互換);所以一輪循環下來結果是arr = [1,5,4,2,3]
代碼實現:

// 記錄循環次數
let count = 0
// 選擇排序
 const selectSort = function (soucre) {
        let len = soucre.length
        let minidx;
        for (let i = 0; i < len; i ++) {
            minidx = i
            for (let j = i + 1; j < len; j++) {
                count ++
                if (soucre[minidx] > soucre[j]) {
                    minidx = j
                }
            }
            if (minidx !== i) {
                change(soucre,i,minidx)
            }
        }
        return soucre
    }
     console.log(selectSort([3,6,2,4,9,1,8,23,45,16,14])) // [1, 2, 3, 4, 6, 8, 9, 14, 16, 23, 45]
    console.log(count) // 55
3.插入排序

原理:將數組分為已排序和未排序,將第一個元素看作是已排序的元素,而其他是未排序的,從未排序的里面取出一元素和已排序元素進行比較,并插入到正確位置,這樣已排序部分增加一個元素,而未排序的部分減少一個元素。直到排序完成
舉個栗子:有數組 arr = [1,5,4,2,3],第一次假設元素1 是已排序部分,5,4,2,3為未排序,取出元素5加入已排序部分,5>1,已排序部分為1,5;而未排序部分為4,2,3;如此往復完成排序;
代碼實現:

const insertSort = function (source) {
        let len = source.length
        let value
        let j
        let i
        for (i = 0; i < len; i++) {
            value = source[i]
            // 已排序部分進行元素的右移一位,并把目標值value插入到對應的位置
            for (j = i -1 ;j > -1 && source[j] > value; j--) {
                source[j+1] = source[j]
            }
            source[j+1] = value
        }
        return source
    }
        console.log(insertSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9]
4.歸并排序

原理: 將兩個已經排序的數組合并,要比從頭開始排序所有元素來得快。因此,可以將數組拆開,分成n個只有一個元素的數組,然后不斷地兩兩合并,直到全部排序完成
代碼實現:

const mergeSort = function mergeSort(source) {
        let len = source.length
        if (len < 2) {
            return source
        }
        let mid = Math.floor(len/2)
        let left = source.slice(0,mid)
        let right = source.slice(mid)
        return merge(mergeSort(left), mergeSort(right))
    }
    function merge(left, right) {
        let result = []
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                result.push(left.shift())
            } else {
                result.push(right.shift())
            }
        }
        while (left.length){
            result.push(left.shift())
        }
        while (right.length){
            result.push(right.shift())
        }
        return result
    }
    console.log(mergeSort([4,8,1,3,5,9,6])) // [1,3,4,5,6,8,9]
5.快速排序

原理:快速排序是目前公認的速度快和高效的排序方式,時間復雜度O(nlogn)是比較理想的狀態,他的實現過程是,先在數組找到一個基點,把大于這個基點的值放到右側,小于基點的值放到左側,再將右側的和左側的也按照這種方式再次分配,直到完成排序
舉個栗子:有一個數組 arr = [1,5,4,2,3];假設我們找數組的中間點作為基點也就是4,那一輪循環后結果就是[1,2,3,4,5] ->_->怎么這么巧,一輪就OK,果然是快速排序,就是快 哈哈,當然程序不會這么做,他是嚴謹的,他還會去拆分[1,2,3]只是這個實際上已經是排好了的;
代碼實現:粗糙一點的

const quire = function quire(source) {
        if(source.length < 2) return source
        let left = []
        let right = []
        let len = source.length
        let key = source[Math.floor(len/2 -1)]
        for (let i = 0;i key){
                right.push(source[i])
            }
        }
        return [].concat(quire(left),key,quire(right))
    }

上面這種方法缺點就是空間浪費,他會創建很多個left 和 right 這樣的數組,造成空間的浪費,當數據量一大的話還是很恐怖的,所以我們要改進的就是,不新建中間數組,而是直接修改位移目標數組;

改進原理: 選取一個基點,從數組的兩頭兩個指針分別向基點位移,位移的原則是,基點的左邊的元素如果小于基點,那就像基點位置靠攏一位,i++,如果大于基點就原地不動,基點右邊的元素反過來,如果大于基點就像基點靠攏一位,j--;如果小于就原地不動;這時再比較兩個原地不動的點,如果右邊的不動點小于左邊的值,就互換他們的位置;

代碼實現:

    // 位置交換
    const change = function (arr, n1, n2) {
      //        let temp = arr[n1]
      //        arr[n1] = arr[n2]
      //        arr[n2] = temp
        // 用es6的實現交換
        [arr[n1], arr[n2]] = [arr[n2], arr[n1]]
    }
 const quiregai = function quiregai(source, start, end) {
       let pivot = source[Math.floor((start + end)/2)]
       let i = start // 左邊指針初始位置
       let j = end // 右邊指針初始位置
       while(i<=j) {
           while (source[i] < pivot) {
               i ++ // 左指針右移
           }
           while (source[j] > pivot) {
               j -- // 右指針左移
           }
           if (i <= j){
               change(source,i,j) // 交換兩個位置的值
               i++
               j--
           }
       }
       return i // 返回一輪循環后左指針的位置,為下一輪循環初始位置確定
    }
    const quiregaiSort = function quiregaiSort(source, start, end) {
        if (source.length < 2) return source
        var start = start || 0
        var end = end || source.length - 1
        var nextStart = quiregai(source, start, end)
//        debugger
        if (start < nextStart -1) {
            quiregaiSort(source, start, nextStart -1 ) // 上個循環結束的左指針作為左邊區塊循環的右指針
        }
        if (nextStart < end) {
            quiregaiSort(source, nextStart, end) // 上個循環結束的左指針作為右邊區塊循環的左指針
        }
        return source
    }
    console.log(quiregaiSort([4,1,9,3,7,5,76,21,12,53,24]))

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/95757.html

相關文章

  • 基本方法筆記 - 收藏集 - 掘金

    摘要:探討判斷橫豎屏的最佳實現前端掘金在移動端,判斷橫豎屏的場景并不少見,比如根據橫豎屏以不同的樣式來適配,抑或是提醒用戶切換為豎屏以保持良好的用戶體驗。 探討判斷橫豎屏的最佳實現 - 前端 - 掘金在移動端,判斷橫豎屏的場景并不少見,比如根據橫豎屏以不同的樣式來適配,抑或是提醒用戶切換為豎屏以保持良好的用戶體驗。 判斷橫豎屏的實現方法多種多樣,本文就此來探討下目前有哪些實現方法以及其中的優...

    maochunguang 評論0 收藏0
  • Javascript算法——快速排序

    摘要:常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。這里主要介紹快速排序。快速排序是一種既不浪費空間又可以快一點的排序算法。 常見的內部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。這里主要介紹快速排序。 一圖勝千言: showImg(https://segmentfault.com/img/bVNIpc?...

    馬忠志 評論0 收藏0
  • 2018年5月前端面試題

    摘要:在上家公司裸辭之后,經過一段時間休整,月中下旬面試了一些公司,由于本人框架使用的是,所以面試題涉及到框架的都是,現將面試題整理一下列舉常用的特性。事件冒泡以及事件捕獲。其他前端分頁和后端分頁優缺點。包含多個子節點及孫節點,遍歷。 在上家公司裸辭之后,經過一段時間休整,5月中下旬面試了一些公司,由于本人框架使用的是vue,所以面試題涉及到框架的都是vue,現將面試題整理一下: es6 ...

    wwolf 評論0 收藏0
  • 2018年5月前端面試題

    摘要:在上家公司裸辭之后,經過一段時間休整,月中下旬面試了一些公司,由于本人框架使用的是,所以面試題涉及到框架的都是,現將面試題整理一下列舉常用的特性。事件冒泡以及事件捕獲。其他前端分頁和后端分頁優缺點。包含多個子節點及孫節點,遍歷。 在上家公司裸辭之后,經過一段時間休整,5月中下旬面試了一些公司,由于本人框架使用的是vue,所以面試題涉及到框架的都是vue,現將面試題整理一下: es6 ...

    Lavender 評論0 收藏0
  • mgo做分頁幾種方法

    摘要:場景當數據兩足夠大的時候,一頁展示不完的時候,我們經常會需要分頁的功能。方案三,數據比較大,排序需要排序當數據量比較大的時候,并且需要排序的時候,可以使用這種情況。 場景 當數據兩足夠大的時候,一頁展示不完的時候,我們經常會需要分頁的功能。 方案 方案一,數據不是很大 需要排序 s := globalS.Copy() c := s.DB(db).C(collection...

    Terry_Tai 評論0 收藏0

發表評論

0條評論

piapia

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<