11.手撕快排算法和归并排序

快排算法思想

1. 在数据集之中，选择一个元素作为"基准"（pivot）。
2. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

实现

//递归实现
function quickSort(arr) {
  /*
   * 创建len保存数组的长度，每次获取数组的长度都要实时查询不利于性能；
   * index作为保存取到的中间值；
   * pivot保存比较参照物；
   * left、right作为子数组的容器；
   */
  var index,
    pivot,
    left = [],
    right = [];
  // 如果数组只有一位，就直接返回数组,递归的终止条件；
  if (arr.length <= 1) return arr;

  //获取中间值的索引，使用Math.floor向下取整；
  index = Math.floor(arr.length / 2);

  // 使用splice截取中间值，第一个参数为截取的索引，第二个参数为截取的长度；
  // 如果此处使用pivot=arr[index]; 那么将会出现无限递归的错误；
  // splice影响原数组，原数组长度减一；
  pivot = arr.splice(index, 1);

  // 小于arr[pivot]的存到left数组里，大于arr[pivot]的存到right数组；
  for (var i = 0; i < arr.length; i++) {
    if (pivot > arr[i]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // 不断把分割的左右子数组传入quickSort，直到分割的只有一位直接返回子数组本身，递归终止；

  // 把每次分割的数组一层一层的用concat连接起来；
  // 每一层left里的元素都小于对应的pivot,right里的元素都大于对应的pivot；
  return quickSort(left).concat(pivot, quickSort(right));
}

// 非递归算法

function quickSort(arr, left, right) {
  /*
   * len为数组的长度;
   * left为需要数组中参与排序的起始点；right为数组中参与排序的终止点;
   * left如果有传数字那么就为left，没有传参则为0；
   * right如果有传参那么就为right，没有传参则为len-1;
   * 有传参可能会部分排序可能不会排序，没传参默认排序整个数组;
   * partitionIndex为分组界限;
   */
  var len = arr.length,
    partitionIndex,
    left = typeof left !== "number" ? 0 : left,
    right = typeof right !== "number" ? len - 1 : right;

  // 如果需要排序的起始索引小于终止索引则执行排序;递归的终止条件；
  if (left < right) {
    // partition的返回值作为partitionIndex来分隔数组；
    // 索引partitionIndex左边的元素均小于arr[partitionIndex]；
    // 右边的元素均大于arr[partitionIndex]；
    partitionIndex = partition(arr, left, right);

    // 数组中小于arr[partitionIndex]的部分(索引left到partitionIndex-1)再次使用quickSort排序；
    quickSort(arr, left, partitionIndex - 1);

    // 数组中大于arr[partitionIndex]的部分(索引partitionIndex+1到right)再次使用quickSort排序；
    quickSort(arr, partitionIndex + 1, right);
  }
  // 递归执行直到不满足left<right;返回本身；
  return arr;
}

function partition(arr, left, right) {
  /*
   * 这部分是具体实现排序的部分；
   * 将left赋值给pivot，作为参照物，因为left在最左边，只需要从左到右比较一遍即可判断整个数组；
   * index索引是arr中待交换位置；
   */
  var pivot = left,
    index = pivot + 1;
  // for循环从参照物arr[pivot]下一个元素arr[pivot+1]开始一直比较到子数组结束arr[right]；
  for (var i = index; i <= right; i++) {
    // 循环中如果有任何小于参照物的，就将他交换到index的位置，然后index向右移动到下一个位置；
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }
  /*
   * 因为每次都是交换完后index移动到下一个位置，所以在循环结束时，index仍为待交换的位置；
   * 此时索引pivot+1到index-1的元素都小于参照物arr[pivot]；
   */

  // 交换pivot和index-1索引的值之后index-1索引左边全都是小于arr[index-1]的元素；
  swap(arr, pivot, index - 1);

  // 返回index-1作为拆分子数组的分界线；
  return index - 1;
}
/*
 * 普通的交换，将a[i]和a[j]的数值交换；
 */
function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function quickSort(num) {
  _quickSort(num, 0, num.length - 1); // 将整个num数组快速排序，left和right分别指向数组左右两端。
}
function _quickSort(num, left, right) {
  var list = [[left, right]]; // 将[left,right]存入数组中，类似于递归入栈
  while (list.length > 0) {
    // 若list不为空，循环弹出list最后一个数组进行快排
    var now = list.pop(); // 弹出list末尾。(也可用list.shift()取出list第一个数组，但在数据量较大时，这种方式效率较低)
    if (now[0] >= now[1]) {
      // 若左右指针相遇，待排序数组长度小宇1，则无需进行快排(注意不能写成now[0]==now[1]，这里now[0]是有可能大于now[1]的
      continue;
    }
    var i = now[0],
      j = now[1],
      flag = now[0]; // 以下与递归方法相同，请参考上面的递归详解
    while (i < j) {
      while (num[j] >= num[flag] && j > flag) j--;
      if (i >= j) {
        break;
      }
      while (num[i] <= num[flag] && i < j) i++;
      let temp = num[flag];
      num[flag] = num[j];
      num[j] = num[i];
      num[i] = temp;
      flag = i;
    }
    list.push([now[0], flag - 1]); // 将flag左边数组作为待排序数组，只需将左右指针放入list即可。
    list.push([flag + 1, now[1]]); // 将flag右边数组作为待排序数组，只需将左右指针放入list即可。
  }
}

归并排序思想

“归并”的意思是将两个或两个以上的有序表组合成一个新的有序表。假如初始序列含有 n 个记录，则可看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到[n/2]（向上取整）个长度为 2 或 1 的有序子序列；再两两归并，……，如此重复，直到得到一个长度为 n 的有序序列为止，这种排序方法称为 2-路归并排序。

步骤解析：

1、把长度为 n 的输入序列分成两个长度为 n/2 的子序列；

2、对这两个子序列继续分为 m/2 的子序列，一直分下去，直为 1 个元素；

3、将两个排序好的子序列合并成一个最终的排序序列。

特点：

速度仅次于快速排序，为稳定排序算法，一般用于总体无序，但是各子项相对有序的数列，属于分治思想，递归归并。

//归并排序
function mergeSort(arr) {
  var len = arr.length;
  if (len < 2) {
    return arr;
  }

  //首先将无序数组划分为两个数组
  var mid = Math.floor(len / 2);
  var left = arr.slice(0, mid);
  var right = arr.slice(mid, len);
  return merge(mergeSort(left), mergeSort(right)); //递归分别对左右两部分数组进行排序合并
}
//合并
function merge(left, right) {
  var result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      //如果左边的数据小于右边的数据，将左边数据取出，放在新数组中
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}
var arr = [3, 44, 38, 5, 47, 15, 36, 26];
console.log(mergeSort(arr)); //3,5,15,26,36,38,44,47