十大排序排序算法

[pfan123]

冒泡排序

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

export const bubbleSort = (arr = []) => {
    let len = arr.length
    for(let i = 0; i < len - 1; i++){
        for(let j = 0; j < len - 1 -i; j++ ){
            if(arr[j] > arr[j+1]){
                let temp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

export const selectionSort = (arr = []) => {
    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
    }    
    return arr 
}

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。+

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

export const insertSort = (arr = []) => {
    let len = arr.length
    let preIndex, current
    for(let 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
}

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

export const shellSort = (arr = []) => {
    let len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3){
        gap = gap*3 + 1
    }
    for(gap; gap > 0; gap = Math.floor(gap/3)){
        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
        }
    }
    return arr
}

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。+

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

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

const merge = (left, right) => {
    let result = []
    while (left.length && right.length) {
        if(left[0] <= right[0]){
            result.push(left.shift())
        }else{
            result.push(right.shift())
        }
    }

    return result.concat(left).concat(right)
}

export const mergeSort = (arr = []) => {
    let len = arr.length
    if(len <= 1)return arr 

    let middle = Math.floor(len / 2),
        left = arr(0, middle),
        right = arr(middle)
    return merge(mergeSort(left), mergeSort(right))
}

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。+

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

export const quickSort = (arr = []) => {
    if(arr.length <= 1)return arr
    let pivotIndex = Math.floor(arr.length / 2) //选择中间数
    let pivot = arr.splice(pivotIndex, 1)[0]  //中间数从原数组删除并保存
    let left = [], right = []
    for(let i = 0; i < arr.length; i++){
        if(arr[i] < pivot){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([pivot],quickSort(right))
}

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

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

let len

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

function heapify(arr, i) {     // 堆调整
    let 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){
    let temp = arr [i]
    arr[i] = arr[j]
    arr[j] = temp  
}

export const heapSort = (arr=[]) => {
    buildMaxHead(arr)
    for(let i = arr.length-1; i > 0; i++){
        swap(arr, 0, i)
        len--
        heapify(arr, 0);
    }
    return arr
}

计数排序

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

export const countingSort = (arr = [], maxValue) => {
    let bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1

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

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

    return arr 
}

桶排序

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

• 在额外空间充足的情况下，尽量增大桶的数量

• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

export const bucketSort = (arr = [], bucketSize) => {
    if (arr.length === 0) {
      return arr
    }

    let i
    let minValue = arr[0]
    let 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]              // 输入数据的最大值
      }
    }

    //桶的初始化
    let DEFAULT_BUCKET_SIZE = 5            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE
    let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1   
    let 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 (let j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j])                      
        }
    }

    return arr
}

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

let counter = []
export const radixSort = (arr = [], maxDigit) => {
    let mod = 10
    let dev = 1
    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
                }
          }
        }
    }
    return arr
}

参考资料

十大经典排序算法
js排序算法总结—冒泡，快速，选择，插入，希尔，归并