排序算法总结_排序算法的实现实验心得

前言

查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。

一般在面试中最常考的是快速排序和归并排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始，如果这些问题回答不好，估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握，有必要时要熟练写出代码。

接下来我们就分析一下常见的排序算法及其使用场景。限于篇幅，某些算法的详细演示和图示请自行寻找详细的参考。

冒泡排序

冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。举个栗子，对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。

实现代码：

选择排序

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)

实现代码：

插入排序

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。

实现代码：

快速排序

快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法。快速排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

举个栗子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。

5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。

5,3,8,6,4 首先设置i,j两个指针分别指向两端，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i,j位置。

5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。

4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。

上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。

快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。

实现代码：

其实上面的代码还可以再优化，上面代码中基准数已经在pivotKey中保存

了，所以不需要每次交换都设置一个temp变量，在交换左右指针的时候只需要先后覆盖就可以了。这样既能减少空间的使用还能降低赋值运算的次数。优化

代码如下：

总结快速排序的思想：冒泡+二分+递归分治，慢慢体会。。。

堆排序

（参考：https://www.cnblogs.com/lanhaicode/p/10546257.html）

堆是一种非线性结构，可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组

按照堆的特点可以把堆分为大顶堆和小顶堆

大顶堆：每个结点的值都大于或等于其左右孩子结点的值

小顶堆：每个结点的值都小于或等于其左右孩子结点的值

（堆的这种特性非常的有用，堆常常被当做优先队列使用，因为可以快速的访问到“最重要”的元素）

我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

我们用简单的公式来描述一下堆的定义就是：（读者可以对照上图的数组来理解下面两个公式）

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 

堆和普通树的区别

内存占用：

普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额外的内存。堆仅仅使用数组，且不使用指针

（可以使用普通树来模拟堆，但空间浪费比较大，不太建议这么做）

平衡：

二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(nlog2n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(nlog2n) 的性能
搜索：

在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作

堆排序的基本思想：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，

如此反复执行，便能得到一个有序序列了，建立最大堆时是从最后一个非叶子节点开始从下往上调整的

首先，实现堆排序需要解决两个问题：

1、如何由一个无序序列键成一个堆？

2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

第一个问题，将待排序序列（线性数组来表示一个堆）构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，

如此反复执行，便能得到一个有序序列了，建立最大堆时是从最后一个非叶子节点开始从下往上调整的。

第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。

从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2-1个元素，由此筛选即可。

6、图解交换过程（得到升序序列，使用大顶堆来调整）

这里以int a[6] = {7, 3, 8, 5, 1, 2}为例子

先要找到最后一个非叶子节点，数组的长度为6，那么最后一个非叶子节点就是：长度/2-1，也就是6/2-1=2，然后下一步就是比较该节点值和它的子树值，如果该节点小于其左\右子树的值就交换（意思就是将最大的值放到该节点）

8只有一个左子树，左子树的值为2，8>2不需要调整

 

下一步，继续找到下一个非叶子节点（其实就是当前坐标-1就行了），该节点的值为3小于其左子树的值，交换值，交换后该节点值为5，大于其右子树的值，不需要交换

下一步，继续找到下一个非叶子节点，该节点的值为7，大于其左子树的值，不需要交换，再看右子树，该节点的值小于右子树的值，需要交换值

下一步，检查调整后的子树，是否满足大顶堆性质，如果不满足则继续调整（这里因为只将右子树的值与根节点互换，只需要检查右子树是否满足，而7>2刚好满足大顶堆的性质，就不需要调整了，

如果运气不好整个树的根节点的值是1，那么就还需要调整右子树）

到这里大顶堆的构建就算完成了，然后下一步交换根节点（8）与最后一个元素（2）交换位置（将最大元素"沉"到数组末端），此时最大的元素就归位了，然后对剩下的5个元素重复上面的操作

（这里用粉红色来表示已经归位的元素）

剩下只有5个元素，最后一个非叶子节点是5/2-1=1，该节点的值（5）大于左子树的值（3）也大于右子树的值（1），满足大顶堆性质不需要交换

找到下一个非叶子节点，该节点的值（2）小于左子树的值（5），交换值，交换后左子树不再满足大顶堆的性质再调整左子树，左子树满足要求后再返回去看根节点，根节点的值（5）小于右子树的值（7），再次交换值

 

得到新的大顶堆，如下图，再把根节点的值（7）与当前数组最后一个元素值（1）交换，再重构大顶堆->交换值->重构大顶堆->交换值····，直到整个数组都变成有序序列

 

最后得到的升序序列如下图

实现代码：

#include <stdio.h>
 
void Swap(int *heap, int len);        /* 交换根节点和数组末尾元素的值 */
void BuildMaxHeap(int *heap, int len);/* 构建大顶堆 */
 
int main()
{
    int a[6] = {7, 3, 8, 5, 1, 2};
    int len = 6;    /* 数组长度 */
    int i;
 
    for (i = len; i > 0; i--)
    {
        BuildMaxHeap(a, i);
        Swap(a, i);
    }
    for (i = 0; i < len; i++)
    {
        printf("%d ", a[i]);
    }
 
    return 0;
}
/* Function: 构建大顶堆 */
void BuildMaxHeap(int *heap, int len)
{
    int i;
    int temp;
 
    for (i = len/2-1; i >= 0; i--)
    {
        if ((2*i+1) < len && heap[i] < heap[2*i+1])    /* 根节点大于左子树 */
        {
            temp = heap[i];
            heap[i] = heap[2*i+1];
            heap[2*i+1] = temp;
            /* 检查交换后的左子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
            if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) 
                || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2]))
            {
                BuildMaxHeap(heap, len);
            }
        }
        if ((2*i+2) < len && heap[i] < heap[2*i+2])    /* 根节点大于右子树 */
        {
            temp = heap[i];
            heap[i] = heap[2*i+2];
            heap[2*i+2] = temp;
            /* 检查交换后的右子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
            if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) 
                || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2]))
            {
                BuildMaxHeap(heap, len);
            }
        }
    }
}
 
/* Function: 交换交换根节点和数组末尾元素的值*/
void Swap(int *heap, int len)
{
    int temp;
 
    temp = heap[0];
    heap[0] = heap[len-1];
    heap[len-1] = temp;
}

希尔排序

希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

举个栗子：

从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。如上面的例子，第一堂排序时的增量为5，第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。

希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)。

实现代码：

public class ShellSort {

        /**

     * 希尔排序的一趟插入

     * @param arr 待排数组

     * @param d 增量

     */

    public static void shellInsert(int[] arr, int d) {

        for(int i=d; i<arr.length; i++) {

            int j = i - d;

            int temp = arr[i];    //记录要插入的数据  

            while (j>=0 && arr[j]>temp) {  //从后向前，找到比其小的数的位置   

                arr[j+d] = arr[j];    //向后挪动  

                j -= d;  

            }  

            if (j != i - d)    //存在比其小的数 

                arr[j+d] = temp;  

        }

    }

    public static void shellSort(int[] arr) {

        if(arr == null || arr.length == 0)

            return ;

        int d = arr.length / 2;

        while(d >= 1) {

            shellInsert(arr, d);

            d /= 2;

        }

    }

}　　

归并排序

归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易。其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。。。。。倒着来看，其实就是先两两合并，然后四四合并。。。最终形成有序序列。空间复杂度为O(n)，时间复杂度为O(nlogn)。

举个栗子：

实现代码：

public class MergeSort {
    void mergeSort(std::vector<int>& arr) {
        mSort(arr, 0, arr.size()-1);
    }
 
    /**
     * 递归分治
     * @param arr 待排数组
     * @param left 左指针
     * @param right 右指针
     */
 
    void mSort(std::vector<int>& arr, int left, int right) {
        if (left >= right)
            return;
 
        int mid = (left + right) / 2;
 
        mSort(arr, left, mid); //递归排序左边
        mSort(arr, mid+1, right); //递归排序右边
        merge(arr, left, mid, right); //合并
 
    }
 
    /**
     * 合并两个有序数组
     * @param arr 待合并数组
     * @param left 左指针
     * @param mid 中间指针
     * @param right 右指针
     */
    void merge(std::vector<int>& arr, int left, int mid, int right) {
        // [left, mid] [mid+1, right]
        std::vector<int> temp; //中间数组
        temp.reserve(right - left + 1);
 
        int i = left;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        
        while(i <= mid) {
            temp[k++] = arr[i++];
        }
 
        while(j <= right) {
            temp[k++] = arr[j++];
        }
 
        for(int p=0; p<temp.size(); p++) {
            arr[left + p] = temp[p];
        }
    }
}

计数排序

如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。

实现代码：

public class CountSort {

    public static void countSort(int[] arr) {

        if(arr == null || arr.length == 0)

            return ;

        int max = max(arr);

        int[] count = new int[max+1];

        Arrays.fill(count, 0);

        for(int i=0; i<arr.length; i++) {

            count[arr[i]] ++;

        }

        int k = 0;

        for(int i=0; i<=max; i++) {

            for(int j=0; j<count[i]; j++) {

                arr[k++] = i;

            }

        }

    }

    public static int max(int[] arr) {

        int max = Integer.MIN_VALUE;

        for(int ele : arr) {

            if(ele > max)

                max = ele;

        }

        return max;

    }

}

桶排序

桶排序算是计数排序的一种改进和推广，但是网上有许多资料把计数排序和桶排序混为一谈。其实桶排序要比计数排序复杂许多。

对桶排序的分析和解释借鉴这位兄弟的文章（有改动）：http://hxraid.iteye.com/blog/647759

桶排序的基本思想：

假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。bindex=f(key)   其中，bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1<k2，那么f(k1)<=f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然，映射函数的确定与数据本身的特点有很大的关系。

举个栗子：

假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如图所示。只要顺序输出每个B[i]中的数据就可以得到有序序列了。

桶排序分析：

桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，希尔排序中的子序列，归并排序中的子问题，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。　

对N个关键字进行桶排序的时间复杂度分为两个部分：

(1) 循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。

(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为  ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。

很显然，第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此，我们需要尽量做到下面两点：

(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。

(2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

总结： 桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

实现代码：

public class BucketSort {

    public static void bucketSort(int[] arr) {

        if(arr == null && arr.length == 0)

            return ;

        int bucketNums = 10; //这里默认为10，规定待排数[0,100)

        List<List<Integer>> buckets = new ArrayList<List<Integer>>(); //桶的索引

        for(int i=0; i<10; i++) {

            buckets.add(new LinkedList<Integer>()); //用链表比较合适

        }

        //划分桶

        for(int i=0; i<arr.length; i++) {

            buckets.get(f(arr[i])).add(arr[i]);

        }

        //对每个桶进行排序

        for(int i=0; i<buckets.size(); i++) {

            if(!buckets.get(i).isEmpty()) {

                Collections.sort(buckets.get(i)); //对每个桶进行快排

            }

        }

        //还原排好序的数组

        int k = 0;

        for(List<Integer> bucket : buckets) {

            for(int ele : bucket) {

                arr[k++] = ele;

            }

        }

    }

    /**

     * 映射函数

     * @param x

     * @return

     */

    public static int f(int x) {

        return x / 10;

    }

}

基数排序

基数排序又是一种和前面排序方式不同的排序方式，基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。。。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。

举个栗子：

实现代码：

public class RadixSort {

    public static void radixSort(int[] arr) {

        if(arr == null && arr.length == 0)

            return ;

        int maxBit = getMaxBit(arr);

        for(int i=1; i<=maxBit; i++) {

            List<List<Integer>> buf = distribute(arr, i); //分配

            collecte(arr, buf); //收集

        }

    }

    /**

     * 分配

     * @param arr 待分配数组

     * @param iBit 要分配第几位

     * @return

     */

    public static List<List<Integer>> distribute(int[] arr, int iBit) {

        List<List<Integer>> buf = new ArrayList<List<Integer>>();

        for(int j=0; j<10; j++) {

            buf.add(new LinkedList<Integer>());

        }

        for(int i=0; i<arr.length; i++) {

            buf.get(getNBit(arr[i], iBit)).add(arr[i]);

        }

        return buf;

    } 
      /**

     * 收集

     * @param arr 把分配的数据收集到arr中

     * @param buf 

     */

    public static void collecte(int[] arr, List<List<Integer>> buf) {

        int k = 0;

        for(List<Integer> bucket : buf) {

            for(int ele : bucket) {

                arr[k++] = ele;

            }

        }

    }

    /**

     * 获取最大位数

     * @param x

     * @return

     */

    public static int getMaxBit(int[] arr) {

        int max = Integer.MIN_VALUE;

        for(int ele : arr) {

            int len = (ele+"").length();

            if(len > max)

                max = len;

        }

        return max;

    }

    /**

     * 获取x的第n位，如果没有则为0.

     * @param x

     * @param n

     * @return

     */

    public static int getNBit(int x, int n) {

        String sx = x + "";

        if(sx.length() < n)

            return 0;

        else

            return sx.charAt(sx.length()-n) - '0';

    }

}

总结

在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的，需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序，只有最适合的排序。

下面就总结一下排序算法的各自的使用场景和适用场合。

1、从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。

2、上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。

3、基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。

4、从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。

5、上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。

附：基于比较排序算法时间下限为O(nlogn)的证明：

基于比较排序下限的证明是通过决策树证明的，决策树的高度Ω（nlgn），这样就得出了比较排序的下限。

首先要引入决策树。

首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。 先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。 具有L片树叶的二叉树的深度至少是logL。 所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。 而 log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1 >=logn+log(n-1)+log(n-2)+...+log(n/2) >=(n/2)log(n/2) >=(n/2)logn-n/2 =O(nlogn) 所以只用到比较的排序算法最低时间复杂度是O(nlogn)。