常见基础实用算法详解

常见排序算法按照线性时间划分可以分为两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

算法时间复杂度

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法。

冒泡排序、插入排序、归并排序和基数排序都是稳定的排序算法。

• 平方阶(O(n^2))排序:插入、选择和冒泡排序；
• 线性对数阶(O(nlog2n))排序：快速排序、堆排序和归并排序；
• O(n^1+§))排序,§是介于0和1之间的常数：希尔排序
• 线性阶(O(n))排序：基数排序，此外还有桶、箱排序。

相关概念

稳定：如果A原本在B前面，而A = B，排序之后A仍然在B的前面。

不稳定：如果a原本在b的前面，而a = b，排序之后a可能会出现在b的后面。

时间复杂度：对排序数据的总的操作次数反映当Ñ变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模Ñ的函数。

【1】快速排序算法(Quick Sort)

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlog n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

从数列中挑出一个元素，称为 “基准”（pivot），

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

代码实现

public class QuickSort {
    public static int[] quickSort(int[] arry,int low,int high){
        int partitionIndex;
        if (low<high){
            partitionIndex=getPartitionIndex(arry,low,high);
            quickSort(arry,low,partitionIndex-1);
            quickSort(arry,partitionIndex+1,high);
        }
        return arry;
    }
    //找到每一轮每一部分中的中间索引--左边小于等于该索引处值，右边大于等于该索引处值
    private static int getPartitionIndex(int[] arry, int low, int high) {
        //基准元素
        int temp=arry[low];
        while (low<high){
            //找到该次中第一个比基准元素小的元素位置
            while (low<high&&arry[high]>=temp){
                high--;
            }
            arry[low]=arry[high];
            //找到该次中第一个比基准元素大的元素位置
            while (low<high&&arry[low]<=temp){
                low++;
            }
            arry[high]=arry[low];
        }
        //将基准值赋值给索引处元素
        arry[low]=temp;
        return low;
    }
    public static void main(String[] args){
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        //默认 low=0,high=length-1
        int[] quickSort = QuickSort.quickSort(a, 0, a.length - 1);
        Arrays.stream(quickSort).forEach(System.out::println);
    }
}

快速排序是不稳定的排序，快速排序的时间复杂度为O(nlogn)，当n较大时使用快排比较好，当序列基本有序时用快排反而不好。

【2】堆排序算法

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

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：

将初始待排序关键字序列（R1，R2 … .Rn）构建成大顶堆，此堆为初始的无序区;

将堆顶元素R [1]与最后一个元素 - [R [n]的交换，此时得到新的无序区（R1，R2，… Rn中-1）和新的有序区（RN），且满足ř并[1,2，…，N-1] <= R [N];

由于交换后新的堆顶R [1]可能违反堆的性质，因此需要对当前无序区（R1，R2，… Rn中-1）调整为新堆，然后再次将R [1]与无序区最后一个元素交换，得到新的无序区（R1，R2 … .Rn-2）和新的有序区（RN-1，RN）的。不断重复此过程直到有序区的元素个数为ñ -1，则整个排序过程完成。

代码实现

var len;   // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) {  // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
function heapify(arr, i) {    // 堆调整
    var 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) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function heapSort(arr) {
    buildMaxHeap(arr);
    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

【3】归并排序

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序列的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序若将两个有序表合并成一个有序表，称为2-路归并。

算法步骤：

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
• 重复步骤3直到某一指针达到序列尾
• 将另一序列剩下的所有元素直接复制到合并序列尾

代码实现

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>0 && right.length>0) {
        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;
}

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

【4】二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法，又叫折半查找。

搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束。如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

【5】BFPRT(线性查找算法)

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，算法作者做了精妙的处理。

算法步骤：

将n个元素每5个一组，分成n/5(上界)组。

取出每一组的中位数，任意排序方法，比如插入排序。

递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。

【6】DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤：

访问顶点v；

依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

上述描述可能比较抽象，举个实例：

DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

【7】BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤

首先将根节点放入队列中。

从队列中取出第一个节点，并检验它是否为目标。

如果找到目标，则结束搜寻并回传结果。

否则将它所有尚未检验过的直接子节点加入队列中。

若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

• 重复步骤2。

【8】Dijkstra算法

戴克斯特拉算法（Dijkstra’s algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

算法步骤：

初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>，d(V0,Vi)为∞

从T中选取一个其距离值为最小的顶点W且不在S中，加入S

对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

【9】动态规划算法

动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

关于动态规划最经典的问题当属背包问题。

算法步骤：

最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

【10】朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

尽管是带着这些朴素思想和过于简单化的假设，但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

【11】冒泡排序（Bubble Sort）

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

算法步骤

比较相邻的元素如果第一个比第二个大，就交换它们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数;

针对所有的元素重复以上的步骤，除了最后一个;

重复步骤1〜3，直到排序完成。

代码实现

public class BubbleSort {
    public static int[] bubbleSort(int[] array){
        //总共需要length-1次冒泡
        for (int i=1;i<array.length;i++){
            //最后(i-1)个元素不需要再比较
            for(int j=0;j<array.length-i;j++){
                if(array[j]>array[j+1]){
                    int temp=array[j+1];
                    array[j+1]=array[j];
                    array[j]=temp;
                }
            }
        }
        return array;
    }
    public static void main(String[] args){
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        int[] quickSort = BubbleSort.bubbleSort(a);
        Arrays.stream(quickSort).forEach(System.out::println);
    }
}

冒泡排序是一种稳定的排序方法:

若数组初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n);

若数组初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n^2);

冒泡排序平均时间复杂度为O(n^2)。

该排序算法是可以优化的，实现思想为加入“ifSweeped”判断

【12】选择排序（Selection Sort）

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

算法步骤

Ñ个记录的直接选择排序可经过N-1趟直接选择排序得到有序结果，具体算法描述如下：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

代码实现

public class SelectionSort {
    public static int[] selectionSort(int[] array){
        //需要array.length-1次选择
        for (int i=0;i<array.length-1;i++){
            int min=array[i];//假设最小数
            int n=i;//假设最小数的索引
            //前面i个数不需要再排序
            for(int j=i+1;j<array.length;j++){
                //如果找到一个比min小的数就重新赋值min和n
                if(array[j]<min){
                    min=array[j];
                    n=j;
                }
            }
            //此时 min n分别为实际最小数及其索引
            array[n]=array[i];
            array[i]=min;
        }
        return array;
    }
    public static void main(String[] args){
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        int[] quickSort = SelectionSort.selectionSort(a);
        Arrays.stream(quickSort).forEach(System.out::println);
    }
}

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

【13】插入排序（Insertion Sort）

插入排序（插入分页）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤

从第一个元素开始，该元素可以认为已经被排序;

取出下一个元素，在已经排序的元素序列中从后向前扫描;

如果扫描到的元素（已排序）大于新元素，将该元素移到下一位置;

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置;

将新元素插入到该位置后;

重复步骤2〜5。

代码实现

public class insertionSort {
    public static int[] insertionSort(int[] array){
        for (int i=1;i<array.length;i++){
            //待插入元素
            int temp=array[i];
            int j;
            for(j=i-1;j>=0;j--){
                //将排序好的序列和temp比较，如果大于temp就移位然后继续比较
                if(array[j]>temp){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            //不大于temp的地方放入temp
            //这里注意for循环里面执行了 j--, 故而需要j+1
            array[j+1]=temp;
        }
        return array;
    }
    public static void main(String[] args){
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        int[] quickSort = insertionSort.insertionSort(a);
        Arrays.stream(quickSort).forEach(System.out::println);
    }
}

插入排序在实现上，通常采用就地排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

直接插入排序是稳定的排序。文件初态不同时，直接插入排序所耗费的时间有很大差异。

若文件初态为正序，则每个待插入的记录只需要比较一次就能够找到合适的位置插入，故算法的时间复杂度为O(n)，这是最好的情况。

若初态为反序，则第i个待插入记录需要比较i+1次才能找到合适位置插入，故时间复杂度为O(n^2)，这是最坏的情况。

直接插入排序的平均时间复杂度为O(n^2)。

【14】希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n^2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序也称递减增量排序算法，是非稳定性排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

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

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

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

算法步骤：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

按增量序列个数k，对序列进行k 趟排序；

每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

代码实现

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while (gap < len / 3) {         // 动态定义间隔序列
        gap = gap * 3 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap / 3)) {
        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;
        }
    }
    return arr;
}

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是“算法（第4版）”的合作者Robert Sedgewick提出的。

【15】计数排序（Counting Sort）

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

算法步骤

找出待排序的数组中最大和最小的元素;

统计数组中每个值为我的元素出现的次数，存入数组Ç的第我项;

对所有的计数累加（从ç中的第一个元素开始，每一项和前一项相加）;

反向填充目标数组：将每个元素我放在新数组的第C（ⅰ）项，每放一个元素就将C（ⅰ）减去1。

算法实现

function countingSort(arr, maxValue) {
      var bucket =new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
    return arr;
}

计数排序是一个稳定的排序算法。当输入的元素是n个0到k之间的整数时，时间复杂度是O（n + k），空间复杂度也是O（n + k），其排序速度快于任何比较排序算法。当ķ不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

【16】桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序（Bucket sort）的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

算法步骤

设置一个定量的数组当作空桶;

遍历输入数据，并且把数据一个一个放到对应的桶里去;

对每个不是空的桶进行排序;

从不是空的桶里把排好序的数据拼接起来。

例如要对大小为[1…1000]范围内的n个整数A[1…n]排序

首先，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1…10]的整数，集合B[2]存储 (10…20]的整数，……集合B[i]存储( (i-1)10, i10]的整数，i = 1,2,…100。总共有 100个桶。

然后，对A[1…n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任 何排序法都可以。

最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这 样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序，那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn – nlogm)

从上式看出，当m接近n的时候，桶排序复杂度接近O(n)

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

前面说的几大排序算法 ，大部分时间复杂度都是O（n2），也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O（n）的时间复杂度。但桶排序的缺点是：

1）首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。

2）其次待排序的元素都要在一定的范围内等等。

代码实现

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
    var i;
    var minValue = arr[0];
    var 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];               // 输入数据的最大值
      }
    }
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;           // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var 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 (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
    return arr;
}

桶排序最好情况下使用线性时间为O（n），桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O（n）中。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

【17】基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集;再按照高位排序，然后再收集。依次类推，直到最高位有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法步骤

取得数组中的最大数，并取得位数;

ARR为原始数组，从最低位开始取每个位组成基数数组;

对基数进行计数排序（利用计数排序适用于小范围数的特点）;

代码实现

// LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value =null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) !=null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O（N）的时间复杂度，而且分配之后得到新的关键字序列又需要O（n）的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O（d * 2n），当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O（N + K），其中ķ为桶的数量一般来说。N >> K，因此额外空间需要大概Ñ个左右。