排序算法 - 简书

选择排序

含义：从第一个值往后开始查找，每次找到最小的值然后与第一个值进行交换，遍历整个数据达到有序。代码实现如下：

public static void sort(Comparable[] a)
{
    //首先获取长度
    N = a.length();
    for(int i=0;i<N;i++) {
        min = i;//假设这是最小的下标
        for(int j=i+1;j<N;j++) {
            if(less(a[j],a[min])) {
                min = j;//a[j]对应的值比a[min]小进行交换
            }
        }
        exch(a,min,j);//一次内循环结束交换
    }
}

插入排序

含义：像整理扑克牌一样，每次一张一张的把牌移入到有序的牌组中，只是代码中因为有空间需求，所以需要进行位置交换腾换空间，代码如下：

public static void sort(Comparable[] a) {
    int N = a.length();//获取数组长度
    for(int i=1;i<N;i++) {
        //有序数组不能为空，所以i从1开始
        for (int j=i;j>0 && less(a[j],a[j-1];j--) {
            //二重循环是从大检索到最小依次比较排序使得有序排列
            exch(a,j,j-1);//交换
        }
    }
}

希尔排序

含义：插入排序的升级版，步长不在为1，而是设定为一个h可以加快往后排列的小数回归到前面的正常位置中，比起插入排序效率更高

public static void sort(Comparable[] a) {
    N = a.length();
    //或者这样设定步长（算法书上的）
    # int h=1;
    # while(h < N/3) {
    #   h = 3*h + 1;   
    #}
    #下面的更改为h = h/3也可，性能不一样
    int h = N/2;//设定步长
    while(h>=1) {
        for(int i=h;i<N;i++) {
            for(int j=i;j>h && less(a[j],a[j-h);j-=h) {
                exch(a,j,j-h);
            }
        }
        h = h/2;
    }
}

归并排序：

时间复杂度是NlgN,命题对于长度为N的任意数组，自顶向下的归并排序需要1/2
原地归并方法：需要一个辅助数组，将原数组copy到辅助数组中，然后将辅助数组的数据根据lo，mid,hi分为两组依次归并到原数组中，具体实现代码如下,关于值的设定for循环中的语句含义还是画一个图看：

private static void Comparable[] aux;//设定归并所需的辅助数组
public static void merge(Comparable[] a, int lo, int mid, int hi) {
    int i = lo,j=mid+1;
    for (int k=lo;k<=hi;k++) {
        aux[k] = a[k];
    }
    //进行归并排序
    for (int k=lo;k<=hi;k++) {
        if(i>mid) {
            a[k] = aux[j++];
        }
        else if (j>hi) {
            a[k] = aux[i++];
        }
        else if (less(aux[j],aux[i])) {
            a[k] = aux[j++];
        }
        else {
            a[k] = aux[i++];
        }
    }
}

public static void sort(Comparable[] sort) {
    aux = new Comparable[a.length];
    sort(a,0,a.length - 1);
}

public static void sort(Comparable[] a,int lo,int hi) {
    if (hi<=lo) return;
    int mid = (lo + hi)/2;
    sort(a,lo,mid);
    sort(a,mid+1,hi);
    merge(a,lo,mid,hi);
}

/**
 * 自顶向上的归并排序
 *多次遍历整个数组，根据子数组大小进行两两归并
 * 类似于1+1=2,2+2=4一直到大于N结束为止
 * lo , mid = lo+sz -1, hi = lo +2*sz -1
 */
public static void sortUp(Comparable[] a) {
    int N = a.length;
    aux = new Comparable[a.length];
    for (int sz=1; sz<N; sz = sz + sz) {
        //lo < N-sz 保证mid = lo + sz <N,即是说[mid, hi]还存在着数据，这个数据只是可能没有sz这么大
        for (int lo=0; lo < N-sz; lo += sz+sz) {
            //进行逐序归并,利用Math.max防止最大值索引直接越界
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
        }
    }
}

快速排序

含义：采用的是分治的排序算法。快排和归并排序是互补的算法，归并需要额外的辅助数组，快速排序不需要。实现的是两个子数组有序时整个数组也就有序了。举例来说如下：首先从数组中选定一个值，假如是第一个值，然后遍历整个数组，将比这个值小的数据放在这个数的左边，比这个大的放在数据右边，从两头往中间缩进，所以需要的时间会小很多，然后再进行递归遍历实现最后以1位间隔的数据段，自然整个数组也就有序了。
代码如下：

public static void sort(Comparable[] a) {
int N = a.length;
sort(a, 0, N-1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi < lo) return;//递归结束条件返回
int j = partition(a, lo, hi);
sort(a, lo, j-1);//左边数组快排
sort(a, j+1, hi);//右边数组快排
}
//以下这个函数是实现快排的重要代码
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1;
while (true) {
    while (less(a[i++],a[lo])) {
    //控制越界
        if (i == hi) {
            break;
        }
    }
    while (less(a[lo],a[j--])) {
        if (j == lo) {
            break;
        }
    }
    if (i >= j) break;
    exch(a, i, j);
}
exch(a, lo, j);
return j;
}

//快排实现代码2感觉比上面那一种简单
private static int partitionBack(Comparable[] a, int lo, int hi) {
        Comparable key = a[lo];
        while(lo < hi) {
            while (lo < hi && less(key, a[hi])) hi--;
            a[lo] = a[hi];
            while (lo < hi && less(a[lo], key)) lo++;
            a[hi] = a[lo];
        }
        a[hi] = key;
        return hi;
    }

堆排序

含义：采用堆的形式（大根堆：父节点都比子节点大，小根堆：父节点都比子节点小），首先将一堆数据排列成为大根堆，然后从根节点取出最大值，一次放入到队列的最后，就可以变成一个有序的从小到大排序的数据，其时间复杂度为NlgN。
父节点和子节点满足以下关系：父节点序号*2+1 或者父节点序号*2 + 2 = 子节点序号，父节点序号 = 子节点序号-1/2
算法如下：

private static void sink(Comparable[] a, int k, int N) {
    //下沉算法
    while (2*k+1 < N) {
        int j = 2*k+1;//找寻子节点
        //比较两个子节点找出最大的
        if (j<N && less(a[j], a[j+1])) {
            j++;
        }
        //比较父节点和最大的子节点
        if(!less(a[k], a[j])) {
            //满足堆特性，结束循环
            break;
        }
        //进行交换
        exch(a,k,j);
        //继续下层遍历
        k = j;
    }
}

//实现堆有序的过程
public static void sort(Comparable[] a) {
    int N = a.length - 1;//数组和实际下标有一个1的差距
    //实现对有序
    for (int k = N/2; k>=1; k--) {
        sink(a, k, N);
    }
    //进行堆排序，每次将根节点挪到后面在进行堆排序循环
    while (N >1 ) {
        exch(a,1,N--);
        sink(a,1,N);
    }
}

冒泡排序

含义：每一轮从前往后的遍历，较大数据后排，就像鱼吐泡泡一样越来越大，轮次结束后数组整体有序
源代码如下：

package com.zhou.sort;

import com.zhou.prepare.StdOut;

/**
 * Created by 强 on 2018/11/21.
 * 冒泡排序：每次进行两个数字的比较，较大者放到后面，从前往后依次进行直到最后一个是本轮次的最大的数，然后继续下一轮直到整个数组有序
 */
public class Bubble {
    public static void main(String[] args) {
        Integer[] a = {5, 3, 2, 10, 1, 15, 4,90};
        bubble_sort(a);
        show(a);
        System.out.println(isSorted(a));
    }

    private static void sort(Comparable[] a) {
        //外层循环控制轮次
        for (int i = 0; i < a.length; i++) {
            //内存循环控制比较
            for (int j = 0; j < a.length - i - 1; j++) {
                if (less(a[j+1], a[j])) exch(a, j, j+1);
            }
        }
    }

    /**
     * 将双层for循环进化为一个while循环加一个for循环，此时若数组处于有序状态可以大大减小排序时间
     * 比如数组本身有序，那么时间复杂度进化为O(n),逆序状态下与原始冒泡排序等同，平均复杂度和逆序等同
     * @param a
     */
    private static void bubble_sort(Comparable[] a) {
        int pos = a.length - 1;
        while (pos != 0) {
            int bound = pos;
            pos = 0;//用于标记是否有交换记录，若有，则记录"下一趟要处理的最后一个位置"
            for (int j = 0; j < bound; j++) {
                if (less(a[j+1], a[j])) {
                    exch(a, j, j+1);
                    pos = j;
                }
            }
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(Comparable[] a) {
        for (int i=0; i<a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

    public static boolean isSorted(Comparable[] a) {
        for (int i=1; i<a.length; i++) {
            if (less(a[i], a[i-1])) {
                return false;
            }
        }
        return true;
    }
}

基数排序(桶排序)

含义：从最基本的认知出发的排序，两个数比较大小首先是看位数是否相同，如果不同那么位数多的肯定比位数少的大，位数相同则逐个位置进行比较大小进行排序。这个每一位比较就被称为基数（个位/十位/百位等），这个排序过程又可以分为MSD（高位优先排序，从左到右）和LSD（低位优先排序，从右到左）和字符串的排序倒是有异曲同工之处。
此处着眼于LSD，具体实现的过程如下：
首先声明10个桶，每个桶代表的数字0-9，也就是对应的基数，然后对于每一个数字按照从低位优先（个位开始）进行取余，加如对应的位数字为5，那么就放入数字为5的桶中，依次将数组中所有数据都放入桶中。
之后再从桶0开始遍历，将桶中所有数据依次取出（同一个桶中的数据按照先进先出的特性）放入到原数组中
然后将基数扩大十倍（个位变百位，百位变千位，依次类推），重复上述过程直到最后循环结束
举例来说，一组数据5、2、9、7、18、17、52
如下图中所示，按照个位数字大小依次放入桶中，然后再将桶中的数据串起来输出得到排序后的结果2、52、5、7、17、18、9，然后以此顺序进行十位的桶排序
如下图第二张图中所示，重复操作即可得到最后有序的数组完成此次排序的结果
在代码实现过程中用一个二维数组实现，行为10表示10个桶，列表示的是桶中药存储的数据，长度为数组长度，然后声明一个长度为10的一维数组用来表示每个桶中有多少数据

第一次桶排序

第二次桶排序
源代码实现如下所示：

package com.zhou.sort;

/**
 * Created by 强 on 2019/4/6.
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] num = new int[50];
        for (int i=0; i<num.length; i++) {
            num[i] = (int)(Math.random()*1000);
        }
        radixSort(num, 1000);
        System.out.println("the result is order: " + isSorted(num));
        for (int i=0; i<num.length; i++) {
            System.out.print(num[i]+ " ");
        }
    }

    //d表示的是数组中最大位的位数+1位，举例来说加如排序的都是1-99两位数，那么d就是100，如果是1-999那么d就是1000
    private static void radixSort(int[] array, int d) {
        int n = 1;//代表位数对应的数:1、10、100
        int length = array.length;
        int[][] bucket = new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
        int[] order = new int[10];//用于保存每个桶里有多少个数字,一共有10个桶
        while (n<d) {
            for (int num:array) {
                //将数组array每个数字放在相应的桶里
                int digit = (num/n)%10;
                bucket[digit][order[digit]]=num;
                order[digit]++;
            }
            int k=0;//回写到原数组时，原数组下标索引
            for (int i=0; i<10; i++) {
                //将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
                if(order[i]!=0) {
                    //这个桶里有数据，从上到下排序并将数据保存到原数组中
                    for (int j=0; j<order[i]; j++) {
                        array[k] = bucket[i][j];
                        k++;
                    }
                }
                order[i]=0;//将桶里计数器清零，用于下一次位排序
            }
            n*=10;
        }
    }

    private static boolean isSorted(int[] a) {
        for (int i=1; i<a.length; i++) {
            if (a[i]<a[i-1]) {
                return false;
            }
        }
        return true;
    }
}

排序算法总结

所需辅助空间最多：归并排序
所需辅助空间最少：堆排序
平均速度最快：快速排序
不稳定性：快速排序、希尔排序、堆排序（不稳定性指的是相同的两个数在排序前后的相对位置是否改变）
平均时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，快排最好
平均时间复杂度为O(n2)的方法有：直接插入排序、冒泡排序、简单选择排序，其中直接插入排序最好，尤其是对那些关键字近似有序的记录序列
平均时间复杂度为O(n)的只有基数排序

排序算法比较表

排序完整代码链接

https://github.com/zhouwaiqiang/JavaLearning/tree/master/algorithm/src/com/zhou/sort

参考资料

算法4
https://wsgzao.github.io/post/iptables/