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

发布于:2023-01-10 ⋅ 阅读:(410) ⋅ 点赞:(0)

在本篇章中不阐释原理,仅阐述使用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))