排序算法与代码实现

本文源自https://xuzhongcn.github.io/my/02/Sort.html

1、意义

排序算法在商业算法、信息搜索、运筹学、事件驱动模拟、数值计算、组合搜索等等领域都有着广泛的应用，不仅如此，定序序列往往是其他算法的前提条件，例如二分查找等。

2、概述

排序算法基本可以分为两大类：

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

3、言归正传

此文以最基本冒泡排序、选择排序作为开始；之后讨论插入排序、希尔排序、归并排序；在之后我们讨论快速排序分析JDK1.7以后的Arrays.sort中对于快速排序的优化，三向切分的快速排序与双轴快速排序。最后我们来看基于优先队列数据结构的堆排序，以及非基于比较的排序：计数排序、桶排序、基数排序。

4、算法理论与代码实现

4-1、冒泡排序

 
​x
    //1、冒泡排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[]= {5,6,8,7,2,9,1,3,4};
        
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length-i-1; j++) {
                if(a[j]>a[j+1]) {
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

4-2、选择排序

 
    //2、选择排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a= {5,6,8,7,2,9,1,3,4};
        for (int i = 0; i < a.length; i++) {
            //记录最小的元素的脚标
            //最开始，我们假定第一个元素最小
            int min=i;
            for (int j = i+1; j < a.length; j++) {
                if(a[min]>a[j]) {
                    //如果a[j]更小。
                    //我们把min更新为j。
                    //这样min就是这时之前所有比较过的元素的最小值的脚标。
                    min=j;
                }
            }
            //把这一次的最小值放到最前面。
            int temp=a[min];
            a[min]=a[i];
            a[i]=temp;
        }
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

4-3、插入排序

 
x
    //3、插入排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a= {5,6,8,7,2,9,1,3,4};
        for (int i = 0; i < a.length; i++) {
            for(int j=i;j>0&&a[j-1]>a[j];j--) {
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

4-4、希尔排序

 
xxxxxxxxxx
    //4、希尔排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a= {5,6,8,7,2,9,1,3,4};
        int N=a.length;
        int h=1;
        while(h<N/3) {
            //h的取值为：1,4,13,40,121,364,1093...
            h=3*h+1;
        }
        while(h>=1) {
            //将数组变为“h有序”
            for (int i = h; i <N; i++) {
                for (int j = i; j>=h&&a[j]<a[j-h]; j-=h) {
                    int temp=a[j];
                    a[j]=a[j-h];
                    a[j-h]=temp;
                }
            }
            h=h/3;
        }
        
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        
    }

4-5、归并排序

 
xxxxxxxxxx
    //5、归并排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a= {5,6,8,7,2,9,1,3,4};
        aux=new int [a.length];
        sort(a,0,a.length-1);
        
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        
    }
    //临时数组，借用空间
    private static int [] aux;
    //排序的算法
    private static void sort(int [] a,int lo,int hi) {
        if(hi<=lo) {
            return ;
        }
        int mid=lo+(hi-lo)/2;
        //对左边排序
        sort(a,lo,mid);
        //对右边排序
        sort(a,mid+1,hi);
        //合并两个部分
        merge(a,lo,mid,hi);
    }
    
    //把mid左边和右边归并成一个数组。
    private static void merge(int[] a,int lo,int mid,int hi) {
        int i=lo;
        int 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(aux[j]<aux[i]) {
                //如果两边都有元素，且右边的小于左边的
                //我们认为下一个元素应该是用右边的元素
                a[k]=aux[j++];
            }else {
                //如果两边都有元素，且右边的不小于左边的
                //我们认为下一个元素应该是用左边的元素
                a[k]=aux[i++];
            }
        }
    }

4-6、基本快速排序

因为时间复杂度的问题，其实冒泡排序与选择排序在实际应用中并不多，因为它们是O(n^2)。快速排序时间复杂度要低，它是O(nlgn)。明显要快很多。

快速排序时间复杂度求解：

代码实现：

 
x
    //6、快速排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a= {5,6,8,7,2,9,1,3,4};
        sort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    //基本快速排序
    private static void sort(int [] a,int start,int end) {
        if(start>=end) {
            return ;
        }
        int n=start;
        int m=end;
        for (;start<end;) {
            for (;start<end; end--) {
                if(a[end]<a[start]) {
                    int temp=a[end];
                    a[end]=a[start];
                    a[start]=temp;
                    start++;
                    break;
                }
            }
            for (; start<end; start++) {
                if(a[start]>a[end]) {
                    int temp=a[start];
                    a[start]=a[end];
                    a[end]=temp;
                    end--;
                    break;
                }
            }
        }
        sort(a,n,start-1);
        sort(a,start+1,m);
    }

4-7、三向切分的快速排序

与基本的快速排序不同，我们改进快速排序，为了使得当“数组中有相同元素”时，不至于浪费比较次数。于是，我们向把数组分成三个部分，以数组中一个元素flag为标准，数组被拆分成{<flag，=flag，>flag}，也就是小于，等于，大于三个部分。

在JDK1.7类java.util.DualPivotQuicksort.java中：

我们可以看到，JDK中，以pivot为基本值，对数组进行比较，企图把数组拆分成三个部分，这里左边分界点为less，当k和great相遇之时，这一次快速排序拆分数组完成，也就是说less左边的都比pivot小，great右边的都比pivot大，于是下一次只需要：

那么基于这种思想，我们可以写出三向切分的快速排序：

 
xxxxxxxxxx
    //三向切分的快速排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a= {5,6,8,7,2,9,1,3,4};
        sort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    private static void sort(int [] a,int start,int end) {
        if(end<=start) {
            return ;
        }
        int left=start;
        int right=end;
        int center=start+1;
        while(center<=right) {
            if(a[center]<a[left]) {
                int temp=a[center];
                a[center]=a[left];
                a[left]=temp;
                left++;
                center++;
            }else if(a[center]>a[left]) {
                int temp=a[center];
                a[center]=a[right];
                a[right]=temp;
                right--;
            }else {
                center++;
            }
        }
        sort(a,start,left-1);
        sort(a,right+1,end);
    }

4-8、双轴快速排序

上面我们看到，快速排序一直都是以一个pivot值，来分裂数组的，双轴快速排序采用两个值，pivot1和pivot2，把数组拆分成三个部分{<pivot1，>=pivot1&&<=pivot2，>pivot2}。

在JDK1.7类java.util.DualPivotQuicksort.java中：

我们看到果真这般如此。less左边的都比pivot1小，great右边的都比pivot2大，当k与great相遇时，less与great之间的值就是介于[pivot1,pivot2]区间内部的值。

双轴快速排序代码实现：

 
xxxxxxxxxx
    //双轴快速排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a= {5,6,8,7,2,9,1,3,4};
        sort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    private static void sort(int [] a,int start,int end) {
        if(start >= end){
            return;
        }
        if(a[start] > a[end]){
            //保证pivot1 小于等于pivot2
            int temp=a[start];
            a[start]=a[end];
            a[end]=temp;
        }
        int right=0;//统计右侧的个数
        int left=0;//统计左侧的个数
        int center=0;//统计中间的个数
        int pivot1=start;
        int pivot2=end;
        for(int i=start;i<end;i++) {
            if(a[i]<a[pivot1]) {
                int temp=a[i];
                a[i]=a[pivot1];
                a[pivot1]=temp;
                pivot1=i;//把第一个轴对正
                left++;//左侧数据个数++
            }else if(a[i]>=a[pivot1]&&a[i]<=a[pivot2]) {
                center++;//中间数据个数++
            }else if(a[i]>a[pivot2]) {
                //换到第二个轴的前一个元素。
                int temp=a[i];
                a[i]=a[pivot2-1];
                a[pivot2-1]=temp;
                //和第二个轴换。
                temp=a[pivot2-1];
                a[pivot2-1]=a[pivot2];
                a[pivot2]=temp;         
                pivot2--;//第二个轴对正。
                right++;//右侧数据个数++。
                i--;//因为我们向前换过去了一个未知元素，这个未知元素需要我们继续判断的！
            }
            //如果所有元素都找到自己的区间了，就结束这次排序
            if(left+center+right==end-start) {
                break;
            }
        }
        //三个区间各自快速排序
        sort(a, start, pivot1-1);
        sort(a, pivot1+1, pivot2-1);
        sort(a, pivot2+1, end);
    }

4-9、堆排序

说到堆排序，它是基于优先队列的，优先队列概念大家自行补充，这里不再说明了，但是给出优先队列的代码实现：

 
xxxxxxxxxx
class MaxPQ<Key extends Comparable<Key>>{
    private Key [] pq;
    private int N=0;
    @SuppressWarnings("unchecked")
    public MaxPQ(int maxN) 
    {
        pq=(Key[])new Comparable[maxN+1];
    }
    
    public boolean isEmpty() {
        return N==0;
    }
    public int size() {
        return N;
    }
    public void insert(Key v) {
        pq[++N]=v;
        //下沉
        swim(N);
    }
    public Key delMax() {
        Key max=pq[1];
        //和最后一个元素交换位置
        exch(1,N--);
        //删掉这个元素
        pq[N+1]=null;
        //上浮，直到叶子节点
        sink(1);
        //返回删掉的那个最大值
        return max;
    }
    
    //打印
    public void show() {
        for (int i = 1; i < pq.length; i++) {
            System.out.print(pq[i]);
        }
    }
    
    //上浮
    private  void sink (int k) {
        while(2*k<=N) {
            int j=2*k;
            if(j<N&&less(j,j+1)) j++;
            if(!less(k,j))break;
            exch(k,j);
            k=j;
        }
    }
    //下沉
    private  void swim(int k) {
        while(k>1&&less(k/2,k)) {
            exch(k/2,k);
            k=k/2;
        }
    }
    //比较
    private  boolean less(int i,int j) {
        return pq[i].compareTo(pq[j])<0;
    }
    //交换
    private  void exch(int i,int j) {
        Key temp=pq[i];
        pq[i]=pq[j];
        pq[j]=temp;
    }
}

有了优先队列，我们把元素放入优先队列里，然后一个一个取出来，就可以了。代码如下：

 
xxxxxxxxxx
    //9、堆排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] a= {5,6,8,7,2,9,1,3,4};
        MaxPQ<Integer> maxPQ=new MaxPQ<Integer>(a.length);
        for (int i = 0; i < a.length; i++) {
            maxPQ.insert(a[i]);
        }
        for (int i = 0; i < a.length; i++) {
            System.out.print(maxPQ.delMax());
        }
    }

4-10、计数排序

 
xxxxxxxxxx
    //10、计数排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int []a= {5,6,8,7,2,9,1,3,4};
        sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    private static void sort(int [] a) {
        int [] temp=new int [10];
        for (int i = 0; i < a.length; i++) {
            temp[a[i]]++;
        }   
        int k=0;
        for (int i = 1; i < temp.length; i++) {
            for (int j = 0; j < temp[i]; j++) {
                a[k++]=i;
            }
        }
    }

4-11、桶排序

 
xxxxxxxxxx
    //11、桶排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int []a= {5,6,8,7,2,9,1,3,4};
        sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    public static void sort(int a[])
    {
        int n = a.length;
        int bask[][] = new int[10][n];
        int index[] = new int[10];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            max = max > (Integer.toString(a[i]).length()) ? max : (Integer.toString(a[i]).length());
        }
        String str;
        for (int i = max - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                str = "";
                if (Integer.toString(a[j]).length() < max) {
                    for (int k = 0; k < max - Integer.toString(a[j]).length(); k++)
                        str += "0";
                }
                str += Integer.toString(a[j]);
                bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = a[j];
            }
            int pos = 0;
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < index[j]; k++) {
                    a[pos++] = bask[j][k];
                }
            }
            for (int x = 0; x < 10; x++)
                index[x] = 0;
        }
    }

4-12、基数排序

 
xxxxxxxxxx
    // 12、基数排序
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int []a= {5,6,8,7,2,9,1,3,4};
        sort(a,1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    public static void sort(int[] number, int d) // d表示最大的数有多少位
    {
        int k = 0;
        int n = 1;
        int m = 1; // 控制键值排序依据在哪一位
        int[][] temp = new int[10][number.length]; // 数组的第一维表示可能的余数0-9
        int[] order = new int[10]; // 数组orderp[i]用来表示该位是i的数的个数
        while (m <= d) {
            for (int i = 0; i < number.length; i++) {
                int lsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }
            for (int i = 0; i < 10; i++) {
                if (order[i] != 0)
                    for (int j = 0; j < order[i]; j++) {
                        number[k] = temp[i][j];
                        k++;
                    }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
    }

5、总结

以上12种排序方式，基本就是目前流行的所有排序了，笔者在这里对于“自认为”比较难理解的“快速排序”、“三向切分的快速排序”、“双轴快速排序”，以及JDK1.7中的Arrays.sort进行了一些说明，谬误之处还望大家批评指正，不胜感激。