近来闲的无事，把排序算法拿来撸了撸，我的先声明哦，没学过算法和数据结构的程序员，代码和结论看看就好，当真你就输了，还有就是很多的算法都是有优化方案的，性能能得到很大的改进，所以看不顺眼的可以贴出你的代码啊，哈哈

一、冒泡是渣，不用也罢

  冒泡排序就是不断在剩余元素中选择最大（或最小）的数，并将其移到末尾（或开头），算法的逻辑清晰，实现也比较简单，更容易理解，所以性能不怎样，毕竟"容易理解的算法，性能都不怎么样"哈哈

冒泡排序图例

/**
 * 冒泡排序
 * <p>* 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置</p>
 * <p>* 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数</p>
 * <p>* 针对所有的元素重复以上的步骤，除了最后一个</p>
 * <p>* 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较</p>
 * @param args
 */
public static int[] bubbleSorting(int[] args){
    int len = args.length;
    for (int i = 0; i < len-1; i++) {
        for (int j = 0; j < len-1-i; j++) {
            if(args[j]>args[j+1]){ 
                int tmp=args[j];
                args[j]=args[j+1];
                args[j+1]=tmp;
            }
        }
    }
    return args;
}

二、还是渣的简单选择排序

简单来说其思想就是不断的在剩余元素中寻找最小（或最大）并将其与剩余元素中最左（或最右）
交换位置

简单选择排序图例

/**
 * 选择排序
 * <p>* 剩余元素中查找最小的数，并将其和剩余元素中第一个数交换位置</p>
 * <p>* 在新的剩余元素中重复上面的操作</p>
 * @param args
 * @return
 */
public static int[] selectionSort(int[] args){
    int len = args.length;
    for(int i=0;i<len-1;i++){
        int minIndex=i;
        for (int j = i+1; j < len; j++) {
            if(args[minIndex]>args[j]){
                minIndex=j;
            }
        }
        int tmp=args[i];
        args[i]=args[minIndex];
        args[minIndex]=tmp;
    }
    return args;
}

三、插入法，估计是我实现的很渣，所以性能还是渣

  插入法又叫扑克排序法，将还未排序的元素，在已排序中寻找相应（大于左边，小于右边或者相反）的位置并插入的办法。插入排序不适合对于数据量比较大的排序应用，但数据量很小的时候性能还是非常不错的，许多实现都将插入排序当做快速排序的补充，用于少量数据。由于插入法是在有序列表寻找相应位置，所以很多实现优化还将二分查找算法引入，改良为二分插入排序

简单插入排序图例

/**
 * 插入法 扑克牌排序
 * <p>从左往右，依次取出元素与左边元素对比，找到左边小于自己右边大于自己的位置插入</p>
 */
public static int[] insertionSort(int[] args){
    int len = args.length;
    for (int i = 0; i < len; i++) {
        for (int j = i; j > 0; j--) {
            if(args[j]<args[j-1]){
                int tmp=args[j];
                args[j]=args[j-1];
                args[j-1]=tmp;
            }
        }
    }
    return args;
}

四、插入法改进之希尔排序法（递减增量排序），百万之下，性能啪啪啪

  希尔排序是插入的改进，它又叫做递减增量排序，希尔排序将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，这样做可以大大的减少比较和交换的次数，增加效率。

希尔排序图例

public static int[] shellSort(int[] args){
    int len=args.length;
    for(int gap=len/2;gap>0;gap=gap/2){
        for(int i=gap;i<len;i++){
            int j = i;
            while(j-gap>=0 && args[j]<args[j-gap]){
                int tmp=args[j];
                args[j]=args[j-gap];
                args[j-gap]=tmp;
                j-=gap;
            }
        }
    }
    return args;
}

  上面的代码有点不好理解，网上找的，每次循环完了是间隔折半，其实只是将部分的比较交换操作转移到了while里，比如当间隔为2的时候，第六个数会与第四个、第二个、第零个数比较，不过我发现其实有很多重复比较，比如间隔为4的时候第六个数也会与第二个数比较。简单测试发现效率还可以就没在需要改进之法了，我有自己写了个容易理解的，简单测试过没问题

/**
 * 希尔算法（递减增量排序）
 * <p>设置初始间隔，从左往右比较间隔的两个的数据，满足条件的交换</p>
 * <p>缩小间隔重复上面步奏</p>
 * <p>初始间隔长度直接影响排序性能</p>
 * @param args
 * @return
 */
public static int[] shellSort(int[] args){
    int len=args.length;
    for(int gap=len/2;gap>0;gap--){
        for(int i=gap;i<len;i++){
            if(i-gap>=0 && args[i]<args[i-gap]){
                int tmp=args[i];
                args[i]=args[i-gap];
                args[i-gap]=tmp;
            }
        }
    }
    return args;
}

  两种方法本质是一样得，因为他们交换的方式和次数都是一样的，不过我测试发现，当数据小于50万的时候，数据越小，第二种实现性能优于第一种，但是当大于50万的时候，第二性能弱于第一种，差距在百分之几到百分之十几之间，当然我只测试到了上亿的数据，后面什么情况不得而知，我猜测是因为第二种多了无效的循环，在数据量极大的时候会降低性能

五、表现良好的归并排序

  我是看了别人描述的原理后就去自己实现了，结果拿来和别人的一对比，我艹，居然性能差距不是一点点，非要问差距多少，30%.....，果然我还是把别人的实现拿过来最合适，哈哈,下面是我挑选的一个性能比较好的写法

归并排序图例

/**
 * 
 * @param arr
 */
public static void mergeSort2(int[] arr) {
    mergeSort(arr, new int[arr.length], 0, arr.length - 1);
 }

private static void mergeSort(int[] arr, int[] temp, int left, int right) {
    if (left < right) {
        int center = (left + right) / 2;
        mergeSort(arr, temp, left, center); // 左边
        mergeSort(arr, temp, center + 1, right); // 右边
        merge(arr, temp, left, center + 1, right); // 合并两个有序
    }
 }

/**
 * 将两个有序表归并成一个有序表
 *
 * @param arr
 * @param temp     临时数组
 * @param leftPos  左边开始下标
 * @param rightPos 右边开始下标
 * @param rightEnd 右边结束下标
 */
private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) {
    int leftEnd = rightPos - 1; // 左边结束下标
    int tempPos = leftPos; // 从左边开始算
    int numEle = rightEnd - leftPos + 1; // 元素个数
    while (leftPos <= leftEnd && rightPos <= rightEnd) {
        if (arr[leftPos] <= arr[rightPos]){
            temp[tempPos++] = arr[leftPos++];
        }else{
            temp[tempPos++] = arr[rightPos++];
        }
    }
    while (leftPos <= leftEnd) {  // 左边如果有剩余
        temp[tempPos++] = arr[leftPos++];
    }
    while (rightPos <= rightEnd) { // 右边如果有剩余
        temp[tempPos++] = arr[rightPos++];
    }
    // 将temp复制到arr
    for (int i = 0; i < numEle; i++) {
        arr[rightEnd] = temp[rightEnd];
        rightEnd--;
    }
}
    

  归并排序的主要原理就是，将元素集折半成两个子集，在递归这两个子集，不断重复折半，最后折成一个元素，最后将每个递归内的子集有序合并（每个子集在返回回来的时候就已经有序了），估计没有解释清楚，文章末尾我会贴出我查找资料的链接，可以过去了解，哈哈

六、快速排序

  快排是非稳定排序算法，在数据量小的时候性能并不好，在接近有序的大数据排序，性能想当的差。Java 的Arrays.sort底层实现主要就是快速排序，当然做了很多优化，比如在数量少的时候使用插入排序法，双轴快排的优化，以及在基准选取上的优化，下面是我实现的一个基础简单快排

快速排序图例

/**
 * 快速排序有几个巧妙的地方
 * <p>1、常用的是选取第一个数为基准，通过对数列两头数据进行比较和移动
 * （比较了左边再比较右边，选取的基准，可以随意被覆盖，所以移动就变成了单向赋值）</p>
 * <p>2、先比较右边，如果大于基准，就会将右下标向左移动一位，右下标数据移动到左边；
 * 在比较左边的数据（其实就是前面右指针指向的数据），小于基准，左下标向右移动，将右下表数据赋值给左下标</p>
 * @param args
 * @param left
 * @param right
 */
private static void quickSort(int[] args,int left, int right){
    if(left>=right){
        return;
    }
    int base=args[left]; //选取第一个为基准
    int i=left;
    int j=right;
    while (i < j) { //每次循环左右指针，必有一个指针发生移动，因为base<=args[j]和base>=args[i]
        if(i < j && base<=args[j]){ //如果大于等于基准，向左移动右指针
            j--;
        }
        args[i]=args[j];  
        if(i < j && base>=args[i]){ //如果小于等于基准，向右移动左指针
            i++;
        }
        args[j]=args[i];
    }
    args[i]=base; //回写基准
    quickSort(args, left,i-1);
    quickSort(args, i+1,right);
 }
    
/**
 * 快速排序
 * <p>从数列中挑出一个元素，称为 “基准”（pivot)</p>
 * <p>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 * 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作</p>
 * <p>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序</p>
 * 
 * @param args
 */
public static void quickSort(int[] args){
    quickSort(args,0,args.length-1);
}

七、堆排序

  堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法

堆的定义：

   n个元素的序列{k1，k2，…,kn}当且仅当满足下列关系之一时，称之为堆。

   情形1：ki <= k2i 且ki <= k2i+1 （最小化堆或小顶堆）

   情形2：ki >= k2i 且ki >= k2i+1 （最大化堆或大顶堆）

   其中i=1,2,…,n/2向下取整;

堆的存储

  一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2i+1和2i+2。

小顶堆存储示例图

堆排序图例

  堆排序还是比较好理解，最大堆在使用数组实现的时候是满足args[i]>=args[2i+1]和args[i]>=args[2i+2]（i是数组下标），

/**
 * 构建最大堆
 * @param args
 * @param right
 * @param base
 */
private static void maxHeap(int[] args,int right,int base){
    int root=base;
    int tmp=args[base];
    int maxIndex=base*2+1;        
    while (true) {
        if(maxIndex>right){
            break;
        }
        if (maxIndex < right && args[maxIndex] < args[maxIndex+1]){
            maxIndex++;
        }
        if(args[maxIndex]<=tmp){
            break;
        }            
        args[root]=args[maxIndex];
        args[maxIndex]=tmp;
        root=maxIndex;
        maxIndex=maxIndex*2+1;
    }
}
    
 /**
 * 堆排序其实就是不断构建最大堆（或最小堆）的过程，满足条件树根大于树子（最小堆是树根小于树子）
 * <p>构建最大堆，满足所有根大于子,需要注意的是要从最后一个元素开始构建，并且每次节点元素交换时都要继续检查其子，以保持最大堆特性</p>
 * <p>由于最大堆的第一个数是最大的，所以将第一个数移动到数组最后，下次最大堆构建最后一个不参与</p>
 * <p>重复上面步奏就会得到一个正序的数组</p>
 * <p>构建过一次的最大堆，交换了第一个和最后一个元素后，其实只有少部分是不满足最大堆特性的，这点可以优化性能</p>
 * @param args
 */
public static void heapSort(int[] args){
    int len=args.length;
    for (int i = len / 2 - 1; i >= 0; i--){  //构建初始最大堆
        maxHeap(args, len-1, i);
    }
    for (int i = (len-1); i > 0; i--) {
        int tmp=args[0];
        args[0]=args[i];
        args[i]=tmp;
        maxHeap(args, i-1 , 0);
    } 
}

  我对上面的算法做过简单的测试，使用1000000来产生随机数，性能表现情况如下表：

推荐阅读：
比较牛的一个博主，一堆算法和数据结构，而且够用心够仔细，膜拜大神，链接如下
http://www.cnblogs.com/skywang12345/p/3603935.html
简书一个作者关于Java 快速排数源码DualPivotQuickSort 的解读，提到的TimSort算法和三路与双轴快排的关系都是值得了解和阅读的
//www.greatytc.com/p/6d26d525bb96
http://rerun.me/2013/06/13/quicksorting-3-way-and-dual-pivot/