JS排序算法初探(一)

我不是女神ヾ 2022-05-26 04:49 156阅读 0赞

*   *  前言
     *  排序实现
        
         *  冒泡排序
         *  选择排序
         *  插入排序
         *  归并排序
         *  快速排序
     *  排序效率
     *  结论

## 前言 ##

这里是一些JavaScript版本的排序算法的探索，参考了以下文章：[Javascript的数据结构与算法(四)][Javascript]，分享一个排序可视化页面：[用HTML5实现的各种排序算法的动画比较][HTML5]

## 排序实现 ##

先定义一个交换函数：

function swap (arr, idx1, idx2) {  // 用于交互数组两个索引的值
      const aux = arr[idx2]
      arr[idx2] = arr[idx1]
      arr[idx1] = aux
    }

其实值交换有好几种方法，比如：

// 如果值为简单的数值类型
    let a = 1, b = 2
    a =^ b
    b =^ a
    a =^ b
    // 数组交换的骚操作，可读性很差
    let a = 'aa', b = 'bbb'
    a = [b， b = a][0]
    // 也可以使用ES2015的解构语法
    let a = 'qw', b = 'er'
    [a, b] = [b, a]
    // 如果是数组成员的值交换
    let arr = [1, 2]
    [arr[0], arr[1]] = [arr[1], arr[0]]
    // 在这里用最直观的临时变量交换的方法

### 冒泡排序 ###

描述：冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。  
算法实现：

### 选择排序 ###

描述：选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。  
算法实现：

### 插入排序 ###

描述：插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。这个算法和选择排序很像，选择排序是在未排序的数组中找到第n小的值，然后和数组的第n个成员交换值。而插入排序是拿出未排序数组的首位元素，然后对已排序数组的成员倒序进行比较，如果已排序数组的成员的值大于待排序的元素则将其值赋值给下一个已排序数组成员。直到找到比待排序的元素小的数组成员，然后将其插入到“小元素”的后面一位。  
算法实现：

function insertionSort(arr) {  // 插入排序
        const len = arr.length
        let temp, j
        for (let i = 1;i < len;i++) {
            temp = arr[i]
            j = i
            while(j > 0 && arr[j - 1] > temp) {
                arr[j] = arr[j - 1]
                j--
            }
            arr[j] = temp
        }
        return arr
    }

### 归并排序 ###

描述：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。  
算法实现：

function mergeSort(arr) {  // 归并排序
        function mergeSortRec(array) { 
            const len = array.length
            if (len === 1) return array
            const mid = Math.floor(len / 2)
            const leftArr = array.slice(0, mid)
            const rightArr = array.slice(mid, len)
            return merge(mergeSortRec(leftArr), mergeSortRec(rightArr))
        }
        function merge(leftArr, rightArr) { 
            const result = []
            let il = 0, ir = 0
            while(il < leftArr.length && ir < rightArr.length) {
                if (leftArr[il] < rightArr[ir]) {
                    result.push(leftArr[il++])
                } else {
                    result.push(rightArr[ir++])
                }
            }
            while(il < leftArr.length) {
                result.push(leftArr[il++])
            }
            while(ir < rightArr.length) {
                result.push(rightArr[ir++])
            }
            return result
        }
        return mergeSortRec(arr)
    }

### 快速排序 ###

描述：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序  
算法实现：

function quickSort(arr) {  // 快速排序
        const len = arr.length
        if (len <= 1) return arr
        const pivotIdx = Math.floor(len / 2)
        const pivot = arr.splice(pivotIdx, 1)[0]
        let leftArr = [], rightArr = []
        for (let i = 0;i < len - 1;i++) {
            if (arr[i] < pivot) {
                leftArr.push(arr[i])
            } else {
                rightArr.push(arr[i])
            }
        }
        return quickSort(leftArr).concat([pivot], quickSort(rightArr))
    }

## 排序效率 ##

先创建一个生成随机数据的数组方法：

const COUNT = 1000 // 待生成的数组成员个数
    const testArr = Array(COUNT).fill().map(val => ~~(Math.random() * COUNT))

结果如下：

<table> 
 <thead> 
  <tr> 
   <th align="left">排序算法\待排序数组个数</th> 
   <th>100</th> 
   <th>1000</th> 
   <th>10000</th> 
   <th>100000</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">冒泡排序</td> 
   <td>0.560ms</td> 
   <td>5.866ms</td> 
   <td>252.304ms</td> 
   <td>24602.321ms</td> 
  </tr> 
  <tr> 
   <td align="left">选择排序</td> 
   <td>0.209ms</td> 
   <td>3.143ms</td> 
   <td>119.986ms</td> 
   <td>15131.266ms</td> 
  </tr> 
  <tr> 
   <td align="left">归并排序</td> 
   <td>0.280ms</td> 
   <td>2.847ms</td> 
   <td>9.750ms</td> 
   <td>68.401ms</td> 
  </tr> 
  <tr> 
   <td align="left">快速排序</td> 
   <td>0.190ms</td> 
   <td>1.800ms</td> 
   <td>8.213ms</td> 
   <td>58.990ms</td> 
  </tr> 
 </tbody> 
</table>

由以上结果可以直观看出，四个排序算法中快速排序表现最为优异，在数组元素100以内的，大家的表现都差不多，1ms一下，1000个数组元素就已经拉开差距了，但还好，人类的反应速度最短诗100ms，所以还可以接受。但在100000数据元素级别，冒泡排序需要24s，选择排序也要15s，时间是比较久了，而归并排序和快速排序表现还很优异，不到70ms。  
实际上，测试了下，归并排序和快速排序在处理百万级别以下的数据量也可以保持在秒以内。

## 结论 ##

好的排序算法对大批量数据处理效率提升很有效。

[Javascript]: https://huang303513.github.io/2016/12/19/Javascript%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%28%E5%9B%9B%29.html
[HTML5]: http://www.webhek.com/post/comparison-sort.html