一起来康康面试中常见的五大排序吧-一一网

前言

这里梳理一下自己理解的5种常见排序。包括思路与代码实现。

简单排序

冒泡排序
选择排序
插入排序

复杂排序

归并排序
快速排序

冒泡排序

说起冒泡排序,有没有想起事件冒泡。字面上可以理解为泡泡在水底向水面逐渐“漂浮”的过程。

实现思路

遍历数组,比较相邻的元素,前者比后者大的话,两者交换位置。
对每一组相邻元素做相同操作,从第一组到最后一组,这样子最后的元素就是最大元素。
针对n个元素重复以上步骤,每次循环排除当前最后一个。
重复步骤1~3，直至排序完成。

代码实现

function bubbleSort(arr, flag = 0) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return flag ? arr : arr.reverse();
}
复制代码

动画演示

冒泡排序

效率

时间复杂度O(N²)
比较次数O(N²)
交换次数O(N²)

选择排序

选择排序改进了冒泡排序, 将交换的次数由O(N²)减少到O(N), 但是比较的次数依然是O(N²)

实现思路

选定第一个索引位置，然后和后面元素依次比较
如果后面的元素, 小于第一个索引位置的队员, 则交换位置
经过一轮的比较后, 可以确定第一个位置是最小的
然后使用同样的方法把剩下的元素逐个比较即可
可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后

代码实现

function sertionSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    let min = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
    }
    [arr[min], arr[i]] = [arr[i], arr[min]];
  }
  return arr;
}
复制代码

动画演示

选择排序

效率

时间复杂度O(N²)
比较次数O(N²)
交换次数O(N)

插入排序

实现思路

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后, 重复上面的步骤.

代码实现

function insertionSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    let j = i;
    let temp = arr[i];
    while (arr[j - 1] > temp && j > 0) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}
复制代码

动画演示

效率

时间复杂度O(N²)
比较次数O(N²),但是比选中排序比较次数要少了一半
交换次数O(N)

归并排序

实现思路

将一个数组拆成A、B两个小组，两个小组继续拆，直到每个小组只有一个元素为止。
按照拆分过程逐步合并小组，由于各小组初始只有一个元素，可以看做小组内部是有序的，合并小组可以被看做是合并两个有序数组的过程。
对左右两个小数列重复第二步，直至各区间只有1个数。

代码实现

function mergeSort(arr) {
  if (arr.length < 2) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    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;
}
复制代码

动画演示

归并排序

效率

「时间复杂度: O(nlog(n))」

快速排序

实现思路

选择数组中间数作为基数，并从数组中取出此基数
准备两个数组容器，遍历数组，逐个与基数比对，较小的放左边容器，较大的放右边容器；
递归处理两个容器的元素，并将处理后的数据与基数按大小合并成一个数组，返回。

代码实现

function quickSort(arr) {
  if (arr.length < 2) return arr;
  let midIndex = Math.floor(arr.length / 2);
  let midItem = arr.splice(midIndex, 1)[0];
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < midIndex) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(midItem, quickSort(right));
}
复制代码