开发者社区> 白大锅> 正文

数据结构与算法之排序(冒泡、选择、插入、希尔、归并、快速)(二)

简介: 数据结构与算法之排序(冒泡、选择、插入、希尔、归并、快速)
+关注继续查看

二、高级排序


上面我们学习过基础排序,包括冒泡排序,选择排序还有插入排序,并且对他们在最坏情况下的时间复杂度做了分析,发现都是O(N^2),而平方阶通过我们之前学习算法分析我们知道,随着输入规模的增大,时间成本将急剧上升,所以这些基本排序方法不能处理更大规模的问题,接下来我们学习一些高级的排序算法,争取降低算法的时间复杂度最高阶次幂


2.1.希尔排序


希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本


前面学习插入排序的时候,我们会发现一个很不友好的事儿,如果已排序的分组元素为 {2,5,7,9,10},未排序的分组元素为{1,8},那么下一个待插入元素为1,我们需要拿着1从后往前,依次和10,9,7,5,2进行交换位置,才能完成真正的插入,每次交换只能和相邻的元素交换位置。那如果我们要提高效率,直观的想法就是一次交换,能把1放到更前面的位置,比如一次交换就能把1插到2和5之间,这样一次交换1就向前走了5个位置,可以减少交换的次数,这样的需求如何实现呢?接下来我们来看看希尔排序的原理


需求:


排序前:{9,1,2,5,7,4,8,6,3,5}

排序后:{1,2,3,4,5,5,6,7,8,9}


排序原理:


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

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

3.减小增长量,最小减为1,重复第二步操作。


3268ce4242d14abf8887cd2f66684b63.png

增长量 h的确定:增长量h的值每一固定的规则,我们这里采用以下规则:

int h=1
while(h<5){
    h=2h+1;//3,7
}
//循环结束后我们就可以确定h的最大值;
//h的减小规则为:
    h=h/2


希尔排序的API设计:


image.png

希尔排序的代码实现:

//排序代码
public class Shell {
    /*
    对数组a中的元素进行排序
    */
    public static void sort(Comparable[] a){
        int N = a.length;
        //确定增长量h的最大值
        int h=1;
        while(h<N/2){
            h=h*2+1;
        }
        //当增长量h小于1,排序结束
        while(h>=1){
            //找到待插入的元素
            for (int i=h;i<N;i++){
            //a[i]就是待插入的元素
            //把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中
                for (int j=i;j>=h;j-=h){
                //a[j]就是待插入元素,依次和a[j-h],a[j-2h],a[j-3h]进行比较,如果a[j]小,那么
                交换位置,如果不小于,a[j]大,则插入完成。
                if (greater(a[j-h],a[j])){
                    exch(a,j,j-h);
                }else{
                break;
                }
            }
        }
        h/=2;
    }
}
    /*
    比较v元素是否大于w元素
    */
    private static boolean greater(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;
    }
}
//测试代码
public class Test {
    public static void main(String[] args) {
        Integer[] a = {9,1,2,5,7,4,8,6,3,5} ;
        Shell.sort(a);
        System.out.println(Arrays.toString(a));
    }
}


希尔排序的时间复杂度分析:


在希尔排序中,增长量h并没有固定的规则,有很多论文研究了各种不同的递增序列,但都无法证明某个序列是最好的,对于希尔排序的时间复杂度分析,已经超出了我们课程设计的范畴,所以在这里就不做分析了。我们可以使用事后分析法对希尔排序和插入排序做性能比较。在资料的测试数据文件夹下有一个reverse_shell_insertion.txt文件,里面存放的是从100000到1的逆向数据,我们可以根据这个批量数据完成测试。测试的思想:在执行排序前前记录一个时间,在排序完成后记录一个时间,两个时间的时间差就是排序的耗时。


希尔排序和插入排序性能比较测试代码:

public class SortCompare {
    public static void main(String[] args) throws Exception{
        ArrayList<Integer> list = new ArrayList<>();
        //读取reverse_arr.txt文件
        BufferedReader reader = new BufferedReader(new InputStreamReader(new
        FileInputStream("reverse_shell_insertion.txt")));
        String line=null;
        while((line=reader.readLine())!=null){
            //把每一个数字存入到集合中
            list.add(Integer.valueOf(line));
        }
        reader.close();
        //把集合转换成数组
        Integer[] arr = new Integer[list.size()];
        list.toArray(arr);
        testInsertion(arr);//使用插入排序耗时:20859
        // testShell(arr);//使用希尔排序耗时:31
    }
    public static void testInsertion(Integer[] arr){
        //使用插入排序完成测试
        long start = System.currentTimeMillis();
        Insertion.sort(arr);
        long end= System.currentTimeMillis();
        System.out.println("使用插入排序耗时:"+(end-start));
    }
    public static void testShell(Integer[] arr){
        //使用希尔排序完成测试
        long start = System.currentTimeMillis();
        Shell.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("使用希尔排序耗时:"+(end-start));
    }
}


通过测试发现,在处理大批量数据时,希尔排序的性能确实高于插入排序


2.2.归并排序


2.2.1. 递归


正式学习归并排序之前,我们得先学习一下递归算法。


定义:


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

public void show(){
    System.out.println("aaaa");
    show();
}

作用:


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


注意事项:


在递归中,不能无限制的调用自己,必须要有边界条件,能够让递归结束,因为每一次递归调用都会在栈内存开辟新的空间,重新执行方法,如果递归的层级太深,很容易造成栈内存溢出


4866458320c041aa910af586fad7eff7.png

需求:


请定义一个方法,使用递归完成求N的阶乘

分析:
1!: 1
2!: 2*1=2*1!
3!: 3*2*1=3*2!
4!: 4*3*2*1=4*3!
...
n!: n*(n-1)*(n-2)...*2*1=n*(n-1)!
所以,假设有一个方法factorial(n)用来求n的阶乘,那么n的阶乘还可以表示为n*factorial(n-1)

代码实现:

public class Test {
    public static void main(String[] args) throws Exception {
        int result = factorial(5);
        System.out.println(result);
    }
    public static int factorial(int n){
        if (n==1){
        return 1;
    }
    return n*factorial(n-1);
    }
}


2.2.2 归并排序


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


需求:


排序前:{8,4,5,7,1,3,6,2}

排序后:{1,2,3,4,5,6,7,8}

排序原理:


1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止。


2.将相邻的两个子组进行合并成一个有序的大组;


3.不断的重复步骤2,直到最终只有一个组为止


fdca0249c61e4b0294382870e43590a1.png


归并排序 API设计:


image.png


归并原理:


a7beadb45ee040969156ef847c7a563a.png

b68d23c0a5e2498391a6ba8b620edc72.png

ec47bab7b5194549afa05c3365ed0830.png

65483221c1ec489ab7a81249c9af6e78.png

b5d7526751ea499a84886f036997c04f.png

归并排序代码实现:

// 排序代码
public class Merge {
    private static Comparable[] assist;//归并所需要的辅助数组
    /*
    对数组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的元素进行排序
    */
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
        return;
    }
    int mid = lo + (hi - lo) / 2;
    //对lo到mid之间的元素进行排序;
    sort(a, lo, mid);
    //对mid+1到hi之间的元素进行排序;
    sort(a, mid+1, hi);
    //对lo到mid这组数据和mid到hi这组数据进行归并
    merge(a, lo, mid, hi);
}
/*
对数组中,从lo到mid为一组,从mid+1到hi为一组,对这两组数据进行归并
*/
private static void merge(Comparable[] a, int lo, int mid, int hi) {
    //lo到mid这组数据和mid+1到hi这组数据归并到辅助数组assist对应的索引处
    int i = lo;//定义一个指针,指向assist数组中开始填充数据的索引
    int p1 = lo;//定义一个指针,指向第一组数据的第一个元素
    int p2 = mid + 1;//定义一个指针,指向第二组数据的第一个元素
    //比较左边小组和右边小组中的元素大小,哪个小,就把哪个数据填充到assist数组中
    while (p1 <= mid && p2 <= hi) {
        if (less(a[p1], a[p2])) {
            assist[i++] = a[p1++];
        } else {
            assist[i++] = a[p2++];
        }
    }
    //上面的循环结束后,如果退出循环的条件是p1<=mid,则证明左边小组中的数据已经归 并完毕,如果退
    出循环的条件是p2<=hi,则证明右边小组的数据已经填充完毕;
    //所以需要把未填充完毕的数据继续填充到assist中,//下面两个循环,只会执行其中的一个
    while(p1<=mid){
        assist[i++]=a[p1++];
    }
    while(p2<=hi){
        assist[i++]=a[p2++];
    }
    //到现在为止,assist数组中,从lo到hi的元素是有序的,再把数据拷贝到a数组中对应的索引处
    for (int index=lo;index<=hi;index++){
        a[index]=assist[index];
    }
}
/*
比较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;
}
}
//测试代码
public class Test {
    public static void main(String[] args) throws Exception {
        Integer[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        Merge.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

归并排序时间复杂度分析:


归并排序是分治思想的最典型的例子,上面的算法中,对a[lo…hi]进行排序,先将它分为a[lo…mid]和a[mid+1…hi]两部分,分别通过递归调用将他们单独排序,最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果一个数组不能再被分为两个子数组,那么就会执行merge进行归并,在归并的时候判断元素的大小进行排序


438f41dcf12c4dec8eb59a2ba7e87771.png

用树状图来描述归并,如果一个数组有8个元素,那么它将每次除以2找最小的子数组,共拆log8次,值为3,所以树共有3层,那么自顶向下第k层有2k个子数组,每个数组的长度为2(3-k),归并最多需要2^(3-k)次比较。因此每层的比较次数为 2^k * 2(3-k)=23,那么3层总共为 32^3。


假设元素的个数为n,那么使用归并排序拆分的次数为log2(n),所以共log2(n)层,那么使用log2(n)替换上面32^3中的3这个层数,最终得出的归并排序的时间复杂度为:log2(n)* 2^(log2(n))=log2(n)*n,根据大O推导法则,忽略底数,最终归并排序的时间复杂度为O(nlogn);


归并排序的缺点:


需要申请额外的数组空间,导致空间复杂度提升,是典型的以空间换时间的操作。


归并排序与希尔排序性能测试:


之前我们通过测试可以知道希尔排序的性能是由于插入排序的,那现在学习了归并排序后,归并排序的效率与希尔排序的效率哪个高呢?我们使用同样的测试方式来完成一样这两个排序算法之间的性能比较。


在资料的测试数据文件夹下有一个reverse_arr.txt文件,里面存放的是从1000000到1的逆向数据,我们可以根据这个批量数据完成测试。测试的思想:在执行排序前前记录一个时间,在排序完成后记录一个时间,两个时间的时间差就是排序的耗时。


希尔排序和插入排序性能比较测试代码:

public class SortCompare {
    public static void main(String[] args) throws Exception{
        ArrayList<Integer> list = new ArrayList<>();
        //读取a.txt文件
        BufferedReader reader = new BufferedReader(new InputStreamReader(newFileInputStream("reverse_merge_shell.txt")));
        String line=null;
        while((line=reader.readLine())!=null){
            //把每一个数字存入到集合中
            list.add(Integer.valueOf(line));
        }
        reader.close();
        //把集合转换成数组
        Integer[] arr = new Integer[list.size()];
        list.toArray(arr);
        // testMerge(arr);//使用归并排序耗时:1200
        testShell(arr);//使用希尔排序耗时:1277
    }
    public static void testMerge(Integer[] arr){
        //使用插入排序完成测试
        long start = System.currentTimeMillis();
        Merge.sort(arr);
        long end= System.currentTimeMillis();
        System.out.println("使用归并排序耗时:"+(end-start));
    }
    public static void testShell(Integer[] arr){
        //使用希尔排序完成测试
        long start = System.currentTimeMillis();
        Shell.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("使用希尔排序耗时:"+(end-start));
    }
}

通过测试,发现希尔排序和归并排序在处理大批量数据时差别不是很大

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
18785 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
27957 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22043 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15480 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20097 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14867 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23536 0
+关注
白大锅
Java领域优质创作者、多年全栈开发经验
103
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载