重温数据结构-排序

排序是数据结构中比较重要的一种基础算法,排序也会考验对线性表和链表、树的灵活运用,本篇文章我们重点讲述下常见的3种基础排序冒泡排序、插入排序、选择排序,下一篇会重点讲述实际工作中用的比较多的快速排序和归并排序。

排序算法基础

排序算法执行效率一般从以下几方面进行衡量:

1)最好情况、最坏情况、平均情况下的时间复杂度

对于待排序数据有的接近有序,有的完全无序,会导致部分算法执行效率上有很大的差异,所以我们在选择算法的时候除了要考虑算法的平均时间复杂度还要参考在实际业务场景下待排数据的实际有序性,和各类排序算法在实际业务场景下的待排数据的时间复杂度来选择合适的算法。

2)比较次数和交换次数

在考虑排序算法的时候,因为基于比较的排序算法会涉及到元素大小比较和元素的交换,所以要把比较次数和交换次数也考虑进去。

3)排序算法的稳定性

仅用效率判断一额排序算法好坏还是不够的,还要看算法的稳定性,什么是算法的稳定性?如果待排序中存在值相等的元素,经过排序后,相等元素之间原有的先后顺序不变,这就说明算法是稳定的。

算法的稳定性在很多多次排序场景下是非常有效的,例如我们需要对一个用户类先按照用户的年龄排序,再按照用户的姓名排序,如果使用的不是稳定算法那么在按照年龄排完序后还需要对相等值再分别进行内部排序,这将非常麻烦,如果是稳定的排序算法,那么处理起来将非常容易,只需要用稳定排序算法对数据进行两次排序就行了,因为排序属性相等的数据在排序前后相对顺序不会变的。

冒泡排序

冒泡排序一般是我们在学习排序算法遇到的第一个排序算法,也是最简单的一种排序算法,冒泡排序的核心思路是相邻两个元素之间的比较,不满足大小关系则交换一次,冒泡排序至少让一个元素移动到它应该在的位置,重复n次完成排序。对于冒泡排序比较形象的解释就是水里的气泡,一堆气泡,含空气多的气泡会从下面慢慢往上升。冒泡排序属于原地排序,只需要一个额外的临时空间所以空间复杂度为O(1),在待排序数据是有序的情况下最好的时间复杂度为O(n),平均时间复杂度为O(n^2)。

public void bubbleSort(int nums[]){
        int temp;
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums.length-i-1;j++){
                if(nums[j]>nums[j+1]){
                    temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }

插入排序

插入排序的核心思路是将数据分为有序区和无序区,初始有序区只有第一个元素,插入算法就是从未排序的元素中挑选一个元素,在已排序的区间找到合适的位置并将其插入并保证有序区一直有序。插入排序属于原地排序,是稳定的排序,平均时间复杂度为O(n^2)。

public void insertSort(int[] nums){
        int temp,j;
        for(int i=1;i<nums.length;i++){
            temp = nums[i];
            j=i-1;//需要将j定义在内循环外,用于结束内循环后进行插入值
            for(;j>=0;j--){
                //从后向前倒推,如果已排当前值大于待排值则后移节点
                if(nums[j]>temp){
                    nums[j+1] = nums[j];
                }else{
                    //当已排区的值小于待排值则跳出循环
                    break;
                }
            }
            //在查找到的位置插入待排值
            nums[j+1] = temp;
        }
    }

选择排序

选择排序同样分为已排区和未排区,但是和插入排序不同,选择排序每次会从未排序区间找到最小值放到已排序末尾,这样出来的排序结果就是从小到大升序的数据结果。选择排序也是原地排序,但是选择排序最好和最坏复杂度都是O(n^2)。

public void selectSort(int[] nums){

        int max=0,temp;
        for(int i=0;i<nums.length;i++){
            //从待排序选择最大值
            max = i;
            for(int j=i;j<nums.length;j++){
                max = nums[max]>=nums[j] ? max : j;
            }
            //和已排区最后一个值后面的值交换
            temp = nums[i];
            nums[i] = nums[max];
            nums[max] = temp;
        }
    }

总结

这3种常见排序算法,我们一般只是在学习的时候会去学习,在真实项目过程中很少会使用到这3种排序算法,因为这3种排序算法的时间复杂度都比较高,都是O(n^2),不能满足性能要求,后续会介绍我们日常常用的排序算法快速排序和归并排序,这两个算法在很多场景下都有使用,甚至在oracle这样的商业数据库中也有使用。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,340评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,762评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,329评论 0 329
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,678评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,583评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 47,995评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,493评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,145评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,293评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,250评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,267评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,973评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,556评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,648评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,873评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,257评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,809评论 2 339

推荐阅读更多精彩内容