1.冒泡排序：

比較相鄰的兩個(gè)數(shù)，如果前一個(gè)數(shù)大于后一個(gè)數(shù)，就將這兩個(gè)數(shù)換位置。每一次遍歷都會(huì)將本次遍歷最大的數(shù)冒泡到最后。為了將n個(gè)數(shù)排好序，需要n-1次遍歷。 如果某次遍歷中，沒(méi)有調(diào)整任何兩個(gè)相鄰的數(shù)的位置關(guān)系，說(shuō)明此時(shí)數(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++) {   //訪問(wèn)序列為arr[0:length-i]      if(this[j] > this[j + 1]){  //發(fā)現(xiàn)前一個(gè)數(shù)大于后一個(gè)時(shí)，互換位置        [this[j],this[j+1]] = [this[j+1],this[j]];        changed = true;      }    }    if(!changed) {      //如果本輪遍歷沒(méi)有發(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++) {  //訪問(wèn)子序列為arr[0:this.length-i]      if (this[j] > this[maxIndex]) {   //當(dāng)前值大于當(dāng)前最大值時(shí)，記錄索引        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)位置?？赡苡腥藭?huì)有疑問(wèn)為什么默認(rèn)數(shù)組前面部分已排好序？是怎么排好序的？是因?yàn)楫?dāng)排序開(kāi)始時(shí)，從第2個(gè)數(shù)字開(kāi)始進(jìn)行向前插入，此時(shí)當(dāng)前數(shù)字索引為1，當(dāng)前數(shù)字前面僅有一個(gè)數(shù)字，因此可以認(rèn)為前面部分已經(jīng)排好序，將這個(gè)數(shù)字插入到相應(yīng)位置之后數(shù)組仍然是有序的。每次都將當(dāng)前數(shù)字插入到對(duì)應(yīng)的位置，因此每次插入之后前面的數(shù)組仍是排好序的。

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

const {floor} = Math;//這個(gè)和插入排序相同，只不過(guò)加了stepArray.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.合并排序

舉個(gè)例子： 有 43 12 32 29 66 78 31這個(gè)數(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

合并的過(guò)程中要開(kāi)辟新的數(shù)組arr，建立兩個(gè)指針i,j分別指向arr1與arr2，此時(shí)arr1與arr2都是排好序的，然后每次都將arr1[i]與arr2[j]較小的數(shù)加到arr中并將指針后移。最后哪個(gè)數(shù)組有剩余的數(shù)在追加到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;  //最初合并時(shí)，每組的大小僅為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;      //截取前后部分?jǐn)?shù)組，將其排序      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.自然合并排序

合并排序的分組是死板的沒(méi)有利用到數(shù)組中原本就是順序的子序列。

如果數(shù)組為 43 56 79 12 33 90 66 將其分組為 43 56 79 | 12 33 90 | 66 再將相鄰的，原本就是從小到大的順序的數(shù)組進(jìn)行合并，效果會(huì)更好。

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) {  //記錄下已經(jīng)原本就是從小到大順序的子數(shù)組  let sortedArrList = [];  let childArr = [arr[0]];  for (let i = 1; i < arr.length; i++) {    //當(dāng)前值小于上一個(gè)值時(shí)，將childArr加入sortedArrList中，創(chuàng)建新的childArr，并加入當(dāng)前值。    if (arr[i] < arr[i - 1]) {      sortedArrList.push(childArr);      childArr = [arr[i]];    }    //否則，將當(dāng)前值加入到childArr中    else {      childArr.push(arr[i]);    }  }  sortedArrList.push(childArr);  return sortedArrList;}Array.prototype.naturalMergeSort = function() {  let sortedArrList = getSortedArrList(this);  //獲取原本從小到大順序的子數(shù)組  while (sortedArrList.length > 1) {    //當(dāng)還有兩個(gè)及以上的數(shù)組沒(méi)合并完成時(shí)    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.基數(shù)排序(LSD least significant digit first) LSD中沒(méi)有數(shù)值之間的比較。建立一個(gè)[10][]的二維數(shù)組arr。 挑選出要排序數(shù)組中最大的數(shù)字，計(jì)算該數(shù)字的位數(shù)記為digitNum。將數(shù)組中的所有數(shù)字填充到digitNum位，位數(shù)不夠的高位補(bǔ)0。 然后遍歷digitNum次，從低位開(kāi)始。第i次遍歷按照將數(shù)組中元素的第i位的數(shù)值，將元素num放到二維數(shù)組相應(yīng)位置處，如果num第i位數(shù)值為n，則執(zhí)行arr[n].push(num)的操作。每次遍歷之后，將arr[0:9]各數(shù)組的元素依次取出，并且重新初始化二維數(shù)組。直到遍歷到最高位為止，再取出的就是已經(jīng)排好序的。

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;  //計(jì)算最大的數(shù)字的位數(shù)  arr = arr.map(num => num.toString().padStart(figureNum, '0'));  //將數(shù)字填充到figureNum位  for (let i = 0; i < figureNum; i++) {    let index = figureNum - i - 1;  //本次根據(jù)第index位來(lái)選擇放入哪個(gè)桶    arr.forEach(numStr => {         //將填充過(guò)的數(shù)組放入桶中      let num = Number(numStr[index]);      barrel[num].push(numStr);    });    arr = barrel.reduce((prevArr, curArr) => prevArr.concat(curArr), []);//匯總barrel中的數(shù)    barrel = initBarrel();    //初始化barrel  }  return arr.map(num => Number(num));   //最終轉(zhuǎn)為數(shù)字形式}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.基數(shù)排序(MSD most significant digit first) 從高位開(kāi)始，依然沒(méi)有數(shù)值之間的比較。 將最初的元素序列按照各元素最高位的數(shù)值進(jìn)行分組，將分組后，組中只有一個(gè)元素或者多個(gè)相等元素的組拼接到result數(shù)組中，而有多個(gè)不同元素的組再遞歸地向下分，取的位次依次減少。

const {max} = Math;function initBarrel() {  let barrel = [];  for (let i = 0; i < 10; i++) {    barrel[i] = [];  }  return barrel;}//判斷當(dāng)前桶中是否只有唯一值 有的桶中可能只有一種值，但是有多個(gè)重復(fù)項(xiàng)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是當(dāng)前分桶依據(jù)第幾位數(shù)  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.快速排序

將數(shù)組頭部的元素pivotNum作為一個(gè)基準(zhǔn)，通過(guò)兩個(gè)指針指向數(shù)組的頭部和尾部，經(jīng)過(guò)一次partition以后將pivotNum放在一個(gè)位置pivot，pivot前面的數(shù)小于pivotNum，后面的數(shù)大于pivotNum。 為了防止最壞情況的發(fā)生，可以在數(shù)組中隨機(jī)選出一個(gè)數(shù)來(lái)與數(shù)組頭部元素?fù)Q位置，來(lái)降低具體實(shí)例與最壞情況的關(guān)聯(lián)性。

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.堆排序 將數(shù)組看做完全二叉樹(shù)，因此節(jié)點(diǎn)i的左右子節(jié)點(diǎn)的索引分別為2i+1與2i+2。通過(guò)從根節(jié)點(diǎn)開(kāi)始令小的值下沉，或者從最后的葉節(jié)點(diǎn)開(kāi)始令大的值上浮的方法，將一個(gè)數(shù)組構(gòu)造成一個(gè)大根堆。再將大根堆的頭元素與尾元素?fù)Q位置，這樣就將當(dāng)前最大值置換到了尾部。然后下次構(gòu)建大根堆的時(shí)候，將剛置換過(guò)的尾部元素刨除在外不做為節(jié)點(diǎn)。

const {floor, max} = Math;function getBiggestNodeIndex(...nodes) {  return nodes.indexOf(max(...nodes));}//將arr從0開(kāi)始，長(zhǎng)度為length的子數(shù)組構(gòu)建為堆function constructHeap(arr, length) {  let adjusted = true;  //adjusted來(lái)標(biāo)識(shí)本次堆是否作出了調(diào)整，若未調(diào)整說(shuō)明堆已構(gòu)建完畢  while (adjusted) {    adjusted = false;    for (let i = 0; i < floor(length / 2); i++) {      //當(dāng)只有左節(jié)點(diǎn)時(shí)      if (2 * i + 2 === length) {        //當(dāng)父節(jié)點(diǎn)比左節(jié)點(diǎn)小的時(shí)候        if (arr[i] < arr[2 * i + 1]) {          //互換          [arr[i], arr[2 * i + 1]] = [arr[2 * i + 1], arr[i]];          adjusted = true;        }      }      //當(dāng)同時(shí)有左節(jié)點(diǎn)和右節(jié)點(diǎn)時(shí)      else {        //判斷三個(gè)中最大的節(jié)點(diǎn)        let biggestNodeIndex = getBiggestNodeIndex(arr[i], arr[2 * i + 1], arr[2 * i + 2]);        //若父節(jié)點(diǎn)不是最大的，則和最大的交換        //如果biggestNodeIndex為0，說(shuō)明自己最大，為1，說(shuō)明左節(jié)點(diǎn)大，為2，說(shuō)明右節(jié)點(diǎn)大        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開(kāi)始，長(zhǎng)度為length的子數(shù)組構(gòu)建成大根堆  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);

END