关于排序，面试的常考点，网上这类博客写的太好了，尤其是动态图这块，再者使用js编写，便于测试学习。
网友博客推荐一
网友博客推荐二
网友博客推荐三

定义

假设含有n个记录的序列为{r1,r2,…,rn}，其相应的关键字分别是{k1,k2,…,kn}，需确定1,2,…,n的一种排列p1,p2,…,pn,使其相应的关键字满足Kp1<=Kp2<=…<=Kpn(非递增或非递减)关系，即使得序列成为一个按关键字有序的序列{Rp1,Rp2,….,Rpn},这样的操作就称为排序。

基础知识

排序的稳定性

假设Ki = Kj(1<=i<=n,1<=j<=n,i不等于j),且在排序前的序列中Ri领先于Rj。如果排序后Ri仍然领先于Rj，则称所用的排序算法是稳定的，反之，若可能使得排序后的序列中Rj领先Ri,则称所用的排序算法是不稳定的。

通俗来说，
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

注意：排序算法是否稳定，是要通过分析后才能得出的；在排序过程中，只要有一组关键字实例发生类似情况，就可以认定此算法是不稳定的了。

算法稳定性的用途？
排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。（百度百科——排序算法稳定性）【个人感觉有点不太全面，后续总结】

内排序与外排序

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

主要讲解的是内排序。

对于内排序来说，排序算法的性能主要受3个方面的影响：

1. 时间性能：要求算法尽可能少的关键字比较次数和尽可能少的记录移动次数。（时间复杂度大O阶衡量）
2. 辅助空间：除了存放待排序所占用的存储空间之外，执行算法所需要的其它存储空间。（还是内存，不同于外排序中的外存，如硬盘）
3. 算法的复杂性：指的是算法本身的复杂度，不是指算法的时间复杂度。

内排序分为：插入排序（直接插入排序，希尔排序），交换排序（冒泡排序，快速排序），选择排序（简单选择，堆排序），归并排序。

按照算法的复杂度分：冒泡排序，简单选择排序，直接插入排序属于简单算法；希尔排序，堆排序，归并排序，快速排序属于改进算法。

排序算法

上网上截图一张，便于整体了解：

冒泡排序

冒泡排序（Bubble Sort）是一种交换排序，基本思想是，两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

最经典的冒泡算法js实现：

function bubbleSort(arr) {
    console.time('经典冒泡排序');
    var count = 0;//比较次数
    var count1 = 0;//交换次数
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            count++;
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                count1++;
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    console.timeEnd('经典冒泡排序');
    console.log('比较次数：'+count+'；交换次数：'+count1);
    return arr;
}
//var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
var arr=[2,1,3,4,5];
console.log(bubbleSort(arr));//

以上算法有缺陷，可以改进。
比如数组[2,1,3,4,5],i=0时，只交换一次，（2,1）交换下，就是有序的了，但是该算法继续去循环比较，这就浪费效率了。
改进版一：

function bubbleSort1(arr) {
    console.time('冒泡排序改进1');
    var count = 0;//比较次数
    var count1 = 0;//交换次数
    var len = arr.length;
    var flag = true;//标记
    for (var i = 0; i < len && flag; i++) {
        flag = false;//某次，下面的j循环，if均不成立，则代表排序完成，中断i的循环。
        for (var j = 0; j < len - 1 - i; j++) {
            count++;
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                count1++;
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
                flag = true;//有交换
            }
        }
    }
    console.timeEnd('冒泡排序改进1');
    console.log('比较次数：'+count+'；交换次数：'+count1);
    return arr;
}
var arr=[2,1,3,4,5];
console.log(bubbleSort1(arr));//[1,2,3,4,5]

以上代码，i=0时，循环j，有交换；i=1时，循环j，没有交换，flag为false，排序完成，终止循环。
这个适用于完全排序好的序列去中断循环，很多时候，排序提前做好了，后面的循环是无用的，使用这个改进方案，可以提高一定的效率。
还有一种改进方案，对于[2,1,3,4,5]也有较大的效率提高。

function bubbleSort2(arr) {
    console.time('冒泡排序改进2');
    var count = 0;//比较次数
    var count1 = 0;//交换次数
    var i = arr.length-1;  //初始时,最后位置保持不变
    while ( i> 0) {
        var pos= 0; //每趟开始时,无记录交换
        for (var j= 0; j< i; j++){
             count++;
            if (arr[j]> arr[j+1]) {
                count1++;
                pos= j; //记录交换的位置
                var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        }
        i= pos; //pos以后的已经排序好了，i直接跳过这段已经排序好的。

     }
     console.timeEnd('冒泡排序改进2');
     console.log('比较次数：'+count+'；交换次数：'+count1);
     return arr;
}
var arr=[2,1,3,4,5];
console.log(bubbleSort2(arr));

以上代码，在第一次循环时，i=len-1,循环后，i=0,退出循环。
这个适用于跳过最大端（最小端）部分排序好的片段，此处代码是，最大端，有一部分已经排序好了，i值直接跳过这一块，达到提高效率的目的，（最小端的代码类似，是以找出最小值为基准的）。

传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

function bubbleSort3(arr) {
    console.time('冒泡排序改进3');
    var low = 0;
    var high= arr.length-1; //设置变量的初始值
    var tmp,j;
    var count = 0;//比较次数
    var count1 = 0;//交换次数
    while (low < high) {
        for (j= low; j< high; ++j){ //正向冒泡,找到最大者
            count++;
            if (arr[j]> arr[j+1]) {
                count1++;
                tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        }
        --high;                 //修改high值, 前移一位
        for (j=high; j>low; --j){//反向冒泡,找到最小者
            count++;
            if (arr[j]< arr[j-1]) {
                count1++;
                tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;
            }
        }
        ++low;
    }
    console.timeEnd('冒泡排序改进3');
    console.log('比较次数：'+count+'；交换次数：'+count1);
    return arr;
}
var arr=[2,1,3,4,5];
console.log(bubbleSort3(arr));

以上算法，比较次数并没有减少，（交换次数肯定都一样），但是，运行时间测试中的确有较少（相对于经典冒泡排序）。
引用中，“使排序趟数几乎减少了一半”，但是每趟都是循环两次（一次找最大，一次找最小）。总次数并没有减少。我猜测，每趟求一个最大值，求一个最小值。由于冒泡的特性，在找最大值时，其它较大值会向最大值端冒泡（移动）；在找最小值时，其它较小值会向最小值端冒泡（移动），使得排序尽早完成了。但是上述算法，并没有做优化，仍然循环完了，导致比较次数和经典冒泡一致，所以应当对其进行如改进算法12的优化，才会有效率的提升吧。
在改进算法1和2中，算法2应该是更加优秀的。由于算法1条件比较苛刻，必须全部都排序好了才终止无用的循环，算法2是最大端有排序好的片段，则会跳过该片段，算法2的条件是包含算法1的条件的（全部排序好，是一种最大端有排序好的片段的特殊情况）。所以使用改进算法2来对算法3进行改进，证实“我猜测”是否对。

function bubbleSort4(arr) {
    console.time('冒泡排序改进4');
    var low = 0;
    var high= arr.length-1; //设置变量的初始值
    var tmp,j;
    var count = 0;//比较次数
    var count1 = 0;//交换次数
    while (low < high) {
        var high_pos = 0;
        for (j= low; j< high; ++j){ //正向冒泡,找到最大者
            count++;
            if (arr[j]> arr[j+1]) {
                count1++;
                high_pos = j;
                tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        }
        high = high_pos;
        --high;                 //修改high值, 前移一位

        var low_pos = 0;
        for (j=high; j>low; --j){//反向冒泡,找到最小者
            count++;
            if (arr[j]< arr[j-1]) {
                count1++;
                low_pos = j;
                tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;
            }
        }
        low = low_pos;
        ++low;
    }
    console.timeEnd('冒泡排序改进4');
    console.log('比较次数：'+count+'；交换次数：'+count1);
    return arr;
}
var arr=[2,1,3,4,5];
console.log(bubbleSort4(arr));

以上代码，比较次数明显减少，并且交换次数也减少了。
测试数据为：[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]。
证实“我猜测”有一定道理的。【后续有时间继续研究】。

冒泡的时间复杂度：
最好情况为O(n);
最坏情况为O(n2)。

简单选择排序算法

简单选择排序法（Simple Selection Sort）就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=n)个记录交换之。

它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

简单选择排序法js实现：

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    console.time('选择排序耗时');
    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;                 //将最小数的索引保存
            }
        }
        if(i!=minIndex){
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    console.timeEnd('选择排序耗时');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

简单选择排序算法的时间复杂度:
最好情况为O(n2);
最坏情况为O(n2)。

直接插入排序算法

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。

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

直接插入排序算法js实现：

function insertionSort(array) {
  console.time('插入排序耗时：');
    for (var i = 1; i < array.length; i++) {
        var key = array[i];//待插入的值
        var j = i - 1;
        while (j >= 0 && array[j] > key) {//循环i之前的元素，找到i的值正确的位置
            array[j + 1] = array[j];//j处的值往后挪一位，为将来插入i处的值留位置
            j--;
        }
        array[j + 1] = key;//i处的值插入正确位置
    }
    console.timeEnd('插入排序耗时：');
    return array;

}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

折半插入，改进后的插入排序，（查找插入位置时，是已排好序的序列，使用二分查找的方式）【感觉用处不大，还不如上面的算法】：

function binaryInsertionSort(array) {
    console.time('二分插入排序耗时：');
    for (var i = 1; i < array.length; i++) {
        var key = array[i], left = 0, right = i - 1;
        while (left <= right) {
            var middle = parseInt((left + right) / 2);
            if (key < array[middle]) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        for (var j = i - 1; j >= left; j--) {
            array[j + 1] = array[j];
        }
        array[left] = key;
    }
    console.timeEnd('二分插入排序耗时：');
    return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

插入排序的时间复杂度：
最好情况为O(n);
最坏情况为O(n2)。

希尔排序

希尔排序（Shell Sort）是D.L.Shell于1959年提出的一种排序算法，在这之前排序算法的时间复杂度基本都是O(n2)的，希尔排序算法是突破这个时间复杂度的第一批算法之一。

希尔排序是直接插入排序的改良。关键点：并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。“增量”的选取就非常关键了，目前还没有找到最好的增量序列。

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    console.time('希尔排序耗时:');
    while(gap < len/5) {          //动态定义间隔序列
        gap =gap*5+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/5))     {//间隔序列不断缩小，直至为1时，达到全部进行简单插入算法
        for (var i = gap; i < len; i++) {//某一个间隔，对子序列进行插入排序
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    console.timeEnd('希尔排序耗时:');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

堆排序

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想：将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点，将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值（n-1个元素的最大值，放到数组倒数第二位），如此反复执行，便能得到一个有序序列了。

其他一些定义：

• 堆定义：1.是一棵完全二叉树；2.每个结点的值都大于或者等于其左右孩子结点的值（大顶堆），或者每个结点的值都小于或等于其左右孩子结点的值（小顶堆）。
• 大顶堆的根节点一定是堆中所有结点的最大值，小顶堆则是最小值。
• 如果按照层次遍历的方式给结点从1开始编号，则有（大顶堆）Ki>=K2i,Ki>=K2i+1,[1<=i<=n/2]。这个可以查看二叉树的性质，大概意思，下标i与2i/2i+1是双亲子女关系。

堆排序的js实现：

/*方法说明：堆排序
@param  array 待排序数组*/
function heapSort(array) {
    console.time('堆排序耗时');
    //建堆
    var heapSize = array.length, temp;
    for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
        heapify(array, i, heapSize);
    }
    //堆排序
    for (var j = heapSize - 1; j >= 1; j--) {
        temp = array[0];
        array[0] = array[j];
        array[j] = temp;
        heapify(array, 0, --heapSize);//调整交换后的堆
    }
    console.timeEnd('堆排序耗时');
    return array;
}
/*方法说明：维护堆的性质
@param  arr 数组
@param  x   数组下标
@param  len 堆大小*/
function heapify(arr, x, len) {
    var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
    if (l < len && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < len && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != x) {
        temp = arr[x];
        arr[x] = arr[largest];
        arr[largest] = temp;
        heapify(arr, largest, len);
    }
}
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]

堆排序是一种不稳定的排序方法。
堆排序的最好（最坏，平均）时间复杂度为O(nlogn)。

归并排序

归并排序（Merging Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有N个记录，则可以看成是N个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（[x]表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为N的有序序列为止，这种排序方法称为2路归并排序。

“归并”一次的中文含义就是合并，并入的意思，而在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表。

归并排序的递归js实现

function mergeSort(arr) {  //采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {//单个元素的子序列
        return arr;
    }
    var middle = Math.floor(len / 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());
        }
    }
    //必定有一个子序列没有元素了。
    while (left.length)
        result.push(left.shift());
    while (right.length)
        result.push(right.shift());
    return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

归并排序：

• 时间复杂度均为O(nlogn)[最好，最坏，平均]
• 空间复杂度为O(n)
• 稳定的算法

快速排序

function quickSort(arr,min,max){
    if(min < max){
        var len1 = min;
        var len2 = max;

        //三个数字取中间值
        var mid = min + Math.floor((max-min)/2)
        if(arr[mid] > arr[max]){
            arr[max] = arr[mid]+arr[max];
            arr[mid] = arr[max]-arr[mid];
            arr[max] = arr[max]-arr[mid];
        }
        if(arr[min] > arr[max]){
            arr[max] = arr[min]+arr[max];
            arr[min] = arr[max]-arr[min];
            arr[max] = arr[max]-arr[min];
        }
        if(arr[mid] > arr[min]){
            arr[min] = arr[mid]+arr[min];
            arr[mid] = arr[min]-arr[mid];
            arr[min] = arr[min]-arr[mid];
        }

        var temp = arr[min];
        //选出中区元素，并把比其小的值放左边，大的放右边
        while(min<max){

            while(min < max && arr[max] >= temp){
                max--;
            }
            arr[min] = arr[max];

            while(min<max && arr[min] <= temp){
                min++;
            }
            arr[max] = arr[min];


        }
        arr[min] = temp;

        //递归调用
        quickSort(arr,len1,min-1);
        quickSort(arr,min+1,len2);
    }

}
//测试
var a = [12,2,69,1,27,111,19,15,100,1];
quickSort(a,0,a.length-1);
for(var i in a){
console.log(a[i]);

}