简介

本文介绍了冒泡、选择、插入、归并、快速、堆排序等多种排序的原理、js实现和性能表现。希望能把排序算法发光发热！

冒泡: 将数组相邻元素两两比较大小，一遍一遍把当前最大值（最小值）冒泡到最后。
选择: 通过数组循环，记录当前最小值（最大值）所在，再与第一个元素进行元素交换，依次类推。
插入: 对未排序数据中，从已排序序列中从后向前查询，找到相应的位置进行插入。
归并: 将数组拆分成n个一个元素的数组，再进行两两合并。从底层往上合并时，左右两边的数组都是排序好的，因此合并容易。
快排: 选择基准元素（一般是中间），所有小于基准的放在左边，大于基准的放在右边，重复直到结束。
堆排: 初始化堆后，将最后一个元素与堆顶元素交换后，最后元素移出堆排序序列中，再不断调整堆使满足堆的性质。

冒泡排序

算法简介

它的基本思想是：

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
再对最后一位以外的数组，重复前面的过程，直至全部排序完成。

举例子：

数组为[3,1,4,2], 3和1交换为[1,3,4,2], 第二位的3和4比较不交换，第三位的4和2交换为[1,3,2,4]。第一遍结束后，最后一个值必然是最大的。再重复以上操作，继续排序[1,3,2]数组,依次循环。

算法实现

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; 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;
            }
        }
    }
    return arr;
}

算法分析

最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

选择排序

算法简介

选择排序（Selection Sort）与冒泡排序类似，也是依次对相邻的数进行两两比较。不同之处在于，它不是每比较一次就调换位置，而是一轮比较完毕，找到最大值（或最小值）之后，将其放在正确的位置，其他数的位置不变。

举例子：

数组为[3,1,4,2], 先假设第一位3为最小值，当前的最小值为3，与第二位1比较，所以1是最小值。然后最小值与第三位4、第四位2比较，最小值不改变。
所以第一位3与最小值1进行交换，数组为[1,3,4,2]。
然后比较[3,4,2]数组。依次类推。

算法实现

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++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

算法分析

表现最稳定的排序算法之一，最佳最差都是O(n²)的时间复杂度。

插入排序

算法简介

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

举例子：

当前未排序数组为[3,1,4,2]，第二位1从已排序好的[3]插入，变为[1,3]。第三位4在[1,3]中插入变成[1,3,4], 第四位2在已排序好的[1,3,4]中排序变成[1,2,3,4]。

算法实现

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;
}

算法分析

最佳情况：输入数组按升序排列。T(n) = O(n)
最坏情况：输入数组按降序排列。T(n) = O(n2)
平均情况：T(n) = O(n2)

归并排序

算法简介

前三种时间复杂度太高，效率低，不适合实际使用。
基本思想：将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

举个例子：

[3,1,4,2]数组分成[3,1]和[4,2]两个部分，[3,1]分为[3]和[1]两部分，再合成[1,3]。同理右边合成了[2,4]。再将两者进行合并为[1,2,3,4]

算法实现

function mergeSort(arr) {
    var len = arr.length;
    if(len <= 1) {
        return arr;
    }
    var middle = Math.floor(arr.length/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());
        }
    }
    if(left.length) {
        result = result.concat(left);
    }

    if(right.length) {
        result = result.concat(right);
    }
    return result;
}

算法分析

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

最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)

快速排序

算法简介

速度快！效率高！是处理大数据最快的排序算法之一。
基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

（1）在数据集之中，选择一个元素作为”基准”（pivot）。
（2）所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
（3）对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

算法实现

var quickSort = function(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    var pivotIndex = Math.floor(arr.length/2);
    var pivot = arr.splice(pivotIndex, 1)[0]; //获取基准元素的值,同时原数组已经改变了
    var left = [];
    var right = [];
    for(var 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));
}

算法分析

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

最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(nlogn)

堆排序

算法简介

利用堆的概念来排序的选择排序。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

分为两种方法：

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

将待排序列构造成一个大顶堆(或小顶堆)，整个序列的最大值(或最小值)就是堆顶的根结点，将根节点的值和堆数组的末尾元素交换，此时末尾元素就是最大值(或最小值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值(或次小值)，如此反复执行，最终得到一个有序序列。

算法实现

根据数组元素构建一个完成二叉树
初始化大顶推（使父节点值大于子节点的值，从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换, 从下往上进行比较交换）
将堆的根节点（初始化后为当前二叉树的最大元素）与最后一个元素交换，同时把当前这个最大元素去除堆元素排序之外，堆的数量减一。
因为交换了元素后，很大可能不满足堆的性质了。从堆顶往下进行调整（使父节点值大于子节点的值，从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换, 从上往下进行交换）使堆满足堆的性质。重复3、4步骤，直到结束。

具体的流程图可以参考：http://www.cnblogs.com/0zcl/p/6737944.html

function heapSort(arr) {
    var heapSize = arr.length, temp;
    //建堆,初始化堆
    //length / 2 - 1是二叉树中最后一个非叶子结点的序号
    for (var i =  Math.floor(heapSize/2) - 1; i >= 0; i--) {
        heapify(arr, i, heapSize)
    }

    //堆进行排序
    for (var j = heapSize - 1; j >= 1 ; j--) {
        //将最后一个元素与堆顶元素交换
        temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;
        heapify(arr, 0, j);
    }
    return arr;
}

function heapify(arr, i, len) {
    //l,r是当前节点的左右孩子节点
    //当前节点的下标保存在largest中
    var l = 2*i + 1, r = 2*i + 2, largest = i, temp;

    if(l < len && arr[l] > arr[largest]) {
        //左节点大于父节点
        largest = l;
    }

    if (r < len && arr[r] > arr[largest]) {
        //右节点在父节点、左孩子节点中更大
        largest = r;
    }

    // 若i处的值比其左右孩子结点的值小，就将其和最大值进行交换
    if(largest != i) {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        // 交换后再查看剩下的堆是否满足堆的性质（以前满足）
        heapify(arr, largest, len);
    }
}

算法分析

参考：https://juejin.im/entry/5883501a128fe10065daaeb0