linuxsir首页 LinuxSir.Org | Linux、BSD、Solaris、Unix | 开源传万世,因有我参与欢迎您!
网站首页 | 设为首页 | 加入收藏
您所在的位置:主页 > Linux基础建设 >

算法之常见排序算法-冒泡排序、归并排序、快速

时间:2019-09-18  来源:未知  作者:admin666

引言

    对于编程中琳琅满目的算法,本人向来是不善此道也不精于此的,而说起排序算法,也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时,面试官便让手写冒泡排序(入职之后才知道,这面试官就是一个冒泡排序"病态"爱好者,逢面试必考冒泡排序-__-)。后来看吴军的一些文章,提到提高效率的关键就是少做事情不做无用功,便对这不起眼的排序算法有了兴趣。刚好今天周末有闲,遂研究一二,与各位道友共享。

    冒泡排序时间之所以效率低,就是因为将所有数都一视同仁不做区分挨个比较,这是最普通的做事方法,所以效率也是最普通的,时间复杂度为N的平方;而归并排序效率高,则是采用了分治的思想,将一个整体分成多个小份,每个小份排好序之后再互相比较,这样就比冒泡快了不少,时间复杂度为NlogN;快速排序的平均时间复杂度也是NlogN,但是实际的耗费时间会比归并排序快两三倍(当然快排在最坏的情况下时间复杂度还是N的平方,比归并排序大),它的平均执行时间能比归并更快一些是因为它每次分组时不是随机分组而是相对有序的分组,即先从数组中随机取一个数作为基数,然后将数据移动,使得基数一边的数都比它小,另一边的数都比它大,再在两边各取一个基数进行相同的移动、分组操作,递归下去,这样每个细分的小组都在整体的大数组中有个位置,合并时直接按从小到大将各个分组合并起来即可,所以一般情况下会比归并快一些。

    了解了思想之后,再用代码实现相对就会容易很多。此处就再借用一个直观一点的例子来说明归并与快排二者的区别。假设有1000个学生,想对他们的成绩进行排序。方法1借用归并排序的思想,具体这样做:将这1000个人分成10组,将每组的100人进行排序,排完之后再在各组之间从小到大依次进行比较,最后得到整个的成绩排名。方法2借用快速排序的思想,具体需这样做:将1000个人也是分成10组,但是是按分数段分,0-10分的放在一组,10-20分的放在一组,20-30分的放在一组,依次类推,分完组之后再在各个小组中进行排序,而当你合并各个小组时,只需将其按从小到大的顺序直接合并就行,无需跟方法1一样将各小组中的数据取出来跟其他小组中的数据挨个比较。看到这里,想必各位道友对快排比归并排序还要快一些的原因就有了解了。

    算法可以理解成做事的技巧或者说套路,我们对其的理解可以不止于编程,完全可以推广出去。比如归并的分治法,将一个大事情拆解成多个小事件,解决起来就会方便很多。闲话扯了一大堆,下面就将我自己写的排序给大家贴出来,附带上注释讲解,如果有之前不了解的道友,相信看完之后便会念头通透,原地飞升 >_<。

正文

归并排序

// 归并排序
    public static void mergeSort (int[] arr) {
        // 建一个临时数据来存放数据
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) { // 如果起始下标跟结束下标差值小于1,则不进行操作
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp); // 分组,将左边分为一组,递归调用进行排序
            mergeSort(arr, mid+1, right, temp); // 将右边分为一组
            merge(arr, left, mid, right, temp); //将左右分组合并
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 定义左指针
        int j = mid + 1; // 定义右指针
        int t = 0; // 给temp临时数组用的指针
        while (i <= mid && j <= right) { // 设置左右指针的移动边界
            if (arr[i] <= arr[j]) { // 此处是升序,故谁小谁先赋给临时数组
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) { // 如果左边有剩余,则放在temp中
            temp[t++] = arr[i++];
        }
        while (j <= right) { // 如果右边有剩余,依次放入temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        // 此时temp中已经是arr数组中下标从left到right之间排好序的数据了,因为temp每次都是从0开始赋值,所以需将排好序的数放回arr的对应位置
        while (left <= right) {
            // 将left到right之间排好序的数据放回arr中,此时left到right之间的数就是最终排好序的数
            arr[left++] = temp[t++];
        }
    }

快速排序

// 快速排序
    public static void quickSort (int[] arr, int left, int right) {
        // 先将异常情况处理掉
        if (arr == null || arr.length < 2) {
            return;
        }
        if (right <= left) {
            return;
        }
        if (right - left == 1 && arr[left] <= arr[right]) {
            return;
        }
        // 取第一个数为基准数(基数取哪个都行,此处是为了方便)
        int index = arr[left];
        int i = left + 1; // 左指针
        int j = right; // 右指针
        while (i < j && i < right && j > left) { // 设置指针的移动边界
            while (arr[j] > index && j > left) {j--;} // 找到从右边数第一个比index小的数
            while (arr[i] < index && i < right) {i++;} // 找到从左边数第一个比index大的数
            if (i < j) { // 交换这两个数  如果i == j,说明二者定位到了同一个位置,则不用交换;如果i > j,说明二者已经相遇然后背向而行了,也不交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 执行完上面循环后,arr已经是左边比index小,右边比index大的数组了,只是基准数仍在基准位置left处,需放到它应该在的位置
        if (j != left && arr[j] != arr[left]) {
            // j最后停留位置的数,肯定是一个小于等于index的值,所以如果不是同一个位置的话,直接将二者调换一下位置即可
            int temp = arr[j];
            arr[j] = arr[left];
            arr[left] = temp;
        }
        quickSort(arr, left, j-1); // 将基准数左边排序
        quickSort(arr, j+1, right); // 将基准数右边排序
    }

Linux公社的RSS地址:https://www.linuxidc.com/rssFeed.aspx

上一篇:Java线程的中断
友情链接
  • Mozilla发布Firefox 67.0.4,修复沙箱逃逸漏洞
  • 蚂蚁金服正式成为CNCF云原生计算基金会黄金会员
  • Firefox 68将采用Microsoft BITS安装更新
  • OpenSSH增加对存储在RAM中的私钥的保护
  • 谷歌想实现自己的curl,为什么?
  • Raspberry Pi 4发布:更快的CPU、更大的内存
  • Firefox的UA将移除CPU架构信息
  • Ubuntu放弃支持32位应用程序实属乌龙,Steam会否重回Ubuntu怀抱
  • Qt 5.13稳定版发布:引入glTF 2.0、改进Wayland以及支持Lottie动
  • 红帽企业Linux 7现已内置Redis 5最新版
  • Slack进入微软内部禁用服务清单,GitHub也在其列?
  • 安全的全新编程语言V发布首个可用版本
  • Windows Terminal已上架,快尝鲜
  • 阿里巴巴微服务开源生态报告No.1
  • 面世两年,Google地球将支持所有基于Chromium的浏览器
  • 推进企业容器化持续创新,Rancher ECIC千人盛典完美收官
  • CentOS 8.0最新构建状态公布,或于数周后发布
  • Debian移植RISC
  • 微软拆分操作系统的计划初现雏形
  • Oracle发布基于VS Code的开发者工具,轻松使用Oracle数据库
  • Ubuntu 19.10停止支持32位的x86架构
  • 微软为Windows Terminal推出全新logo
  • 联想ThinkPad P系列笔记本预装Ubuntu系统
  • 微软发布适用于Win7/8的Microsoft Edge预览版
  • 启智平台发布联邦学习开源数据协作项目OpenI纵横
  • 经过六个多月的延迟,微软终于推出Hyper
  • ZFS On Linux 0.8.1 发布,Python可移植性工作
  • DragonFly BSD 5.6.0 发布,HAMMER2状态良好
  • Linux Kernel 5.2
  • CentOS 8.0 看起来还需要几周的时间
  • 百度网盘Linux版正式发布
  • PCIe 6.0宣布:带宽翻倍 狂飙至256GB/s
  • PHP 7.4 Alpha 发布,FFI扩展,预加载Opcache以获得更好的性能
  • Canonical将在未来的Ubuntu版本中放弃对32位架构的支持
  • Scala 2.13 发布,改进的编译器性能
  • 微软的GitHub收购了Pull Panda,并且使所有订阅完全免费
  • Windows Subsystem for Linux 2 (WSL 2)现在适用于Windows 10用
  • Debian 10 “Buster”的RISC
  • MariaDB宣布发布MariaDB Enterprise Server 10.4
  • DXVK 1.2.2 发布,带来微小的CPU开销优化
  • DragonFlyBSD 5.6 RC1 发布,VM优化,默认为HAMMER2
  • PrimeNG 8.0.0 发布,支持Angular 8,FocusTrap等
  • GIMP 2.10.12 发布,一些有用的改进
  • 清华大学Anaconda 镜像服务即将恢复
  • Debian GNU/Linux 10 “Buster” 操作系统将于2019年7月6日发布
  • 时时彩论坛
  • 五星体育斯诺克
  • 北单比分直播
  • 河北11选5走势图
  • 福建体彩36选7开奖结果
  • 九龙图库下载