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

資訊專欄INFORMATION COLUMN

排序算法的Javascript實現(xiàn)

fredshare / 2695人閱讀

摘要：排序加了的插入排序。分別以索引數(shù)為的元素為起點，將其看做不同的組，，，為一組，，為一組依次分組，按照組為單位進(jìn)行插入排序。各組都已經(jīng)插入排序一輪過后，將除以向下取整，再進(jìn)行分組并將各組分別進(jìn)行插入排序，直到為。

1.冒泡排序：

比較相鄰的兩個數(shù)，如果前一個數(shù)大于后一個數(shù)，就將這兩個數(shù)換位置。每一次遍歷都會將本次遍歷最大的數(shù)冒泡到最后。為了將n個數(shù)排好序，需要n-1次遍歷。 如果某次遍歷中，沒有調(diào)整任何兩個相鄰的數(shù)的位置關(guān)系，說明此時數(shù)組已排好序，可以結(jié)束程序。

Array.prototype.bubbleSort = function () {
  let i, j;
  for (i = 1; i < this.length; i++) {  //表示本次是第i次遍歷
    let changed = false;
    for (j = 0; j < this.length - i; j++) {   //訪問序列為arr[0:length-i]
      if(this[j] > this[j + 1]){  //發(fā)現(xiàn)前一個數(shù)大于后一個時，互換位置
        [this[j],this[j+1]] = [this[j+1],this[j]];
        changed = true;
      }
    }
    if(!changed) {      //如果本輪遍歷沒有發(fā)現(xiàn)位置調(diào)整，結(jié)束排序函數(shù)
      break;
    }
  }
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.bubbleSort();
console.log(arr);

2.選擇排序

第i輪遍歷arr[0:n-i]選出最大的數(shù)，與arr[n-i]互換。

Array.prototype.selectSort = function () {
  let i, j;
  for (i = 1; i < this.length; i++) {     //表示本次是第i次遍歷
    let maxIndex = 0;
    for (j = 0; j <= this.length - i; j++) {  //訪問子序列為arr[0:this.length-i]
      if (this[j] > this[maxIndex]) {   //當(dāng)前值大于當(dāng)前最大值時，記錄索引
        maxIndex = j;
      }
    }
    //將子數(shù)組最大值索引的值，與子數(shù)組末尾的值互換
    [this[this.length - i], this[maxIndex]] = [this[maxIndex], this[this.length - i]]
  }
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.selectSort();
console.log(arr);

3.插入排序 數(shù)組的前面部分已經(jīng)排好序，要把當(dāng)前數(shù)字插入到前面已排好序的數(shù)組的相應(yīng)位置?？赡苡腥藭幸蓡枮槭裁茨J(rèn)數(shù)組前面部分已排好序？是怎么排好序的？是因為當(dāng)排序開始時，從第2個數(shù)字開始進(jìn)行向前插入，此時當(dāng)前數(shù)字索引為1，當(dāng)前數(shù)字前面僅有一個數(shù)字，因此可以認(rèn)為前面部分已經(jīng)排好序，將這個數(shù)字插入到相應(yīng)位置之后數(shù)組仍然是有序的。每次都將當(dāng)前數(shù)字插入到對應(yīng)的位置，因此每次插入之后前面的數(shù)組仍是排好序的。

Array.prototype.insertSort = function () {
  let i, j;
  for (i = 1; i < this.length; i++) {   //i表示當(dāng)前要向前插入的數(shù)字的索引，從1(即第2個數(shù))開始前插
    let val = this[i];   //記錄當(dāng)前要前插的數(shù)的大小
    /*
    * 用指針j來遍歷第i個數(shù)字前面的，已經(jīng)排好序的子數(shù)組。當(dāng)j沒有指到頭，并且j的數(shù)字大于要插入的數(shù)字時，說明
    * j還要向前遍歷，直到發(fā)現(xiàn)一個比要插入數(shù)字小的位置pos，然后將這個數(shù)字插到pos+1處。如果j已經(jīng)指到頭了，
    * 到了-1了還沒有找到比當(dāng)前數(shù)字小的位置，就把當(dāng)前數(shù)字放在索引0處。
    * */
    for (j = i - 1; j >= 0 && this[j] > val; j--) {  
      this[j + 1] = this[j];
    }
    this[j + 1] = val;
  }
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.insertSort();
console.log(arr);

4.shell排序 加了step的插入排序。分別以索引數(shù)為0,1,......step-1的元素為起點，將其看做不同的組，0、0+step,0+2step，......，0+nstep為一組，1,1+step,1+2step，.....,1+nstep為一組依次分組，按照組為單位進(jìn)行插入排序。各組都已經(jīng)插入排序一輪過后，將step除以2向下取整，再進(jìn)行分組并將各組分別進(jìn)行插入排序，直到step為0。 step的取值與性能直接相關(guān)，需要思考后取值。 并且這里的分組僅僅是邏輯上分組，并沒有開辟新的地址空間將其進(jìn)行物理上的分組。

const {floor} = Math;
//這個和插入排序相同，只不過加了step
Array.prototype.shellInsertSort = function (startIndex, step) {
  let i, j;
  for (i = startIndex + step; i < this.length; i += step) {
    let val = this[i];
    for (j = i - step; j >= 0 && this[j] > val; j -= step) {
      this[j + step] = this[j];
    }
    this[j + step] = val;
  }
};
Array.prototype.shellSort = function () {
  let i, step;
  for (step = floor(this.length / 2); step > 0; step = floor(step / 2)) {
    for (i = 0; i < step; i++) {
      this.shellInsertSort(i, step);
    }
  }
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.shellSort(true);
console.log(arr);

5.合并排序

舉個例子： 有 43 12 32 29 66 78 31這個數(shù)組要用合并排序。 先將相鄰兩數(shù)分為一組進(jìn)行合并 43|12 32|29 66|78 31 結(jié)果為12 43 29 32 66 78 31

再將組的大小乘以二 (12 43|29 32) (66 78|31) 本次合并后結(jié)果為 12 29 32 43 31 66 78

再將組的大小乘以二 12 43 29 32 | 66 78 31 合并結(jié)果：12 29 31 32 43 66 78

合并的過程中要開辟新的數(shù)組arr，建立兩個指針i,j分別指向arr1與arr2，此時arr1與arr2都是排好序的，然后每次都將arr1[i]與arr2[j]較小的數(shù)加到arr中并將指針后移。最后哪個數(shù)組有剩余的數(shù)在追加到arr后面。

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

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

相關(guān)文章

  • 深入淺出 JavaScript 的 Array.prototype.sort 排序算法

    摘要：快速排序是不穩(wěn)定的排序算法。瀏覽器的實現(xiàn)不同有什么影響排序算法不穩(wěn)定有什么影響舉個例子某市的機(jī)動車牌照拍賣系統(tǒng)，最終中標(biāo)的規(guī)則為按價格進(jìn)行倒排序相同價格則按照競標(biāo)順位即價格提交時間進(jìn)行正排序。 本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復(fù)雜度，看看它有多快？ 3、...

    itvincent 評論0 收藏0

  • 常用排序算法之JavaScript實現(xiàn)

    摘要：代碼實現(xiàn)六堆排序算法簡介堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。九計數(shù)排序算法簡介計數(shù)排序是一種穩(wěn)定的排序算法。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。 贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介 插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...

    jerry 評論0 收藏0

  • 優(yōu)秀程序員都應(yīng)該學(xué)習(xí)的 GitHub 上開源的數(shù)據(jù)結(jié)構(gòu)與算法項目

    摘要：強(qiáng)烈推薦上值得前端學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數(shù)據(jù)結(jié)構(gòu)，提供進(jìn)一步閱讀的解釋和鏈接。數(shù)據(jù)結(jié)構(gòu)和算法必知必會的個代碼實現(xiàn)。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就算招式練的再花哨，終究成不了高手；只有內(nèi)功深厚者，前端之路才會走得...

    cheukyin 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

    摘要：常見的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。插入排序在實現(xiàn)上，通常采用排序即只需用到的額外空間的排序，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segm...

    GeekQiaQia 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

    摘要：常見的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。插入排序在實現(xiàn)上，通常采用排序即只需用到的額外空間的排序，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segm...

    cgspine 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

    摘要：常見的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。插入排序在實現(xiàn)上，通常采用排序即只需用到的額外空間的排序，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segm...

    lufficc 評論0 收藏0

發(fā)表評論

0條評論

fredshare

男|高級講師

TA的文章

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