前端必知的十大排序算法

> 周末梳理了十种排序算法当作复习，给大家也一起重温一下，下面将讲解10种应用较多的排序算法，其代码实现使用了JavaScript。

### 冒泡排序

思路：

- 循环数组，比较当前元素和下一个元素，若当前元素比下一个大，则向上冒泡，这样一次循环之后最后一个数就是该数组最大的数。
- 下一次循环继续上面的操作，不循环已经排序好的数。
- 当一次循环没有发生冒泡，说明已经排序完成，停止循环。

```javascript
function bubbleSort(array){
  for(let i = 0; i < array.length; i++){
    let flag = true;
    for(let j = 0; j < array.length - 1 - i; j++){
      if(array[j] > array[j + 1]){
        [array[j],array[j + 1]] = [array[j + 1],arr[j]];
        flag = false;
      }
    }
    if(flag){// 没有冒泡，则停止循环
      break;
    }
  }
  return array;
}
```

- 时间复杂度：O($N^2$)
- 空间复杂度：O($1$)

稳定性：稳定

### 快速排序

思路：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据均比另一部分的小，再按这种方法对这两部分数据继续进行快排，排序过程使用递归进行，使整个数据变得有序。可以看出，快排利用了分治的思想。

- 选择一个基准元素target（一般选首项）
- 将比target小的元素移到数组左边，比target大的元素移到数组右边（与target相等的移动到哪边都可以）
- 继续对左右部分进行快排

![image](https://user-images.githubusercontent.com/47481681/126074921-d03d7418-99a5-4d56-b910-8fcd6a01eb30.png)


```javascript
/*
 * 法一：开辟left和right两个空间来存储
 * 每次递归返回left、target、right拼接后的数组
 */
function quickSort(array){
  if(array.length < 2) return array;
  const target = array[0];
  const left = [], right = [];
  for(let i = 0; i < array.length; i++){
    if(array[i] < target) {
      left.push(array[i]);
    }else{
      right.push(array[i]);
    }
  }
  return quickSort(left).concat([target],quickSort(right));
}

/*
 * 法二：双下标法
 * 声明l和r分别为首尾两个下标
 * 在 l < r 条件下，找到 array[r] < target的值赋给array[l]
 * 在 l < r 条件下，找到 array[r] >= target的值赋给array[r]
 * 当 l = r 时，左侧的值全部小于 target，右侧的值全部大于target，将target放到此位置
 * 相对于上一种方法，节省了空间
 */
function quickSort(arr,start,end){
  if(end - start < 1) {
    return; 
  }
  const target = array[start];
  let l = start, r = end;
  while(l < r){
    while(l < r && array[r] >= target){
      r--;
    }
    array[l] = array[r];
    while(l < r && array[l] < target){
      l++;
    }
    array[r] = array[l];
  }
  array[l] = target;
  quickSort(array, start, l - 1);
  quickSort(array, l + 1, end);
  return array;
}
```

- 时间复杂度：平均O($NlogN$)，最坏O($N^2$)，一般情况下小于O($NlogN$)
- 空间复杂度：O($logN$)，递归调用消耗

稳定性：不稳定

### 归并排序

思路：

归并排序（MERGE-SORT）是利用**归并**的思想实现的排序方法，该算法采用**分治**策略（分治法将问题**分**成一些小的问题然后递归求解，而**治**的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）。

- 将数组不断的进行一拆二，拆到每个数组中只有一个元素为止
- 对每个数组两两进行合并，其中每个数组内都是有序的

![v2-270f0c9a7cfb02a067f174412df4bb0b_b](https://user-images.githubusercontent.com/47481681/126074975-9057c4e0-600a-41f7-b6a0-48c2290e4c92.gif)


```javascript
// 分割数组时直接将数组分割为两个数组，合并时直接合并数组
function mergeSort(array){
  if(array.length < 2){
    return array;
  }
  const mid = Math.floor(array.length / 2);
  const left = array.slice(0, mid);
  const right = array.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const 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($NlogN$)
- 空间复杂度：O($N$)

稳定性：稳定

### 选择排序

思路：

每次循环选取一个最小的数字放到前面的有序序列中。

![选择排序](https://user-images.githubusercontent.com/47481681/126074996-291ff882-2111-4ac6-a7ad-626a6b7b8ce2.gif)


```javascript
function selectionSort(array, flag = false) { // flag用于选择顺序 
  for(let i = 0; i < array.length - 1; i++){
    let minIndex = i;
    for(let j = i + 1; j < array.length; j++){
      	if(array[j] < array[minIndex]){
          minIndex = j;
        }
    }
    [array[minIndex], array[i]] = [array[i], array[minIndex]];
  }
  return flag ? arr.reverse() : arr;
}
```

- 时间复杂度：O($N^2$)
- 空间复杂度：O($1$)

稳定性：不稳定

### 插入排序

思路：

- 将左侧序列看成一个有序序列，取出下一个元素，从右往左扫描扫描已排序的序列
- 如果该元素小于新元素，继续往前扫描，否则将该元素移到下一位
- 当找到元素小于或等于新元素的位置时，则停止
- 重复以上步骤至整个循环结束

![插入排序 (1)](https://user-images.githubusercontent.com/47481681/126075009-676a6477-1d13-4ae3-ad1e-a000d461982d.gif)


```javascript
function insertSort(array){
  for(let i = 0; i < array.length; i++){
    let preIndex = i - 1, cur = array[i];
    while(preIndex >= 0 && array[preIndex] > cur){
      array[preIndex + 1] = array[preIndex];
      preIndex--;
    }
    array[preIndex + 1] = cur;
  }
  return array;
}
```

- 时间复杂度：O($N^2$)
- 空间复杂度：O(1)

稳定性：稳定

### 堆排序

堆是具有以下性质的**完全二叉树**：

- 每个结点的值都大于或等于其左右孩子结点值，称为**大顶堆**

- 每个结点的值都小于或等于其左右孩子结点值，称为**小顶堆**

注意：没有要求结点的左右孩子结点值的大小关系。

大顶堆如下：

![image](https://user-images.githubusercontent.com/47481681/126075021-4e1ad39b-35fa-44f0-810b-14a7e038543c.png)


下标为i的节点的父节点下标：$(i-1)/2$取整

下标为i的节点的左孩子下标：$i*2+1$

下标为i的节点的右孩子下标：$i*2+2$

这里我们举例大顶堆的思路：

- 将待排序序列构造成一个大顶堆，取堆顶数字（也就是最大值）
- 再将剩下的数字构建一个大顶堆，取堆顶数字（也就是剩下值当中的最大值）
- 重复以上操作，直到取完堆中的数字，最终得到一个从大到小排列的序列

```javascript
/*
 * 维护堆的性质
 * @param arr 存储堆的数组
 * @param n 数组长度
 * @param i 待维护节点的下标
 */
function heapify(arr,n,i){
  let largest = i;
  let lson = i * 2 + 1;
  let rson = i * 2 + 2;
  // 找出父结点、左孩子、右孩子中最大的下标
  if(lson < n && arr[largest] < arr[lson]){
    largest = lson;
  }
   if(rson < n && arr[largest] < arr[rson]){
    largest = rson;
  }
  if(largest !== i){ 
    // 将最大的值赋值给父节点
    [arr[largest],arr[i]] = [arr[i],arr[largest]];
  	// 因为一个堆被改变了，会影响到子孩子的堆，所以需要进行递归
    heapify(arr, n, largest);
  }
}

// 堆排序入口
function heap_sort(arr, n){
  let i;
  // 建堆 [(n/2)-1] ---> [((n-1)-1)/2]，从后往前建堆
  for(i = (n / 2) - 1; i >= 0; i--){
    heapify(arr, n, i);
  }
  
  // 排序 大顶堆堆顶元素与最后一个元素交换
  for(i = n - 1; i >= 0; i--){
    [arr[i], arr[0]] = [arr[0], arr[i]];
    heapify(arr, i, 0);// 维护堆顶的元素
  }
  return arr;
}
// let arr = [2,3,8,1,4,9,10,7,16,14];
// let n = 10;
// heap_sort(arr, n);
```

- 时间复杂度：O($NlogN$)，其中建堆复杂度为O($N$)，heapify复杂度为O($logN$)
- 空间复杂度：O(1)

稳定性：稳定

### 希尔排序

希尔排序是为了加快速度，改进了插入排序，交换不相邻的元素以对数组的局部进行排序。

思路：

- 先对整个数组进行分组，通常为总长度的一半（奇偶数均可），这里我们将间隔设置为t。
- 先让数组中任意间隔为t的元素有序，再不断地将t缩小一半，继续做排序，直到t=1为止，当t=1时，数组已经是有序的了。

```javascript
function shellSort(arr){
  let len = arr.length, gap, temp;
  // 缩小增量gap
  for(gap = len >> 1; gap >= 1; gap>>=1){
    for(let i = gap; i < len; i++){
      let preIndex = i - gap;// 插入排序是从后往前的，preIndex代表当前元素的上一个元素
      if(arr[i] < arr[preIndex]){
        temp = arr[i];
        while(preIndex >= 0 && arr[preIndex] > temp){
          arr[preIndex + gap] = arr[preIndex];
          preIndex -= gap;
        }
        arr[preIndex + gap] = temp;
      }
    }
  }
  return arr;
}
// shellSort([8, 9, 1, 7, 2, 3, 5, 4, 6, 0]);
```

- 时间复杂度：最坏是O($N^2$)
- 空间复杂度：O(1)

稳定性：不稳定

### 计数排序

该排序适合对一定范围内的整数进行排序，空间取决于最大的数字。

思路：

统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

- 获取待排序数组的最大值，最小值，算出差值，如果最小值为负数
- 创建数组用于统计元素个数
- 遍历统计数组，按照统计数组中每个元素的个数和顺序将原数组元素加入结果数组

![89124171-815c0400-d507-11ea-9b77-e45ea157a96d](https://user-images.githubusercontent.com/47481681/126075052-571bbbc6-6856-42c0-8c37-b5f0aea3cad1.gif)


```javascript
function countingSort(arr, flag = 0){
  let min = arr[0], max = arr[0], len = arr.length;
  // 求最大最小值
  for(let i = 0; i < len; i++){
    max = Math.max(arr[i], max);
    min = Math.min(arr[i], min);
  }
  // 计算差值
  let s = max - min;
  console.log(s)
  // 创建数组用于统计元素个数
  let count = new Array(s).fill(0);
  for(let i = 0; i < len; i++){
    let index = arr[i] - min;// 创建下标
    count[index] += 1;
  }
  console.log(count)
  // 遍历统计数组，按照统计数组中每个元素的个数和顺序将原数组元素加入结果数组
  let res = [];
  for(let i = 0; i < s + 1; i++){
    if(count[i] === 0) continue;
    res.push(arr[arr.indexOf(i + min)]);
   	--count[i];
  }
  return flag ? res.reverse() : res;
}

// let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
// console.log(countingSort(arr))
```

- 时间复杂度：O($n + k$)
- 空间复杂度：O($n + k$)

稳定性：稳定

### 桶排序

当数组中取值范围过大，或者不是整数时，可以使用桶排序来解决，其类似于计数排序创建的统计数组，桶排序需要创建若干个“桶“来协助排序。

思路：

- 每一个桶代表一个区间范围，里面可以承载一个或多个元素，首先我们要创建这些桶并明确每个桶的区间范围。`区间大小 = （最大值 - 最小值）/ 桶的数量`
- 遍历原始数组，把各元素放入各自的桶中
- 每个桶内的元素分别排序
- 遍历所有桶，输出所有元素

![image](https://user-images.githubusercontent.com/47481681/126075061-a8f6d16b-956c-48e5-ac6c-20699f9db2be.png)

```javascript
function bucketSort(arr, size = 10){
  let max = Math.max(...arr),
      min = Math.min(...arr),
      count = Math.floor((max - min) / size) + 1;// 设置区间大小
  let buckets = [];
  for(let i = 0; i < count; i++){
    // 创建桶
    buckets.push([]);
  }
  for(val of arr){
    // 把每个元素归类，num表示桶的序号
    let num = Math.floor((val - min) / size);
    buckets[num].push(val);
  }
  let result = [];
  for(bucket of buckets){
    // 排序用任一排序算法都可以，如果数据量不大可以使用插入排序
    result.push(...insertSort(bucket));
  }
  return result;
}
// 插入排序
function insertSort(arr){
  for(let i =1; i < arr.length; i++){
    let j = i;
    let target = arr[j];
    while(j > 0 && arr[j - 1] > target){
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = target;
  }
  return arr;
}

// let arr = [3,6,3,2,87,23,673,0]
// bucketSort(arr, 5)
```

桶数量为N时，

- 时间复杂度：O($N$)
- 空间复杂度：O($N$)

稳定性：稳定

### 基数排序

思路：

先以个位数的大小来对数据进行排序，接着以十位数的大小来对数据进行排序，接着以百位数的......

在对某位数进行排序时，是用“桶”来排序的，排到最后，就是一组有序的元素。

- 设置大小范围为0 - 9的10个桶，然后把具有相同的数值的数放进桶
- 再把桶里的数按照0到9号桶的顺序取出来，重复个位、十位、百位......
- 最后排序完成

注意：不够位数的数值在前面补0

![v2-3a6f1e5059386523ed941f0d6c3a136e_b](https://user-images.githubusercontent.com/47481681/126075068-3fa817ed-5c33-4bdf-9ba2-dfecd4258818.gif)


```javascript
function radixSort(arr) {
  let maxLen = 0;
  // 算出最大值的位数
  for(let val of arr){
    let len = String(val).length;
    if(len > maxLen){
      maxLen = len;
    }
  }
  // 遍历各个位数并进行排序
  for(let i = 1; i <= maxLen; i++){
    arr = sort(arr, i, maxLen);
  }
  return arr;
}
// 对位数的排序
function sort(arr, index, maxLen){
  let buckets = [];
  for(let i = 0; i < 10; i++){
  // 创建十个桶
    buckets.push([]);
  }
  for(let val of arr){
    // str.padStart(targetLength,string)：
    // 使用指定字符串填充到目标字符串前面，使其达到目标长度；
    // 位数不够则进行补0
    let str = String(val).padStart(maxLen, '0');
    // 将对应数值的存入对应的桶 #
    let num = str[maxLen - index];
    buckets[num].push(val);
  }
  let result = [];
  for(let bucket of buckets){
    result.push(...bucket);
  }
  return result;
}
```

- 时间复杂度：O($k*N$)
- 空间复杂度：O($N + K$)

稳定性：稳定

动图来源：https://zhuanlan.zhihu.com/p/57088609

****

周末肝文，写作不易，如果你觉得有用或者喜欢，点个`star`吧～您的支持是我最大的鼓励！



Provide feedback

Saved searches

Use saved searches to filter your results more quickly

前端必知的十大排序算法 #1

冒泡排序

快速排序

归并排序

选择排序

插入排序

堆排序

希尔排序

计数排序

桶排序

基数排序

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

前端必知的十大排序算法 #1

Description

冒泡排序

快速排序

归并排序

选择排序

插入排序

堆排序

希尔排序

计数排序

桶排序

基数排序

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions