排序算法太多了，打开Google，搜索排序二字，出现了好多名字都没听过的，比如猴子排序、睡眠排序、面条排序。
今天也就复习一下常用的排序：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

按照时间复杂度

排序算法	时间复杂度	是否基于比较
冒泡、插入、选择	O(n²)	是
快排、归并	O(nlogn)	是
桶、计数、基数	O(n)	否

先抛出一个问题，插入排序与冒泡排序时间复杂度相同，都为O(n²)，为什么实际开发里，更倾向于用插入排序而不是冒泡排序

分析一个“排序算法”

排序算法的执行效率

1. 最好情况、最坏情况、平均情况时间复杂度
1. 时间复杂度的系数、常数、低阶
1. 比较次数和交换（或移动）次数

排序算法的内存消耗

排序算法的内存消耗可以用空间复杂度来衡量，我们还引入了一个叫原地排序的概念，就是空间复杂度是O(1)的排序算法。

排序算法的稳定性

稳定性,这个概念指的是如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

一个例子，假如 2，9，3，4，8，3 在排序后就是 2，3，3，4，5，8，9
这个例子中如果两个3顺序变了，那么就不稳定，反之稳定。

这是为什么呢？平时学习算法过程中，我总用整数来进行表示这些。
但是假如说给一个开发的场景，比如给一个订单进行排序，此时10w条数据，我们会希望按照金额从小到大排序。对于金额相同的数据，我们会按照下单时间从早到晚排序。对于这样一个排序需求，如何做？

借助稳定排序算法，先按照下单时间进行排序，再按照下单的金额进行排序。此时两遍排序之后，我们使用稳定的排序算法，将不会影响金额相同的两个对象，相同金额相同的订单仍然保持下单时间从早到晚有序。

冒泡排序

冒泡排序算法比较好理解，下面贴一下代码：

// arr为待排序数组，n为数组大小
function bubbleSort(arr, n){
    for(let i = 0; i < n; ++i) {
        let boolSort = false;
        for( let j = 0; j < n - i -1; ++j){
            if(arr[j] > arr[j + 1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                boolSort = true;
            }
        }
        if(!boolSort) break;
    }
    return arr;
}

冒泡排序是原地排序算法，它只涉及相邻数据的交换操作，只需要常量级的临时空间，所以他的空间复杂度为O(1).
是稳定的排序算法

插入排序

function insertSort(arr,n){
    for(i = 1; i < n ; ++i ){
        let value = arr[i];
        for(j = i - 1;j >=0;--j){
            if(arr[j] > value){
                arr[j+1] = arr[j]
            } else {
                break;
            }
        }
        arr[j+1] = value;
    }
}

插入排序是原地排序算法，只需要常量级的临时空间，所以他的空间复杂度为O(1).
是稳定的排序算法

选择排序

function selectionSort(arr) {
    for(let i = 0; i < arr.length-1; i++){
        let minIndex = i;
        for(let j = i+1; j < arr.length; j++){
            if(arr[j] < arr[minIndex] ){
                let t = arr[j];
                arr[j] = arr[minIndex];
                arr[minIndex] = t;
            }
        }
    }
}

选择排序不稳定，他每次都要找到未排序元素的最小值，并和前面元素交换位置，这样破坏了稳定性
选择排序是原地排序，时间复杂度为O(1)

解答开篇，由于冒泡排序数据交换要比插入排序的数据移动要复杂。
冒泡排序需要三个赋值操作，而插入排序只需要一个赋值操作。

Another Curtin

插入排序比冒泡排序更受欢迎？