前端技术分享

Appearance

排序算法

🕒 Published at:

前言 ​

研究算法一直是比较痛苦的事，因为算法极其抽象，不像做个轮播图抑或是导航栏那样直观可感，一段只有几行的代码，需要研究好几天才能参透其中奥妙。算法一直是我的短板，所以这次才下决心一定要研究透彻，话不多说，先上图。

要彻底理解上面的这张图，有必要先对一些名词术语做一些简单的解释。

时间复杂度 ​

时间复杂度是描述一个算法时间上运行长短的概念。以前我一直以为时间复杂度是一个定量的概念，可以直接通过时间复杂度算排序到底会经过几次计算，但其实它是一个定性的概念，也就是说它是模糊的，并不是一个精确的概念，无法进行精确的定量计算，同样时间复杂度为O(n^2)的算法，在最坏的情况下所需要的时间可能会差很多。那提出时间复杂度的概念有什么用？其实主要是为了粗略地比较各种算法之间的优劣，一般而言，常见的时间复杂度排序如下：

O（1）< O（logn）<O（n）<O（nlogn）<O（n2）<O（n3）<…<O（2n）<O（n!） 既然是粗略地比较，就有可能会有反例，这里涉及一些积分和概率论的知识，我在这里不做深入研究，有兴趣的童鞋可以自行Google。

空间复杂度 ​

和时间复杂度类似，空间复杂度是描述一个算法运行占用内存多少的概念。

In-place和Out-place ​

In-place表示不占用额外内存，对应空间复杂度为O(1) Out-place表示占用额外内存，简单来说就是在算法运行过程中，除了待排数字所占用的内存外，还要占用额外的内存。

稳定性 ​

相等元素排序后相对位置不发生改变即为稳定，否则为不稳定。简单来说就是序列中存在两个或两个以上的元素相等时，如果排序后这些元素的相对位置不发生改变，A在排序前在B的前面，排序后A仍然在B的前面，有这种效果的排序算法，我们就称它是稳定的，否则为不稳定。

冒泡排序 ​

这是最简单的一种排序算法了，两个for循环，这个算法要能够背下来，面试经常会问到，也应用得最广泛，一般10W以下的数据量，用这个算法基本就没什么问题。代码如下(为了避免麻烦，代码均是升序排列，如果需要降序排列的小伙伴，只需将代码粘贴后，修改符号即可)：

js
function bubbleSort(arr) {
      console.time('冒泡排序耗时');
      let len = arr.length;
      for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) { //相邻元素两两对比
           arr[j] = arr[j]+arr[j + 1]; //元素交换
            arr[j + 1] = arr[j]-arr[j+1];
            arr[j] = arr[j]-arr[j+1];
          }
        }
      }
      console.timeEnd('冒泡排序耗时');
      return arr;
    }

控制台测试 其实这个非常原始的代码还有一点点优化的空间，就是在元素交换的位置上将加法改为指数，我拿了3000个数据来测试，发现确实速度快了一两毫秒，但是我担心将加法改成指数容易出现未知的问题，主要是js有一个东西叫Infinity，如图：

所以我一般安全起见还是用前一种，大家可以自行选择。代码如下：

js
function bubbleSort(arr) {
      console.time('冒泡排序耗时');
      let len = arr.length;
      for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) { //相邻元素两两对比
            arr[j] = arr[j]**arr[j + 1]; //元素交换
            arr[j + 1] = arr[j]**arr[j+1];
            arr[j] = arr[j]**arr[j+1];
          }
        }
      }
      console.timeEnd('冒泡排序耗时');
      return arr;
    }

冒泡排序算法的3种变体 第一种

js
function bubbleSort1(arr) {
      console.time('1.1版冒泡排序耗时');
      let i = arr.length - 1; //初始时,最后位置保持不变　　
      while (i > 0) {
        let pos = 0; //每趟开始时,无记录交换
        for (let j = 0; j < i; j++) {
          if (arr[j] > arr[j + 1]) {
            pos = j; //记录交换的位置
            arr[j] = arr[j]+arr[j + 1]; //元素交换
            arr[j + 1] = arr[j]-arr[j+1];
            arr[j] = arr[j]-arr[j+1];
          }
        }
        i = pos; //为下一趟排序作准备
      }
      console.timeEnd('1.1版冒泡排序耗时');
      return arr;
    }

第二种

js
function bubbleSort2(arr) {
      let low = 0;
      let high = arr.length - 1; //设置变量的初始值
      let tmp, j;
      console.time('1.2版冒泡排序耗时');
      while (low < high) {
        for (j = low; j < high; ++j) { //正向冒泡,找到最大者
          if (arr[j] > arr[j + 1]) {
            tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
          }
        }
        --high; //修改high值, 前移一位
        for (j = high; j > low; --j) { //反向冒泡,找到最小者
          if (arr[j] < arr[j - 1]) {
            tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
          }
        }
        ++low; //修改low值,后移一位
      }
      console.timeEnd('1.2版冒泡排序耗时');
      return arr;
    }

第三种

js
function bubbleSort3(arr) {
      console.time('1.3版冒泡排序耗时');
      let low = 0;
      let high = arr.length - 1; //设置变量的初始值
      let tmp, j;
      while (low < high) {
        let pos1 = 0,
          pos2 = 0;
        for (let i = low; i < high; ++i) { //正向冒泡,找到最大者
          if (arr[i] > arr[i + 1]) {
            tmp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = tmp;
            pos1 = i;
          }
        }
        high = pos1; // 记录上次位置
        for (let j = high; j > low; --j) { //反向冒泡,找到最小者
          if (arr[j] < arr[j - 1]) {
            tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
            pos2 = j;
          }
        }
        low = pos2; //修改low值
      }
      console.timeEnd('1.3版冒泡排序耗时');
      return arr;
    }

冒泡排序总结 ​

经过我的测试，发现冒泡排序算法的三种变体确实要比原始的冒泡排序效率要高一点，但是同样的，它们更难理解，而且代码量看起来也要多，要多码一些字母符号，有兴趣的童鞋可以把代码粘走，自行体味。需要注意的是，1.3版冒泡排序效率的提升非常明显，值得仔细研究一下。

选择排序 ​

在时间复杂度上表现非常稳定的排序算法，因为无论什么数据进去都是O(n²)，但稳定性上是属于不稳定排序，适用数据量小，对稳定性没有要求的数据排序 代码如下：

js
function selectionSort(arr) {
    console.time('选择排序耗时：');
    let len = arr.length;
    let minIndex, temp;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.timeEnd('选择排序耗时：');
    return arr;
}

插入排序 ​

代码如下：

js
function insertionSort(arr) {
　　console.time('插入排序耗时：');
　　for (let i = 1; i < arr.length; i++) {
　　　　let key = arr[i];
　　　　let j = i - 1;
　　　　while ( arr[j] > key) {
　　　　　　arr[j + 1] = arr[j];
　　　　　    j--;
　　　　}
　　　　arr[j + 1] = key;
　　}
　　console.timeEnd('插入排序耗时：');
　　return arr;
}

二分法插入排序 ​

插入排序还有一种二分法插入排序，代码如下：

js
function binaryInsertionSort(arr) {
　　console.time('二分插入排序耗时：');
　　for (let i = 1; i < arr.length; i++) {
　　　　let key = arr[i], left = 0, right = i - 1;
　　　　while (left <= right) {
　　　　　　let middle = parseInt((left + right) / 2);
　　　　　　if (key < arr[middle]) {
　　　　　　　　right = middle - 1;
　　　　　　} else {
　　　　　　　　left = middle + 1;
　　　　　　}
　　　　}
　　　　for (let j = i - 1; j >= left; j--) {
　　　　　　arr[j + 1] = arr[j];
　　　　}
　　　　arr[left] = key;
　　}
　　console.timeEnd('二分插入排序耗时：');
　　return arr;
}

希尔排序 ​

代码如下：

js
function shellSort(arr) {
　　console.time('希尔排序耗时：');
　　let len = arr.length,
　　temp,
　　gap = 1;
　　while(gap < len/5) { //动态定义间隔序列
　　　　gap =gap*5+1;
　　}
　　for (gap; gap > 0; gap = Math.floor(gap/5)) {
　　　　for (let i = gap; i < len; i++) {
　　　　　　temp = arr[i];
　　　　　　for (let j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
　　　　　　　　arr[j+gap] = arr[j];
　　　　　　}
　　　　　　arr[j+gap] = temp;
　　　　}
　　}
　　console.timeEnd('希尔排序耗时：');
　　return arr;
}

归并排序 ​

代码如下：

js
function mergeSort(arr) { //采用自上而下的递归方法
　　let len = arr.length;
　　if(len < 2) {
　　　　return arr;
　　}
　　let middle = Math.floor(len / 2),
　　left = arr.slice(0, middle),
　　right = arr.slice(middle);
　　return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
　　let result = [];
　　console.time('归并排序耗时');
　　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());
　　}
　　console.timeEnd('归并排序耗时');
　　return result;
}

快速排序（最常用） ​

快排适用于数据量大(10W以上)，且对稳定性没有要求的数据排序，是经常要使用的排序方法，需要理解并掌握原理 代码如下：

js
function quickSort(arr, left, right) {
　　console.time('1.快速排序耗时');
　　if (left < right) {
　　　　let x = arr[right], i = left - 1, temp;
　　　　for (let j = left; j <= right; j++) {
　　　　　　if (arr[j] <= x) {
　　　　　　　　i++;
　　　　　　　　temp = arr[i];
　　　　　　　　arr[i] = arr[j];
　　　　　　　　arr[j] = temp;
　　　　　　}
　　　　}
　　　　console.log(arr) ;
　　　　console.log(left,i) ;
　　　　quickSort(arr, left, i - 1);
　　　　console.log(arr)
　　　　console.log(i,right)
　　　　quickSort(arr, i + 1, right);
　　}
　　console.timeEnd('1.快速排序耗时');
　　console.log(arr)
　　return arr;
}

还有一种便于理解的快速排序版本 代码如下：

js
let quickSort2 = function(arr) {
　　console.time('2.快速排序耗时');
　　if (arr.length <= 1) { return arr; }
　　let pivotIndex = Math.floor(arr.length / 2);
　　let pivot = arr.splice(pivotIndex, 1)[0];
　　console.log(pivot)
　　let left = [];
　　let right = [];
　　for (let i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　console.timeEnd('2.快速排序耗时');
　　return quickSort2(left).concat([pivot], quickSort2(right));
};

堆排序 ​

代码如下：

js
function heapSort(arr) {
　　console.time('堆排序耗时');
　　//建堆
　　let heapSize = arr.length, temp;
　　for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {　　
　　　　heapify(arr, i, heapSize);
　　}
　　//堆排序
　　for (let j = heapSize - 1; j >= 1; j--) {
　　　　temp = arr[0];
　　　　arr[0] = arr[j];
　　　　arr[j] = temp;
　　　　console.log(arr)
　　　　heapify(arr, 0, --heapSize);
　　}
　　console.timeEnd('堆排序耗时');
　　return arr;
}
function heapify(arr, x, len) {
　　let l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
　　if (l < len && arr[l] > arr[largest]) {
　　　　largest = l;
　　}
　　if (r < len && arr[r] > arr[largest]) {
　　　　largest = r;
　　}
　　if (largest != x) {
　　　　temp = arr[x];
　　　　arr[x] = arr[largest];
　　　　arr[largest] = temp;
　　　　console.log(arr)
　　　　heapify(arr, largest, len);
　　}
}

计数排序 ​

代码如下：

js
function countingSort(arr) {
　　let len = arr.length,
　　B = [],
　　C = [],
　　min = max = arr[0];
　　console.time('计数排序耗时');
　　for (let i = 0; i < len; i++) {
　　　　min = min <= arr[i] ? min : arr[i];
　　　　max = max >= arr[i] ? max : arr[i];
　　　　C[arr[i]] = C[arr[i]] ? C[arr[i]] + 1 : 1;
　　　　console.log(C)
　　}

　　// 计算排序后的元素下标
　　for (let j = min; j < max; j++) {
　　　　C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
　　　　console.log(C)
　　}
　　for (let k = len - 1; k >= 0; k--) {
　　　　B[C[arr[k]] - 1] = arr[k];
　　　　C[arr[k]]--;
　　　　console.log(B)
　　}
　　console.timeEnd('计数排序耗时');
　　return B;
}

计数排序还有一种变体

js
function countingSort2(arr) {
 　　let len = arr.length,
 　　B = [],
 　　C = [],
 　　min = max = arr[0];
 　　console.time('计数排序耗时');
 　　for (let i = 0; i < len; i++) { 　　　　min = min <= arr[i] ? min : arr[i]; 　　　　max = max >= arr[i] ? max : arr[i];
 　　　　C[arr[i]] = C[arr[i]] ? C[arr[i]] + 1 : 1;
 　　}
 　　for (let k = 0; k <len; k++) {
 　　　　let length = C[k]；
 　　　　for(let m = 0 ;m <length ; m++){
 　　　　　　B.push(k);
 　　　　}
 　　}
 　　console.timeEnd('计数排序耗时');
 　　return B;
 }

桶排序 ​

代码如下：

js
function bucketSort(arr, num) {
　　console.time('桶排序耗时');
　　if (arr.length <= 1) {
　　　　return arr;
　　}
　　let len = arr.length, buckets = [], result = [], min = max = arr[0], space, n = 0;

　　let index = Math.floor(len / num) ;
　　while(index<2){

　　　　num--;
　　　　index = Math.floor(len / num) ;
　　}

　　for (let i = 1; i < len; i++) {
　　　　min = min <= arr[i] ? min : arr[i];
　　　　max = max >= arr[i] ? max : arr[i];
　　}
　　space = (max - min + 1) / num;  //步长
　　for (let j = 0; j < len; j++) {
　　　　let index = Math.floor((arr[j] - min) / space);
　　　　if (buckets[index]) { // 非空桶，插入排序
　　　　　　let k = buckets[index].length - 1;
　　　　　　while (k >= 0 && buckets[index][k] > arr[j]) {
　　　　　　　　buckets[index][k + 1] = buckets[index][k];
　　　　　　　　k--;
　　　　　　}
　　　　　　buckets[index][k + 1] = arr[j];
　　　　} else { //空桶，初始化
　　　　　　buckets[index] = [];
　　　　　　buckets[index].push(arr[j]);
　　　　}
　　}
　　while (n < num) {
　　　　result = result.concat(buckets[n]);
　　　　n++;
　　}
　　console.timeEnd('桶排序耗时');
　　return result;
}

基数排序 ​

代码如下：

js
function radixSort(arr, maxDigit) {
　　console.time('基数排序耗时：');
　　let mod = 10;
　　let dev = 1;
　　let counter = [];
　　for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
　　　　for(let j = 0; j < arr.length; j++) {
　　　　　　let bucket = parseInt((arr[j] % mod) / dev);
　　　　　　if(counter[bucket]== null) {
　　　　　　　　counter[bucket] = [];
　　　　　　}
　　　　counter[bucket].push(arr[j]);
　　　　}
　　　　let pos = 0;
　　　　for(let j = 0; j < counter.length; j++) {
　　　　　　let value = null;
　　　　　　if(counter[j]!=null) {
　　　　　　　　while ((value = counter[j].shift()) != null) {
　　　　　　　　　　arr[pos++] = value;
　　　　　　　　}
　　　　　　}
　　　　}
　　}
　　console.timeEnd('基数排序耗时：');
　　return arr;
}