常见的排序算法--Java

冒泡排序

排序原理：

1. 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
2. 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值

代码实现

public class Bubble {
    /**
     * 对数组a中的元素进行排序
     * @param a
     */
    public  static void sort(Comparable[] a){
        for (int i=0;i< a.length;i++){
            for (int j=0;j< a.length-i-1;j++){
                if (greater(a[j],a[j+1])){
                    exch(a,j,j+1);
                }
            }
        }
    }

    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    public static  boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }

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

选择排序:

1. 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引的值，则假定其他某个索引处的值为最小值，最后可以找到最小值所在的索引

2. 交换第一个索引和最小值所在的索引处的值

   

代码实现:

public class Selection {

    /**
     * 对数组a进行午排序
     * @param a
     */
    public static void sort(Comparable[] a){
        for (int i=0;i<a.length;i++){
            int min=i;
            for (int j=i;j< a.length;j++){
                if (greater(a[min],a[j])){
                    min=j;
                }
            }
           exchange(a,min,i);
        }
    }
    /**
     * 在一次比较完成之后交换2个元素
     * @param a
     * @param min
     * @param i
     */
    public static void exchange(Comparable[] a,int min,int i){
        Comparable temp;
        temp=a[min];
        a[min]=a[i];
        a[i]=temp;
    }

    /**
     * 比较2个元素的大小
     * @param a
     * @param b
     * @return
     */
    public static boolean greater(Comparable a, Comparable b){
        return a.compareTo(b)>0;
    }
}

插入排序：

1. 把所有的元素分为两组，已经排序的和未排序的；
2. 找到未排序组中的第一个，向已排序组中进行插入；
3. 倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

代码实现：

public class Insertion {
    /**
     * 对数组进行排序
     * @param a
     */
    public  static void sort(Comparable[] a){
        for (int i=1;i<a.length;i++){
            for (int j=i;j>=1;j--){
                if (greater(a[j],a[j-1])){
                  exchange(a,j,j-1);
                }else {
                    break;
                }
            }
        }
    }
    
    /**
     * 判断2个元素的大小关系
     * @param a
     * @param b
     * @return
     */
    public static boolean greater(Comparable a,Comparable b){
        return a.compareTo(b)<0;
    }

    /**
     * 交换2个元素在数组的位置
     * @param a
     * @param i
     * @param j
     */
    public static void exchange(Comparable[] a,int i,int j){
        Comparable temp;
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

希尔排序：（n1.3次方）

1. 选定一个增长量h,按照增长量h作为数据分组的依据，对数据进行分组；

2. 对分好组的每一组数据完成插入排序；

3. 减少增长量，最小减为1，重复第二步操作；

   增长量h和减少的确定：

   int h=1
   while(h<数组的长度/2){
   	h=2h+1;
   }
   //循环结束后我们就可以确定h的最大值
   h的减少规则为:
   	h=h/2
   

代码实现

public class Shell {
    /**
     * 对数组进行排序
     * @param a
     */
    public  static void sort(Comparable[] a){
        int h=1;
        while (h<(a.length/2)){
            h=2*h+1;
        }
        while (h!=0){
//            找到每组待插入的元素
            for (int i=h;i<a.length;i++){
                for (int j=i;j>=h;j-=h){
                    if (greater(a[j-h],a[j])){
                        exchange(a,j-h,j);
                    }else {
                        break;
                    }
                }
            }
            h=h/2;
        }
    }
    /**
     * 判断2个元素的大小关系
     * @param a
     * @param b
     * @return
     */
    public static boolean greater(Comparable a,Comparable b){
        return a.compareTo(b)>0;
    }

    /**
     * 交换2个元素在数组的位置
     * @param a
     * @param i
     * @param j
     */
    public static void exchange(Comparable[] a,int i,int j){
        Comparable temp;
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

递归：

定义：定义方法时，在方法内部调用方法本身，称之为递归

作用：它通常把一个大型复杂的问题，层层转换为一个与原问题相似的，规模较小的问题来求解。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

求n的阶层：

代码实现：

public class Factorial {

    /**
     * 求n的阶层
     * @param n
     * @return
     */
    public static Long factorial(Long n){
        if (n==1){
            return 1L;
        }else {
            return n*factorial(n-1);
        }
    }
}

归并排序：

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

原理：

1. 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
2. 将相邻的两个子组进行合并成一个有序的大组。
3. 不断的重复步骤2，直到最终只有一个组为止。

归并过程：

代码实现：（nlogn）

public class Merge {
    /**
     * 完成归并操作需要的辅助数组
     */
    private static  Comparable[] assist;

    /**
     * 对数组内的元素进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
//        初始化辅助数组
        assist=new Comparable[a.length];
        int lo=0;
        int hi=a.length-1;
        sort(a,lo,hi);
    }

    /**
     * 对数组a中从索引lo到索引hi之间的元素进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a,int lo,int hi){
//        做一个安全校验
        if (hi<=lo){
            return;
        }
//        对lo到hi的数据进行分组(2组)
        int mid=lo+(hi-lo)/2;
//        对分组元素进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
//        将2个组进行归并
        merge(a,lo,mid,hi);
    }

    /**
     * 从索引lo到索引mid为一个子组，从索引mid+1到索引hi为另一个子组，把数组
     * a中的这两个子组的数据合并成一个有序的大组(从索引lo到索引hi)
     * @param a
     * @param lo
     * @param mid
     * @param hi
     */
    private static void merge(Comparable[] a,int lo,int mid,int hi){
//        定义三个指针
        int i=lo;
        int p1=lo;
        int p2=mid+1;

//        遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
        while (p1<=mid && p2<=hi){
//            比较对应索引处的值
            if (greater(a[p1],a[p2])){
                assist[i++]=a[p1++];
            }else {
                assist[i++]=a[p2++];
            }
        }
//        遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
        while (p1<=mid){
            assist[i++]=a[p1++];
        }
//        遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
        while (p2<=hi){
            assist[i++]=a[p2++];
        }
//        把辅助数组中的元素拷贝到原数组中
        for (int index=lo;index<=hi;index++){
            a[index]=assist[index];
        }
    }

    /**
     * 判断2个元素的大小关系
     * @param v
     * @param w
     * @return
     */
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分隔为两个独立的部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序原理：

1. 首先设定一个分界值，通过该分界值将数组分成两部分;
2. 将大于或等于分界值的数据放到数组右边，小于分界值的数据放到数组左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将部分数据拆分左右两个部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重置上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，在递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

切分原理：

1. 找一个基准值，用两个指针分别指向数组的头部和尾部；
2. 先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3. 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4. 交换当前左边指针位置和右边指针位置的元素；
5. 重复2，3，4步骤，直到左边指针的值大于右边指针的值停止。

最一步:

代码实现：

public class Quick {
    /**
     * 对数组内所有的元素进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        int lo=0;
        int hi=a.length-1;
        sort(a,lo,hi);
    }
    /**
     * 对拆分的数组进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a,int lo,int hi){
        //安全性校验
        if (lo>=hi){
            return;
        }
        //需要对数组lo索引到hi索引处的元素进行分组(左子组和右子组);
        int partition=partition(a,lo,hi);//返回的是分组的分界值所在的索引，位置变化后的索引

        //让左子组有序
        sort(a, lo, partition-1);

        //让右子组有序
        sort(a,partition+1,hi);
    }
    /**
     * 对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    private static int partition(Comparable[] a,int lo,int hi){
        //确定分界值
        Comparable key=a[lo];
        //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left=lo;
        int right=hi+1;
        //切分
        while (true){
            //先从右向左扫描，移动right指针，找到一个比分界值小的元素，停止
            while (greater(key,a[--right])){
                if (right==lo){
                    break;
                }
            }
            //先从左向右扫描，移动right指针，找到一个比分界值大的元素，停止
            while (greater(a[++left],key)){
                if (left==hi){
                    break;
                }
            }
            if (left>=right){
                break;
            }else{
                exchange(a,left,right);
            }
        }
        exchange(a,right,lo);
        return right;
    }

    /**
     * 交换a数组中元素的位置
     * @param a
     * @param i
     * @param j
     */
    private static void exchange(Comparable[] a,int i,int j){
            Comparable temp;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
    }
    /**
     * 比较a是否小于b
     * @param a
     * @param b
     * @return
     */
    private static boolean greater(Comparable a,Comparable b){
        return a.compareTo(b)<0;
    }
}