js 排序算法

冒泡排序

简介：冒泡排序需要两个嵌套的循环. 其中, 外层循环移动游标; 内层循环遍历游标及之后(或之前)的元素, 通过两两交换的方式, 每次只确保该内循环结束位置排序正确, 然后内层循环周期结束, 交由外层循环往后(或前)移动游标, 随即开始下一轮内层循环, 以此类推, 直至循环结束. 平均时间复杂度 O(n²) 最好情况时间复杂度 O(n) 最坏情况时间复杂度 O(n²)

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - i - 1; j++) {
      let swap;
      if (array[j] > array[j + 1]) {
        swap = array[j];
        array[j] = array[j + 1];
        array[j + 1] = swap;
      }
    }
  }
  return array;
}

快速排序

简介：快速排序借用了分治的思想, 并且基于冒泡排序做了改进.它将数组拆分为两个子数组, 其中一个子数组的所有元素都比另一个子数组的元素小, 然后对这两个子数组再重复进行上述操作, 直到数组不可拆分, 排序完成. 平均时间复杂度 O(nlog₂n) 最好情况时间复杂度 O(nlog₂n) 最坏情况时间复杂度 O(n²)

var quickSort = function(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

选择排序

简介：内层循环每执行一遍, 将选出本次待排序的元素中最小(或最大)的一个, 存放在数组的起始位置. 而 外层循环则像老板一样, 它告诉内层循环你需要不停的工作, 直到工作完成(也就是全部的元素排序完成). 平均时间复杂度 O(n²) 最好情况时间复杂度 O(n²) 最坏情况时间复杂度 O(n²)

function SelectionSort(arr) {
  const length = arr.length;
  for (let i = 0; i < length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < length; j++) {
      minIndex = arr[minIndex] <= arr[j] ? minIndex : j;
    }
    if (minIndex !== i) {
      const temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

插入排序

把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 种类： 直接插入排序 , 折半插入排序(又称二分插入排序), 链表插入排序 , 希尔排序

• 直接插入排序（稳定排序）

  简介：将待排序的元素按照大小顺序, 依次插入到一个已经排好序的数组之中, 直到所有的元素都插入进去. 平均时间复杂度 O(n²) 最好情况时间复杂度 O(n²) 最坏情况时间复杂度 O(n²)

function directInsertionSort(array) {
  var length = array.length,
    index,
    current;
  for (var i = 1; i < length; i++) {
    index = i - 1; //待比较元素的下标
    current = array[i]; //当前元素
    while (index >= 0 && array[index] > current) {
      //前置条件之一:待比较元素比当前元素大
      array[index + 1] = array[index]; //将待比较元素后移一位
      index--; //游标前移一位
      //console.log(array);
    }
    if (index + 1 !== i) {
      //避免同一个元素赋值给自身
      array[index + 1] = current; //将当前元素插入预留空位
      //console.log(array);
    }
  }
  return array;
}

• 折半插入排序（稳定）

  简介：折半插入排序是直接插入排序的升级版. 鉴于插入排序第一部分为已排好序的数组, 我们不必按顺序依次寻找插入点, 只需比较它们的中间值与待插入元素的大小即可. 时间复杂度：时间复杂度都是 O(n²)

function binaryInsertionSort(array) {
  var current, i, j, low, high, m;
  for (i = 1; i < array.length; i++) {
    low = 0;
    high = i - 1;
    current = array[i];

    while (low <= high) {
      //步骤1&2:折半查找
      m = (low + high) >> 1;
      if (array[i] >= array[m]) {
        //值相同时, 切换到高半区，保证稳定性
        low = m + 1; //插入点在高半区
      } else {
        high = m - 1; //插入点在低半区
      }
    }
    for (j = i; j > low; j--) {
      //步骤3:插入位置之后的元素全部后移一位
      array[j] = array[j - 1];
    }
    array[low] = current; //步骤4:插入该元素
  }
  return array;
}

• 希尔排序（也称缩小增量排序）

  简介：实质就是分组插入排序，先分组再不断的进行直接插入排序

//形参增加步数gap(实际上就相当于gap替换了原来的数字1)
function directInsertionSort(array, gap) {
  gap = gap == undefined ? 1 : gap; //默认从下标为1的元素开始遍历
  var length = array.length,
    index,
    current;
  for (var i = gap; i < length; i++) {
    index = i - gap; //待比较元素的下标
    current = array[i]; //当前元素
    while (index >= 0 && array[index] > current) {
      //前置条件之一:待比较元素比当前元素大
      array[index + gap] = array[index]; //将待比较元素后移gap位
      index -= gap; //游标前移gap位
    }
    if (index + gap != i) {
      //避免同一个元素赋值给自身
      array[index + gap] = current; //将当前元素插入预留空位
    }
  }
  return array;
}

function shellSort(array) {
  var length = array.length,
    gap = length >> 1,
    current,
    i,
    j;
  while (gap > 0) {
    directInsertionSort(array, gap); //按指定步长进行直接插入排序
    gap = gap >> 1;
  }
  return array;
}

归并排序（稳定）

简介：归并排序建立在归并操作之上, 它采取分而治之的思想, 将数组拆分为两个子数组, 分别排序, 最后才将两个子数组合并; 拆分的两个子数组, 再继续递归拆分为更小的子数组, 进而分别排序, 直到数组长度为 1, 直接返回该数组为止. 归并排序可通过两种方式实现:（1）自上而下的递归（2）自下而上的迭代 平均时间复杂度 O(nlog₂n) 最好情况时间复杂度 O(nlog₂n) 最坏情况时间复杂度 O(nlog₂n)

• 递归

function mergeSort(array) {
  //采用自上而下的递归方法
  var length = array.length;
  if (length < 2) {
    return array;
  }
  var m = length >> 1,
    left = array.slice(0, m),
    right = array.slice(m); //拆分为两个子数组
  return merge(mergeSort(left), mergeSort(right)); //子数组继续递归拆分,然后再合并
}
function merge(left, right) {
  //合并两个子数组
  var result = [];
  while (left.length && right.length) {
    var item = left[0] <= right[0] ? left.shift() : right.shift(); //注意:判断的条件是小于或等于,如果只是小于,那么排序将不稳定.
    result.push(item);
  }
  return result.concat(left.length ? left : right);
}