　　本文集中汇总冒泡、插入(对半插入)、选择、希尔、堆排序、归并、快速、七种排序算法，收集了网上的示意图、动图进行生动的展示。

由于内容较多，这里只提供了Java代码int类型数组进行举例说明，其他语言或者数据类型请自行转换。

一、排序算法基础知识准备

1. Swap函数的三种实现

　　首先针对排序常用到的数据交换Swap函数，汇总了一下它的三种实现方式：

直接交换法：

/**
 * 数组元素交换 直接交换
 */
public static void Swap1(int[] array,int i,int j){
    int tmp=array[i];
    array[i]=array[j];
    array[j]=tmp;
}

异或交换法：

/**
 * 数组元素交换 异或交换
 */
public static void Swap2(int[] array,int i,int j){
    array[i]^=array[j];
    array[j]^=array[i];
    array[i]^=array[j];
}

加法交换法：

/**
 * 数组元素交换 加法交换
 */
public static void Swap3(int[] array,int i,int j){
    array[i]=array[i]+array[j];
    array[j]=array[i]-array[j];
    array[i]=array[i]-array[j];
}

2. 算法复杂度

排序方式	时间复杂度			空间复杂度	稳定性
排序方式	平均	最好	最坏	平均	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
希尔排序	O(n¹·³)	O(n)	O(n²)	O(1)	不稳定
堆排序	O(n㏒₂n)	O(n㏒₂n)	O(n㏒₂n)	O(n)	稳定
归并排序	O(n㏒₂n)	O(n㏒₂n)	O(n㏒₂n)	O(n)	稳定
快速排序	O(n㏒₂n)	O(n㏒₂n)	O(n²)	O(n㏒₂n)	不稳定

计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
桶排序	O(n+k)	O(n)	O(n²)	O(n+k)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定

3. 相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

二、7大排序算法

排序算法分类

1. 冒泡排序(Bubble Sort)：

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

　　根据冒泡的方向，可以分为前向冒泡和后向冒泡，对于升序排序：前向冒泡指较小的数逐渐浮到数列的前方，后向冒泡指较大的数逐渐后浮。降序排序则反之。

1.1 算法描述

前向冒泡

比较第一个元素与后面一个元素，如果第一个比第二个大，就交换它们两个；
递增第二个索引，继续比较两个索引对应的元素，直到第二个索引到达数列末尾；
递增第一个索引，第二个索引回到第一个索引后面，如果第一个比第二个大，就交换它们两个；
重复2、3步，直到两个元素到达数列末尾截止，此时完成排序。

后向冒泡

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。

1.2 动图演示(后向冒泡)

冒泡排序演示图1

冒泡排序演示图2

1.3 代码实现

/**
 * 冒泡排序 前向冒泡
 * @param array 待排序的数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
public static void BubbleSortForward(int[] array,boolean asc){
    int len=array.length;
    if(asc){
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(array[i]>array[j]){
                    Swap(array,i,j);
                }
            }
        }
    }else{
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(array[i]<array[j]){
                    Swap(array,i,j);
                }
            }
        }
    }
}
/**
 * 冒泡排序 后向冒泡
 * @param array 待排序的数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
public static void BubbleSortBackword(int[] array,boolean asc){
    int len=array.length;
    if(asc){
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-1-i;j++){
                if(array[j]>array[j+1]){
                    Swap(array,j,j+1);
                }
            }
        }
    }else{
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-1-i;j++){
                if(array[j]<array[j+1]){
                    Swap(array,j,j+1);
                }
            }
        }
    }
}

1.4 算法复杂度分析

　　根据冒泡排序的原理，若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；若是倒序，比较次数为 n-1+n-2+…+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n²）。

2 插入排序

1.1 算法描述

　　直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。插入排序示意图

1.2 动图演示

插入排序演示图1
插入排序演示图2

1.3 代码实现

/**
 * 插入排序
 * @param array 待排序的数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
public static void InsertSort(int[] array,boolean asc){
    int len=array.length;
    int tmp;
    int j;
    if(asc){
        for(int i=1;i<len;i++){
            tmp=array[i];
            for(j=i;j>0&&tmp<array[j-1];j--){
                array[j]=array[j-1];
            }
            array[j]=tmp;
        }
    }else{
        for(int i=1;i<len;i++){
            tmp=array[i];
            for(j=i;j>0&&tmp>array[j-1];j--){
                array[j]=array[j-1];
            }
            array[j]=tmp;
        }
    }
}

1.4 算法复杂度分析

　　插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n²)。

3 选择排序

1.1 算法描述

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

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

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

1.2 动图演示

选择排序演示图2

1.3 代码实现

/**
 * 选择排序
 * @param array 待排序的数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
public static void SelectSort(int[] array,boolean asc){
    int len=array.length;
    if(asc){
        //每一轮循环未排序序列中找到最小元素的下标min
        int min;
        for(int i=0;i<len-1;i++){
            min=i;
            for(int j=i+1;j<len;j++){
                if(array[j]<array[min]){
                    min=j;
                }
            }
            if(i!=min){
                //最小元素依次与未排序序列首元素交换(放置于已排序序列末尾)
                Swap(array,i,min);
            }
        }
    }else{
        int max;
        for(int i=0;i<len-1;i++){
            max=i;
            for(int j=i+1;j<len;j++){
                if(array[j]>array[max]){
                    max=j;
                }
            }
            if(i!=min){
                Swap(array,i,min);
            }
        }
    }
}

4 希尔排序

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

1.1 算法描述

　　先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

1.2 动图演示

希尔排序演示图1
希尔排序演示图2

1.3 代码实现

/**
 * 希尔排序 参考:https://www.cnblogs.com/alsf/p/6606287.html
 * @param array 待排序的数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
public static void ShellSort(int[] array,boolean asc){
    int len=array.length;
    int h=1;
    while(h<len/3){
        h=h*3+1;
    }
    int tmp;
    int j;
    if(asc){
        while(h>=1){
            for(int i=h;i<len;i++){
                tmp=array[i];
                for(j=i;j>=h&&tmp<array[j-h];j-=h){
                    array[j]=array[j-h];
                }
                array[j]=tmp;
            }
            h=h/3;
        }
    }else{
        while(h>=1){
            for(int i=h;i<len;i++){
                tmp=array[i];
                for(j=i;j>=h&&tmp>array[j-h];j-=h){
                    array[j]=array[j-h];
                }
                array[j]=tmp;
            }
            h=h/3;
        }
    }
}

1.4 算法分析

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

5 堆排序

1.1 算法描述

堆排序

　　堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(n㏒₂n)，它也是不稳定排序。首先简单了解下堆结构。

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
堆排序示意图
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
堆排序示意图1
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

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

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

堆排序的基本思想及基本步骤

　　堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了.

步骤一构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

　　a.假设给定无序序列结构如下
堆排序示意图2
　　b.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

堆排序示意图3
　　c.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
堆排序示意图4
　　d.这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
堆排序示意图5
　　此时，我们就将一个无需序列构造成了一个大顶堆。
　　步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

　　a.将堆顶元素9和末尾元素4进行交换
堆排序示意图6
　　b.重新调整结构，使其继续满足堆定义
堆排序示意图7
　　c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
堆排序示意图8
　　后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
堆排序示意图9

再简单总结下堆排序的基本思路：

　　a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
　　b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。 　　

1.2 动图演示

堆排序演示图1
堆排序演示图2

1.3 代码实现

/**
 * 堆排序函数 参考:https://www.cnblogs.com/chengxiao/p/6129630.html
 * @param array 待排序的数组
 * @param asc 是否为升序排序模式 true:升序 false:降序
 */
public static void HeapSort(int[] array,boolean asc){
    int len=array.length;
    for(int i=len/2-1;i>=0;i--){
        AdjustHeap(array,i,len,asc);
    }
    for(int i=len-1;i>0;i--){
        Swap(array,0,i);//将堆顶元素与最后一个元素交换
        AdjustHeap(array,0,i,asc);//重新调整余下len-1个元素
    }
}

/**
 * 堆排序 堆调整函数
 * @param array 堆数组
 * @param i 待调整的节点头元素索引
 * @param len 待调整的数组长度
 * @param asc 是否为升序排序模式 true:升序 false:降序
 */
private static void AdjustHeap(int[] array,int i,int len,boolean asc){
    int tmp=array[i];//先取出当前元素i
    if(asc){//升序采用大顶堆
        for(int k=2*i+1;k<len;k=k*2+1){
            if(k+1<len&&array[k]<array[k+1]){//如果左子节点小于右子节点，k指向右子节点
                k++;
            }
            if(tmp<array[k]){//如果跟节点小于子节点
                array[i]=array[k];//根节点赋值为较大子节点
                i=k;//跟节点指向右子节点 迭代
            }else{
                break;
            }
        }
    }else{//降序采用小顶堆
        for(int k=2*i+1;k<len;k=k*2+1){
            if(k+1<len&&array[k]>array[k+1]){//如果左子节点大于右子节点，k指向右子节点
                k++;
            }
            if(tmp>array[k]){//如果跟节点大于子节点
                array[i]=array[k];//根节点赋值为较小子节点
                i=k;//跟节点指向右子节点 迭代
            }else{
                break;
            }
        }
    }
    array[i]=tmp;//右子节点赋值为跟节点 完成调整
}

1.4 算法复杂度分析

　　堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[㏒₂(n-1),㏒₂(n-2)…1]逐步递减，近似为n㏒₂n。所以堆排序时间复杂度一般认为就是O(n㏒₂n)级。

6 归并排序

1.1 算法描述

　　归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

分而治之

　　可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

合并相邻有序子序列

　　再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
归并排序示意图1
归并排序示意图2

1.2 动图演示

归并排序演示图1
归并排序演示图2

1.3 代码实现

/**
 * 归并排序 参考:https://www.cnblogs.com/chengxiao/p/6194356.html
 * @param array 待排序的数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
public static void MergeSort(int[] array,boolean asc){
    int len=array.length;
    int[] tmp=new int[len];
    MergeSortDivide(array,0,len-1,tmp,asc);
}

/**
 * 归并排序(分治)——分
 * @param array 待排序的数组
 * @param l     左
 * @param r     右
 * @param tmp   与array相同大小的临时数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
private static void MergeSortDivide(int[] array,int l,int r,int[] tmp,boolean asc){
    if(l<r){
        //定义中值值将序列从中间分割
        int mid=(l+r)/2;
        //对中值两侧的子序列进行迭代分割
        MergeSortDivide(array,l,mid,tmp,asc);
        MergeSortDivide(array,mid+1,r,tmp,asc);
        //按需合并两个子序列
        MergeSortMerge(array,l,mid,r,tmp,asc);
    }
}

/**
 * 归并排序(分治)——治(合)
 * @param array 待排序的数组
 * @param l     左
 * @param mid   中
 * @param r     右
 * @param tmp   与array相同大小的临时数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
private static void MergeSortMerge(int[] array,int l,int mid,int r,int[] tmp,boolean asc){
    int i=l;
    int j=mid+1;
    int k=0;
    if(asc){
        while(i<=mid&&j<=r){
            //依次选择左右两个子序列中较小值填充到新序列
            if(array[i]<array[j]){
                tmp[k++]=array[i++];
            }else{
                tmp[k++]=array[j++];
            }
        }
    }else{
        while(i<=mid&&j<=r){
            if(array[i]>array[j]){
                tmp[k++]=array[i++];
            }else{
                tmp[k++]=array[j++];
            }
        }
    }

    //左序列未遍历完，依次填充到新序列末尾
    while(i<=mid){
        tmp[k++]=array[i++];
    }
    //右序列未遍历完，依次填充到新序列末尾
    while(j<=r){
        tmp[k++]=array[j++];
    }
    k=0;
    //新序列拷贝回原始序列
    while(l<=r){
        array[l++]=tmp[k++];
    }
}

1.4 算法复杂度分析

　　n个元素都要被遍历一遍以保证其被放到新数组, 需要将待排序序列中的所有记录扫描一遍，所以O(n)。由完全二叉树可知，整个归并排序需要㏒₂n次，所以最好=最坏=平均=O(n㏒₂n)。由于归并排序需要与原始记录序列同样数量的存储空间存放归并结果以及递归时㏒₂n的栈空间，所以空间复杂度O(n+㏒₂n)。

　　归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|㏒₂n|。总的平均时间复杂度为O(n㏒₂n)。而且，归并排序的最好，最坏，平均时间复杂度均为O(n㏒₂n)。

7 快速排序

　　快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

1.1 算法描述

三数取中

　　在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。
快速排序示意图1

根据枢纽值进行分割

1.2 动图演示

快速排序演示图1
快速排序演示图2

1.3 代码实现

/**
 * 快速排序
 * @param array 待排序的数组
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
public static void QuickSort(int[] array,boolean asc){
    int len=array.length;
    QuickSort(array,0,len-1,asc);
}

/**
 * 快速排序——递归函数
 * @param array 待排序的数组
 * @param l     左
 * @param r     右
 * @param asc   是否为升序排序模式 true:升序 false:降序
 */
private static void QuickSort(int[] array,int l,int r,boolean asc){
    if(l>=r){
        return;
    }
    int j=QuickSortPartion(array,l,r,asc);
    QuickSort(array,l,j-1,asc);
    QuickSort(array,j+1,r,asc);
}

/**
 * 快速排序——分区操作
 * @param array 待排序的数组
 * @param l     左
 * @param r     右
 * @param asc   是否为升序排序模式 true:升序 false:降序
 * @return
 */
private static int QuickSortPartion(int[] array,int l,int r,boolean asc){
    int i=l,j=r+1;
    int tmp=array[l];
    if(asc){
        while(true){
            while(array[++i]<tmp){
                if(i==r){
                    break;
                }
            }
            while(tmp<array[--j]){
                if(j==l){
                    break;
                }
            }
            if(i>=j){
                break;
            }
            Swap(array,i,j);
        }
    }else{
        while(true){
            while(array[++i]>tmp){
                if(i==r){
                    break;
                }
            }
            while(tmp>array[--j]){
                if(j==l){
                    break;
                }
            }
            if(i>=j){
                break;
            }
            Swap(array,i,j);
        }
    }

    Swap(array,l,j);
    return j;
}

1.4 算法复杂度分析

　　快速排序是一种交换类的排序，它同样是分治法的经典体现。在一趟排序中将待排序的序列分割成两组，其中一部分记录的关键字均小于另一部分。然后分别对这两组继续进行排序，以使整个序列有序。在分割的过程中，枢纽值的选择至关重要，本文采取了三位取中法，可以很大程度上避免分组”一边倒”的情况。快速排序平均时间复杂度也为O(n㏒₂n)级。

三、其他排序算法

1 计数排序（Counting Sort）

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

1.1 算法描述

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

1.2 动图演示

计数排序演示图1

1.3 代码实现

(略)

1.4 算法复杂度分析

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

2 桶排序

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

1.1 算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。　　
1.2 图片演示

1.3 代码实现

(略)

1.4 算法复杂度分析

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

3 基数排序

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

1.1 算法描述

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；　　
1.2 动图演示

1.3 代码实现

(略)

1.4 算法复杂度分析

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

　　基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。　　

四、稳定排序和不稳定排序

　　排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。

　　其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些（个人感觉，没有证实）。

　　回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。

(1)冒泡排序

　　冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

(2)选择排序

　　选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

(3)插入排序

　　插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

(4)快速排序

　　快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j，交换a[i]和a[j],重复上面的过程，直到i > j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

(5)归并排序

　　归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

(6)基数排序

　　基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

(7)希尔排序(shell)

　　希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

(8)堆排序

　　我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， … 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

　　综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序是稳定的排序算法。

五、参考

常见排序算法总结与实现(冒泡、插入、选择、希尔、堆排序、归并、快排):https://www.cnblogs.com/alsf/p/6606287.html

十大经典排序算法（动图演示）:https://www.cnblogs.com/onepixel/articles/7674659.html

图解排序算法(一)之3种简单排序(选择，冒泡，直接插入)
:http://www.cnblogs.com/chengxiao/p/6103002.html

图解排序算法(三)之堆排序:http://www.cnblogs.com/chengxiao/p/6129630.html

图解排序算法(四)之归并排序:https://www.cnblogs.com/chengxiao/p/6194356.html

图解排序算法(五)之快速排序——三数取中法:http://www.cnblogs.com/chengxiao/p/6262208.html

一、排序算法基础知识准备

1. Swap函数的三种实现

2. 算法复杂度

3. 相关概念

二、7大排序算法

1. 冒泡排序(Bubble Sort)：

1.1 算法描述

1.2 动图演示(后向冒泡)

1.3 代码实现

1.4 算法复杂度分析

2 插入排序

1.1 算法描述

1.2 动图演示

1.3 代码实现

1.4 算法复杂度分析

3 选择排序

1.1 算法描述

1.2 动图演示

1.3 代码实现

4 希尔排序

1.1 算法描述

1.2 动图演示

1.3 代码实现

1.4 算法分析

5 堆排序

1.1 算法描述

1.2 动图演示

1.3 代码实现

1.4 算法复杂度分析

6 归并排序

1.1 算法描述

1.2 动图演示

1.3 代码实现

1.4 算法复杂度分析

7 快速排序

1.1 算法描述

1.2 动图演示

1.3 代码实现

1.4 算法复杂度分析

三、其他排序算法

1 计数排序（Counting Sort）

1.1 算法描述

1.2 动图演示

1.3 代码实现

1.4 算法复杂度分析

2 桶排序

1.1 算法描述

1.2 图片演示

1.3 代码实现

1.4 算法复杂度分析

3 基数排序

1.1 算法描述

1.2 动图演示

1.3 代码实现

1.4 算法复杂度分析

四、稳定排序和不稳定排序

(1)冒泡排序

(2)选择排序

(3)插入排序

(4)快速排序

(5)归并排序

(6)基数排序

(7)希尔排序(shell)

(8)堆排序

五、参考

1.2 图片演示　　

1.2 动图演示　　