前端细究-常见排序算法JavaScript实现

谁借莪１个温暖的怀抱￠ 2023-07-13 03:33 54阅读 0赞

> 本文参考：百度百科对于排序的解释

## 常见排序算法的比较： ##

<table> 
 <thead> 
  <tr> 
   <th>排序算法</th> 
   <th>最佳时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>选择排序</td> 
   <td>O(N^2)</td> 
   <td>O(N^2)</td> 
   <td>O(N^2)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(N)</td> 
   <td>O(N^2)</td> 
   <td>O(N^2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(N)</td> 
   <td>O(N^2)</td> 
   <td>O(N^2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(N)</td> 
   <td>O(NlogN)</td> 
   <td>O(N^S)（1&lt;S&lt;2）</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(NlogN)</td> 
   <td>O(NlogN)</td> 
   <td>O(N^2)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(NlogN)</td> 
   <td>O(NlogN)</td> 
   <td>O(NlogN)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(NlogN)</td> 
   <td>O(NlogN)</td> 
   <td>O(NlogN)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

### 选择排序： ###

> 选择排序  
> （Selectionsort）是一种简单直观的排序算法。  
> 它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

#### JavaScript实现： ####

### 插入排序： ###

> 插入排序  
> （Insertionsort）是一种简单直观且稳定的排序算法。  
> 如果有一个**已经有序的数据序列**，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,算法适用于少量数据的排序，时间复杂度O(n^2)。是稳定的排序方法。  
> 插入算法把要排序的数组分成**两部分**：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

![在这里插入图片描述][20200310141639107.gif]

#### JavaScript实现： ####

//测试数组
    var arr = new Array(1, 3, 2, 8, 9, 1, 5);
    //插入排序
    function InsertionSort(arr) { 
        if (arr == null || arr.length < 2) { 
            return arr;
        }
        for (let i = 1; i < arr.length; i++) { 
            for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { 
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        return arr;
    }
    //控制台输出
    console.log(arr);
    InsertionSort(arr);
    console.log(arr);

### 冒泡排序 ###

> 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。  
> 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。  
> 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

#### JavaScript实现： ####

### 希尔排序 ###

> 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment  
> Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。  
> 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

#### JavaScript实现 ####

### 快速排序 ###

> 快速排序（Quicksort）是对冒泡排序的一种改进。 快速排序由C. A. R.  
> Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

#### JavaScript实现： ####

const quickSort = (array) => { 
     const sort = (arr, left = 0, right = arr.length - 1) => { 
      if (left >= right) { //如果左边的索引大于等于右边的索引说明整理完毕
       return
      }
     let i = left
     let j = right
     const baseVal = arr[j] // 取无序数组最后一个数为基准值
     while (i < j) { //把所有比基准值小的数放在左边大的数放在右边
      while (i < j && arr[i] <= baseVal) {  //找到一个比基准值大的数交换
       i++
      }
      arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
      while (j > i && arr[j] >= baseVal) {  //找到一个比基准值小的数交换
       j--
     }
      arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
     }
     arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
     sort(arr, left, j-1) // 将左边的无序数组重复上面的操作
     sort(arr, j+1, right) // 将右边的无序数组重复上面的操作
     }
     const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
     sort(newArr)
     return newArr
    }

### 堆排序 ###

> 堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

### 归并排序 ###

> 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and  
> Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

[20200310141639107.gif]: https://img-blog.csdnimg.cn/20200310141639107.gif