写作认知体系
  • 《技能记录》
  • algorithm
samy
2021-01-30

十大经典排序算法js版

# 主流排序算法概览

# 分类

十种常见排序算法可以分为两大类：

  • 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
  • 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

# 算法复杂度

![](./_image/01.classic-algo-js/21-23-24.jpg)

# 名词解释

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
  • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
  • **空间复杂度：**是指算法在计算机

内执行时所需存储空间的度量，它也是数据规模n的函数。

  • n: 数据规模
  • k:“桶”的个数
  • In-place: 占用常数内存，不占用额外内存
  • Out-place: 占用额外内存

# 算法

tips：常用的**【冒选归插】** 谐音：冒险归插

# 冒泡排序（Bubble Sort）

# 简介

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

# 算法描述

  • 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；
  • 重复步骤1~3，直到排序完成。

# 动图演示

![](./_image/01.classic-algo-js/bubbleSort.gif)

# 代码实现

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len-1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
                //[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
}//确保更大的在后面；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len-1; i++) {
      for (var j = 0; j < len - 1 - i; j++) {
          if (arr[j] > arr[j+1]) { //交互两边的位置；确保更大的在后面；
              [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
          }
      }
  }
  return arr;
}
var arr = [4,2,3,5]
console.log(bubbleSort(arr));//[ 2, 3, 4, 5 ]
1
2
3
4
5
6
7
8
9
10
11
12
13

# 算法分析

什么时候最快（Best Cases）：当输入的数据已经是正序时（都已经是正序）

什么时候最慢（Worst Cases）：当输入的数据是反序时（写一个for循环反序输出数据不就行了，干嘛要用你冒泡排序呢）

# 选择排序（Selection Sort）

# 简介

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：**首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。**以此类推，直到所有元素均排序完毕。

# 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

  • 初始状态：无序区为R[1..n]，有序区为空；
  • 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  • n-1趟结束，数组有序化了。

# 动图演示

![](./_image/01.classic-algo-js/selectionSort.gif)

# 代码实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
        //for (var j = i; j < len -1; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
            //if (arr[i] > arr[j]) {//也可以直接在循环里面替换；
        	//	[arr[i], arr[j]] = [arr[j], arr[i]];
      		//}
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
        //[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function selectionSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
      for (var j = i; j < len-1; j++) {
          if (arr[i] > arr[j]) {//内部循环找出最下的；
        	[arr[i], arr[j]] = [arr[j], arr[i]];
        }
      }
  }
  return arr;
}
var arr = [4,2,3,5]
console.log(selectionSort(arr));//[ 2, 3, 4, 5 ]
1
2
3
4
5
6
7
8
9
10
11
12
13

# 算法分析

在时间复杂度上表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度, 所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

# 归并排序（Merge Sort）

# 简介

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  1. 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）
  2. 自下而上的迭代

在《数据结构与算法JavaScript描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle. 然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是JavaScript编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。

# 算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列；
  • 对这两个子序列分别采用归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列。

# 动图演示

![](./_image/01.classic-algo-js/mergeSort.gif)

# 代码实现

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

function merge(left, right){
    var 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

# 插入排序（Insertion Sort）

# 简介

插入排序是一种基本排序，它的基本思路是构建有序序列，对于未排序的数据，在已排序的基础上，从右向左（或者二分查找）选择位置插入，维基百科-插入排序 (opens new window)。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

# 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

# 动图演示

![](./_image/01.classic-algo-js/insertionSort.gif)

# 代码实现

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

function insert_sort(input){//用for循环更易懂点
  var i, j, temp;
  for(i = 1; i < input.length; i++){
    temp = input[i];
    for(j = i-1; j >= 0 && input[j] > temp; j--)
      input[j+1] = input[j];
    input[j+1] = temp;
  }
  return input;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 算法分析

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

如果以比较次数和移动次数来衡量算法的效率，最好情况下，比较 n-1 次，移动 0 次，最坏情况，比较 n*(n-1)/2 次，移动 n*(n-1)/2 次。

# 快速排序（Quick Sort）

# 简介

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。 快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据最快的排序算法之一了。虽然Worst Case的时间复杂度达到了O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为O(n log n) 的排序算法表现要更好，查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

# 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  • 从数列中挑出一个元素，称为 “基准”（pivot）；
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

# 动图演示

![](./_image/01.classic-algo-js/quickSort.gif)

# 代码实现

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     //分区操作
    var pivot = left,                      //设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 算法分析

快速排序的最坏运行情况是O(n²)，比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ，且O(n log n)记号中隐含的常数因子很小，比复杂度稳定等于O(n log n)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

# 希尔排序（Shell Sort）

# 简介

希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。

# 代码实现

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {//动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

function shell_sort(input){
  var gap, i, j, temp;
  gap = input.length >> 1;
  while(gap > 0){
    for (i = gap; i < input.length; i++) {
      temp = input[i];
      for (j = i - gap; j >= 0 && input[j] > temp; j -= gap)
        input[j + gap] = input[j];
      input[j + gap] = temp;
    }
    gap = gap >> 1;
  }
  return input;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 堆排序（Heap Sort）

# 简介

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列

# 动图演示

![](./_image/01.classic-algo-js/buildMaxHeap.gif)

# 代码实现

var len;    //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {   //建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}

function heapify(arr, i) {     //堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 计数排序（Counting Sort）

# 简介

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

# 动图演示

![](./_image/01.classic-algo-js/countingSort.gif)

# 代码实现

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 桶排序（Bucket Sort）

# 简介

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。 为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

什么时候最快（Best Cases）：当输入的数据可以均匀的分配到每一个桶中

什么时候最慢（Worst Cases）：当输入的数据被分配到了同一个桶中

# 代码实现

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i]; //输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i]; //输入数据的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;//设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);//对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 基数排序（Radix Sort）

# 简介

基数排序有两种方法：

  1. MSD 从高位开始进行排序
  2. LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异： 基数排序：根据键值的每位数字来分配桶 计数排序：每个桶只存储单一键值 桶排序：每个桶存储一定范围的数值

# 动图演示

![](./_image/01.classic-algo-js/radixSort.gif)

# 代码实现

//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 二分插入排序

# 简介

思路基本同上，只是在查找插入位置的时候，不是依次查找，而是采用二分法：

将要查找的值每次与中间值比较，大于中间值，则在右边进行相同的查找，小于中间值则在左边进行比较查找，找到返回索引值，没找到返回-1。

二分查找的前提是有序数组

# 代码实现

function bin_insert_sort(input){
  var i, j, low, high, mid, temp;
  for(i = 1; i < input.length; i++){
    temp = input[i];
    high = i - 1;
    low = 0;
    while(low <= high){
      mid = parseInt((low + high) / 2);
      if(temp < input[mid]){
        high = mid - 1;
      }else{
        low = mid + 1;
      }
    }
    // low 位置就是要插入的位置
    for(j = i-1; j >= low; j--)
      input[j+1] = input[j];
    input[low] = temp;
  }
  return input;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.非递归：

function binarySearch(target,arr){
   var start = 0;
   var end = arr.length-1;
   while(start <= end){
       var mid = parseInt((start+end)/2);
       if(target == arr[mid]){
           return mid
       }else if(target > arr[mid]){
           start = mid + 1;
       }else if(target < arr[mid]){
           end = mid - 1;
       }else{
           return -1;
       }
   }
}
var arr = [1,2,4,6,8,9,11,34,67];
console.log(binarySearch(11,arr));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.递归：

function binarySearch(arr,target,start,end){
   var start = start || 0;
   var end = end || arr.length-1;
   var mid = parseInt((start+end)/2);
   if(target == arr[mid]){
            return mid
        }else if(target > arr[mid]){
            start = mid + 1;
            return binarySearch(arr,target,start,end);
        }else if(target < arr[mid]){
            end = mid - 1;
            return binarySearch(arr,target,start,end);
        }else{
            return -1;
   }
}
var arr = [1,2,4,6,8,9,11,34,67];
console.log(binarySearch(arr,11));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 参考链接

算法可视化来源：http://visualgo.net/

上次更新: 2022/04/15, 05:41:29
设计模式js版
数据结构及常用算法

← 数据结构及常用算法→

Copyright © 2015-2022 友一升 | yessz
×