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

資訊專欄INFORMATION COLUMN

排序算法的Javascript實現

tommego / 2127人閱讀

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

1.冒泡排序:

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

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]){  //發現前一個數大于后一個時,互換位置
        [this[j],this[j+1]] = [this[j+1],this[j]];
        changed = true;
      }
    }
    if(!changed) {      //如果本輪遍歷沒有發現位置調整,結束排序函數
      break;
    }
  }
};

let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.bubbleSort();
console.log(arr);

2.選擇排序

第i輪遍歷arr[0:n-i]選出最大的數,與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]) {   //當前值大于當前最大值時,記錄索引
        maxIndex = j;
      }
    }
    //將子數組最大值索引的值,與子數組末尾的值互換
    [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.插入排序
數組的前面部分已經排好序,要把當前數字插入到前面已排好序的數組的相應位置。可能有人會有疑問為什么默認數組前面部分已排好序?是怎么排好序的?是因為當排序開始時,從第2個數字開始進行向前插入,此時當前數字索引為1,當前數字前面僅有一個數字,因此可以認為前面部分已經排好序,將這個數字插入到相應位置之后數組仍然是有序的。每次都將當前數字插入到對應的位置,因此每次插入之后前面的數組仍是排好序的。

Array.prototype.insertSort = function () {
  let i, j;
  for (i = 1; i < this.length; i++) {   //i表示當前要向前插入的數字的索引,從1(即第2個數)開始前插
    let val = this[i];   //記錄當前要前插的數的大小
    /*
    * 用指針j來遍歷第i個數字前面的,已經排好序的子數組。當j沒有指到頭,并且j的數字大于要插入的數字時,說明
    * j還要向前遍歷,直到發現一個比要插入數字小的位置pos,然后將這個數字插到pos+1處。如果j已經指到頭了,
    * 到了-1了還沒有找到比當前數字小的位置,就把當前數字放在索引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的插入排序。分別以索引數為0,1,......step-1的元素為起點,將其看做不同的組,0、0+step,0+2step,......,0+nstep為一組,1,1+step,1+2step,.....,1+nstep為一組依次分組,按照組為單位進行插入排序。各組都已經插入排序一輪過后,將step除以2向下取整,再進行分組并將各組分別進行插入排序,直到step為0。
step的取值與性能直接相關,需要思考后取值。
并且這里的分組僅僅是邏輯上分組,并沒有開辟新的地址空間將其進行物理上的分組。

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這個數組要用合并排序。
先將相鄰兩數分為一組進行合并 43|12 32|29 66|78 31
結果為12 43 29 32 66 78 31

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

再將組的大小乘以二 12 43 29 32 | 66 78 31
合并結果:12 29 31 32 43 66 78

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

const {min} = Math;

function merge(arr1, arr2,) {
  let arr = [];
  let i = 0, j = 0;
  while (i < arr1.length && j < arr2.length) {
    arr1[i] < arr2[j] ? arr.push(arr1[i++]) : arr.push(arr2[j++]);
  }
  return i < arr1.length ? arr.concat(arr1.slice(i)) : arr.concat(arr2.slice(j))
}

Array.prototype.mergeSort = function () {
  let groupSize, i, secondPartSize, firstPart, secondPart, totalSize;
  //最初合并時,每組的大小僅為1,然后將組的大小乘以2。
  for (groupSize = 1; groupSize < this.length; groupSize *= 2) {
    for (i = 0; i < this.length; i += 2 * groupSize) {
      //前半段大小一定是groupSize,后半段則不一定
      secondPartSize = min(groupSize, this.length - i - groupSize);
      totalSize = secondPartSize + groupSize;
      //截取前后部分數組,將其排序
      firstPart = this.slice(i, i + groupSize);
      secondPart = this.slice(i + groupSize, i + groupSize + secondPartSize);
      this.splice(i, totalSize, ...merge(firstPart, secondPart));
    }
  }
};

let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.mergeSort();
console.log(arr);

6.自然合并排序

合并排序的分組是死板的沒有利用到數組中原本就是順序的子序列。

如果數組為 43 56 79 12 33 90 66
將其分組為 43 56 79 | 12 33 90 | 66
再將相鄰的,原本就是從小到大的順序的數組進行合并,效果會更好。

function merge(arr1, arr2) {
  let arr = [], i = 0, j = 0;
  while (i < arr1.length && j < arr2.length) {
    arr.push(arr1[i] < arr2[j] ? arr1[i++] : arr2[j++])
  }
  return arr.concat(i < arr1.length ? arr1.slice(i) : arr2.slice(j));
}

function getSortedArrList(arr) {
  //記錄下已經原本就是從小到大順序的子數組
  let sortedArrList = [];
  let childArr = [arr[0]];
  for (let i = 1; i < arr.length; i++) {
    //當前值小于上一個值時,將childArr加入sortedArrList中,創建新的childArr,并加入當前值。
    if (arr[i] < arr[i - 1]) {
      sortedArrList.push(childArr);
      childArr = [arr[i]];
    }
    //否則,將當前值加入到childArr中
    else {
      childArr.push(arr[i]);
    }
  }
  sortedArrList.push(childArr);
  return sortedArrList;
}

Array.prototype.naturalMergeSort = function() {
  let sortedArrList = getSortedArrList(this);  //獲取原本從小到大順序的子數組

  while (sortedArrList.length > 1) {    //當還有兩個及以上的數組沒合并完成時
    let newSortedArrList = [];
    for (let i = 0; i < sortedArrList.length; i += 2) {
      if (i !== sortedArrList.length - 1) {
        newSortedArrList.push(merge(sortedArrList[i], sortedArrList[i + 1]));
      }
      else {
        newSortedArrList.push(sortedArrList[i]);
      }
    }
    sortedArrList = newSortedArrList;
  }
  this.splice(0,this.length,...sortedArrList[0]);
};

let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.naturalMergeSort();
console.log(arr);

7.基數排序(LSD least significant digit first)
LSD中沒有數值之間的比較。建立一個[10][]的二維數組arr。
挑選出要排序數組中最大的數字,計算該數字的位數記為digitNum。將數組中的所有數字填充到digitNum位,位數不夠的高位補0。
然后遍歷digitNum次,從低位開始。第i次遍歷按照將數組中元素的第i位的數值,將元素num放到二維數組相應位置處,如果num第i位數值為n,則執行arr[n].push(num)的操作。每次遍歷之后,將arr[0:9]各數組的元素依次取出,并且重新初始化二維數組。直到遍歷到最高位為止,再取出的就是已經排好序的。

const {max} = Math;

function initBarrel() {
  let barrel = [];
  for (let i = 0; i < 10; i++) {
    barrel[i] = [];
  }
  return barrel;
}

function radixSort(arr) {
  let barrel = initBarrel();
  let figureNum = max(...arr).toString().length;  //計算最大的數字的位數
  arr = arr.map(num => num.toString().padStart(figureNum, "0"));  //將數字填充到figureNum位
  for (let i = 0; i < figureNum; i++) {
    let index = figureNum - i - 1;  //本次根據第index位來選擇放入哪個桶
    arr.forEach(numStr => {         //將填充過的數組放入桶中
      let num = Number(numStr[index]);
      barrel[num].push(numStr);
    });
    arr = barrel.reduce((prevArr, curArr) => prevArr.concat(curArr), []);//匯總barrel中的數
    barrel = initBarrel();    //初始化barrel
  }
  return arr.map(num => Number(num));   //最終轉為數字形式
}

Array.prototype.radixSort = function () {
  let arr = radixSort(this);
  this.splice(0, this.length, ...arr);
};

let arr = [1234342, 52165, 75, 1, 356, 575, 765433212, 57994, 3535];
arr.radixSort();
console.log(arr);

8.基數排序(MSD most significant digit first)
從高位開始,依然沒有數值之間的比較。
將最初的元素序列按照各元素最高位的數值進行分組,將分組后,組中只有一個元素或者多個相等元素的組拼接到result數組中,而有多個不同元素的組再遞歸地向下分,取的位次依次減少。

const {max} = Math;

function initBarrel() {
  let barrel = [];
  for (let i = 0; i < 10; i++) {
    barrel[i] = [];
  }
  return barrel;
}

//判斷當前桶中是否只有唯一值 有的桶中可能只有一種值,但是有多個重復項
function unique(barrel) {
  return new Set(barrel).size <= 1;
}

Array.prototype.radixSort = function () {
  let result = [];
  let figureNum = max(...this).toString().length;
  this.splice(0, this.length, ...this.map(num => num.toString().padStart(figureNum, "0")));
  radixGroup(this, 0, figureNum, result);
  this.splice(0, this.length, ...result.map(numStr => Number(numStr)));
};

function radixGroup(group, index, figureNum, result) {    //輸入的group是一組numStr,index是當前分桶依據第幾位數
  if (index < figureNum) {
    let barrel = initBarrel();
    group.forEach(numStr => {
      let idx = Number(numStr[index]);
      barrel[idx].push(numStr);
    });

    barrel.forEach(subBarrel => {
      if(unique(subBarrel)) {
        subBarrel.forEach(num => {
          result.push(num);
        })
      }
      else {
        radixGroup(subBarrel,index+1,figureNum,result);
      }
    })
  }
}
let arr = [1234342, 52165, 75, 1, 356, 575, 765433212, 57994, 3535];
arr.radixSort();
console.log(arr);

9.快速排序

將數組頭部的元素pivotNum作為一個基準,通過兩個指針指向數組的頭部和尾部,經過一次partition以后將pivotNum放在一個位置pivot,pivot前面的數小于pivotNum,后面的數大于pivotNum。
為了防止最壞情況的發生,可以在數組中隨機選出一個數來與數組頭部元素換位置,來降低具體實例與最壞情況的關聯性。

const {floor, random} = Math;

function randomIndex(start, end) {
  return floor(random() * (end - start + 1)) + start;
}

function partition(arr, start, end) {
  let index = randomIndex(start, end);
  [arr[start], arr[index]] = [arr[index], arr[start]];

  let value = arr[start];

  while (start < end) {
    while (start < end && arr[end] > value) end--;
    arr[start] = arr[end];
    while (start < end && arr[start] < value) start++;
    arr[end] = arr[start];
  }

  arr[start] = value;
  return start;
}

function quickSort(arr, start, end) {
  if (start < end) {
    let pivot = partition(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
  }
}

Array.prototype.quickSort = function (asc = true) {
  quickSort(this, 0, this.length - 1, asc)
};

let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.quickSort();
console.log(arr);

10.堆排序
將數組看做完全二叉樹,因此節點i的左右子節點的索引分別為2i+1與2i+2。通過從根節點開始令小的值下沉,或者從最后的葉節點開始令大的值上浮的方法,將一個數組構造成一個大根堆。再將大根堆的頭元素與尾元素換位置,這樣就將當前最大值置換到了尾部。然后下次構建大根堆的時候,將剛置換過的尾部元素刨除在外不做為節點。

const {floor, max} = Math;

function getBiggestNodeIndex(...nodes) {
  return nodes.indexOf(max(...nodes));
}

//將arr從0開始,長度為length的子數組構建為堆
function constructHeap(arr, length) {
  let adjusted = true;  //adjusted來標識本次堆是否作出了調整,若未調整說明堆已構建完畢
  while (adjusted) {
    adjusted = false;
    for (let i = 0; i < floor(length / 2); i++) {
      //當只有左節點時
      if (2 * i + 2 === length) {
        //當父節點比左節點小的時候
        if (arr[i] < arr[2 * i + 1]) {
          //互換
          [arr[i], arr[2 * i + 1]] = [arr[2 * i + 1], arr[i]];
          adjusted = true;
        }
      }
      //當同時有左節點和右節點時
      else {
        //判斷三個中最大的節點
        let biggestNodeIndex = getBiggestNodeIndex(arr[i], arr[2 * i + 1], arr[2 * i + 2]);
        //若父節點不是最大的,則和最大的交換
        //如果biggestNodeIndex為0,說明自己最大,為1,說明左節點大,為2,說明右節點大
        switch (biggestNodeIndex) {
          case 0:
            break;
          case 1:
            [arr[i], arr[2 * i + 1]] = [arr[2 * i + 1], arr[i]];
            adjusted = true;
            break;
          case 2:
            [arr[i], arr[2 * i + 2]] = [arr[2 * i + 2], arr[i]];
            adjusted = true;
            break;
        }
      }
    }
  }
}

function heepSort(arr) {
  //只將arr從0開始,長度為length的子數組構建成大根堆
  let length = arr.length;
  while (length > 1) {
    constructHeap(arr, length);
    [arr[0], arr[length-- - 1]] = [arr[length - 1], arr[0]];
  }
}

Array.prototype.heepSort = function () {
  heepSort(this);
};

let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.heepSort();
console.log(arr);

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

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

相關文章

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

    摘要:快速排序是不穩定的排序算法。瀏覽器的實現不同有什么影響排序算法不穩定有什么影響舉個例子某市的機動車牌照拍賣系統,最終中標的規則為按價格進行倒排序相同價格則按照競標順位即價格提交時間進行正排序。 本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復雜度,看看它有多快? 3、...

    itvincent 評論0 收藏0
  • 常用排序算法JavaScript實現

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

    jerry 評論0 收藏0
  • 優秀程序員都應該學習 GitHub 上開源數據結構與算法項目

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

    cheukyin 評論0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

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

    GeekQiaQia 評論0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

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

    cgspine 評論0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

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

    lufficc 評論0 收藏0

發表評論

0條評論

tommego

|高級講師

TA的文章

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