排序算法的Javascript实现

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后面。