排序各个算法特点

一. 冒泡排序

特点: 依次从头到尾相邻两个元素比较,如果左边比较高,就左右互换,每次遍历总数减去一.即:末尾是当前排序后最大的元素.
算法复杂度: O(n^2)

/**
 *@description 冒泡排序
 * @param {array} arr
 * @returns {array}
 */
function bubblingSort (arr) {
  const length = arr.length;
  for(var j = length - 1; j >= 0; j--) {
    for(var i = 0; i < j; i++) {
      let tmp = arr[i];
      if(tmp > arr[i+1]) {
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
      }
    }
  }
  return arr;
}

二.选择排序

特点: 从下标1位置开始,依次将最小值放在最前面,即:第一次遍历完,最小值在第一个位置,第二次遍历完,最小值在第二个位置.依次遍历到完整排序完.
算法复杂度: O(n^2)

/**
 *@description 选择排序
 * @param {array} arr
 * @returns {array}
 */
function selectionSort(arr) {
  const length = arr.length;
  for(var j = 0; j < length; j++) {
    let min = j;
    for(var i = j + 1; i < length; i++) {
      if (arr[i] < arr[min]) {
        min = i;
      }
    }
    if (min != j) {
      let tmp = arr[j];
      arr[j] = arr[min];
      arr[min] = tmp;
    } 
  }
  return arr;
}

三.插入排序

特点: 局部有序,从下标为1开始,左边为局部有序(单个元素默认为有序).后续依次比较左边元素,如果比标记值大则右移动.如果比标记值小.则将标记值插入到其后边.
算法复杂度: O(n^2)

/**
 *@description 插入排序
 * @param {array} arr
 * @returns {array}
 */
function insertSort(arr) {
  const length = arr.length;
  for(var i = 1; i < length; i++) {
    let tmp = arr[i];
    var j = i;
    while(arr[j - 1] > tmp && j > 0 ) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = tmp;
  }
  return arr;
}

四.希尔排序

特点: 先分组,比如按照5. 3. 2 1.主要是间隔问题.常规算法,取间距为N/2
也就是说对于N=100的数组,增量间隔序列为 50,25,12,6,3,1
算法复杂度最好情况: O(n^(1.3—2))

/**
 *@description 希尔排序
 * @param {array} arr
 * @returns {array}
 */
 function shellSort(arr) {
  const length = arr.length;
  // 初始化增量
  var gap = Math.floor(length / 2)
  while(gap >= 1) {
    for(var i = gap; i < length; i++) {
      var tmp = arr[i];
      var j = i;
      while(arr[j - gap] > tmp && j > gap - 1) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = tmp
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}

五.快速排序

特点:
算法复杂度: 最好 nlogn 最差 n平方

/**
 *@description 快速排序
 * @param {array} arr
 * @returns {array}
 */
function quickSort(arr) {
  // 数组分区, 左小右大
  function partition(arr, left, right) {
    let storIndex = left;
    let pivot = arr[right]; // 直接从右边的元素为基准元素
    // [1,2,3,4,5]
    for(let i = left; i < right; i++) {
      if (arr[i] < pivot) {
        let tmp = arr[storIndex];
        arr[storIndex] = arr[i];
        arr[i] = tmp;
        storIndex ++;
      }
    }
    let tmp = arr[storIndex];
    arr[storIndex] = arr[right];
    arr[right] = tmp;
    return storIndex;
  }
  // 排序主函数
  function sort(arr, left, right) {
    if(left > right) {
      return;
    }
    let storeIndex = partition(arr, left, right);
    sort(arr, left, storeIndex - 1);
    sort(arr, storeIndex + 1, right);
  }
  sort(arr,0, arr.length - 1);
  return arr;
}