基本数据结构与算法实现JavaAPI【2】-----排序篇

在本篇章中不阐释原理，仅阐述使用java语言实现。

1.冒泡排序（时间复杂度：O(N^2)；稳定）：

public class sort00 {
    public static void sort(Comparable[] a){
        for(int i=a.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                if(greater(a[j],a[j+1])){
                    exch(a,j,j+1);
                }
            }
        }
    }
 
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp=a[i];
        a[i]=a[j];
        a[j]=temp;
 
    }
 
    private static boolean greater(Comparable a, Comparable b) {
        return a.compareTo(b)>0;
    }
 
}

​冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。（出自百度百科）
​

2.选择排序：（时间复杂度：O(N^2)；不稳定）：

public class sort01 {
    public static void sort(Comparable[] a){
        for (int i = 0; i <a.length-1 ; i++) {
            int minindex=i;
            for(int j=i+1;j<a.length;j++){
                if(greater(a[minindex],a[j])){
                    minindex=j;
                }
            }
            exch(a,i,minindex);
        }
    }
 
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp=a[i];
        a[i]=a[j];
        a[j]=temp;
 
    }
 
    private static boolean greater(Comparable a, Comparable b) {
        return a.compareTo(b)>0;
    }
 
}

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。（出自百度百科）

3.插入排序：（时间复杂度：O(N^2)；稳定）

public class sort02 {
    public static void sort(Comparable[] a){
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i; j >=0 ; j--) {
                if(geater(a[j],a[j+1])){
                    exch(a,j,j+1);
                }
            }
        }
    }
 
 
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
 
    private static boolean geater(Comparable a,Comparable b){
        return a.compareTo(b)>0;
    }
}

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动（出自百度百科）

4.希尔排序（不稳定）

public class sort03 {
 
    public static void sort(Comparable[] a){
        //1.由数组a的长度确定增长量h的初始值
        int h=1;
        while (h<a.length/2){
            h=2*h+1;
        }
        //2.希尔排序
        while (h>=1){
            //排序
            //找到待插入的元素
            for (int i = h; i < a.length; i++) {
                //把待插入的元素插入到有序数列中
                for (int j = i; j >=h ; j-=h) {
                    //带插入元素是a[j],比较a[j]和a[j-h]
                    if(geater(a[j-h],a[j])){
                        //交换元素
                        exch(a,j-h,j);
                    }else {
                        //待插入元素已经找到了合适的位置，结束循环
                        break;
                    }
                }
            }
 
            //减小h的值
            h=h/2;
        }
    }
 
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
 
    private static boolean geater(Comparable a,Comparable b){
        return a.compareTo(b)>0;
    }
 
}

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止（出自百度百科）

5.归并排序：时间复杂度为o(nlog(n))

public class sort04 {
    //归并排序所需要的辅助数组
    private  static Comparable[] assist;
 
    //比较v元素是否小于w元素
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
 
//    数组元素i和j交换位置
    private static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
 
//    对数组a中元素进行排序
    public static void sort(Comparable[] a){
        //1.初始化辅助数组assist
        assist=new Comparable[a.length];
        //2.定义一个lo变量和hi变量，分别记录数组中最小索引和最大索引
        int lo=0;
        int hi=a.length-1;
        //3.调用sort重载方法完成数组a中，从实验lo到索引hi的元素的排序
        sort(a,lo,hi);
    }
 
//    对数组a中从lo到hi的元素进行排序
    private static void sort(Comparable[] a,int lo,int hi){
        if(hi<=lo){
            return;
        }
//        对lo到hi之间的数据分为两个组
        int mid=lo+(hi-lo)/2;
 
//        分别对每一组数据排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
 
//        把两个组中的数据进行归并
        merge(a,lo,mid,hi);
    }
 
//    对数组中从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并
    private static void merge(Comparable[] a,int lo,int mid,int hi){
        //定义三个指针
        int i=lo,p1=lo,p2=mid+1;
        //遍历移p1指针和p2指针，比较对应索引处的值，找出最小的一个，放到辅助数组的对应索引处
        while (p1<=mid && p2<=hi){
            //比较对应索引处的值
            if(less(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];
        }
    }
}

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

6.快速排序

public class sort05 {
    //比较v元素是否小于w元素
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
 
    //    数组元素i和j交换位置
    private static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
 
    //    对数组a中元素进行排序
    public static void sort(Comparable[] a){
        int lo=0;
        int hi=a.length-1;
        sort(a,lo,hi);
    }
 
    //    对数组a中从lo到hi的元素进行排序
    private static void sort(Comparable[] a,int lo,int hi){
        //安全性校验
        if(hi<=lo){
            return;
        }
        //需要对数组中lo索引到hi索引出的元素进行分组(左子组和右子组)
        int partition = partition(a, lo, hi);//返回的是分组分界值所在的索引，分界值位置变换后的索引
 
        //让左子组有序
        sort(a,lo,partition-1);
 
        //让右子组有序
        sort(a,partition+1,hi);
    }
 
    // 对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引
    public static int partition(Comparable[] a,int lo,int hi){
        //确定分界值
        Comparable key =a[lo];
        //对应两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left=lo;
        int right=hi+1;
        //切分
        while (true){
            //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止
            while (less(key,a[--right])){
                if(right==lo){
                    break;
                }
            }
            //在从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
            while (less(a[++left],key)){
                if(left==hi){
                    break;
                }
            }
            // 判断left>=right；如果成立则证明元素扫描完毕结束循环。若不成立，则交换元素即可
            if(left>=right){
                break;
            }else {
                exch(a,left,right);
            }
        }
        //交换分界值
        exch(a,lo,right);
 
        return right;
    }
}

快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对冒泡排序算法的一种改进（出自百度百科）

几种排序算法小节：

排序的稳定性：
    在乱序数组中，相等元素A,B在排序之后，其位置保持不变，表明此排序算法是稳定的
稳定性的意义：
    在多次排序情况下需要使用稳定性的算法，意义在于可以最大保留排序后的结果，减小内存开销

稳定排序：
    冒泡、插入、归并、

快速排序和归并排序的区别：
            1.归并：先等数量分组各自排序，将分别拍好序的子数组再重新排序成原数组
            2.快排：先按标准值分组，这个组不一定是等数量分组，分好组后再各自排序，当所有组拍好序，本数组就有序
        时间复杂度：
            等分最优：o(nlog(n))
            有多少个元素切多少组最坏：o(n^2)
            平均复杂度o(nlog(n))