数据结构与算法第七讲 - 排序(上)

对于排序算法,主要掌握内容如下:

  • 排序算法的实现原理
  • 手写出实现代码
  • 评价及分析算法

本讲内容

如何分析一个排序算法
冒泡排序
插入排序
选择排序

思考题:插入排序和冒泡排序的时间复杂度相同,都是 O(n2),在实际的软件开发里,为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢?

如何分析一个排序算法?

排序算法的执行效率

  1. 最好情况、最坏情况、平均情况时间复杂度
    有序度不同的数据,算法的时间复杂度不同
  2. 时间复杂度的系数、常数 、低阶
    时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶。
    但在实际开发中,排序算法中的数据集一般是有限的,有的可能还比较小,所以这个时候不能忽略系数、常数、低阶,要考虑进去
  3. 比较次数和交换(或移动)次数
    基于比较的排序算法的执行过程,会涉及两种操作,一种是元素比较大小,另一种是元素交换或移动。
    TODO:那些是基于比较的排序算法

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量。
针对排序算法的空间复杂度,我们还引入了一个新的概念,原地排序(Sorted in place)
原地排序算法,就是特指空间复杂度是 O(1) 的排序算法

排序算法的稳定性

稳定性:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
为什么要引入稳定性?
对于纯数据的排序,数据是否改变顺序没什么影响
但实际业务开发过程中,大多是对一个对象进行排序,而一个对象有多个属性。

比如我们现在要给电商交易系统中的“订单”排序。订单有两个属性,一个是下单时间,另一个是订单金额。如果我们现在有 10 万条订单数据,我们希望按照金额从小到大对订单数据排序。对于金额相同的订单,我们希望按照下单时间从早到晚有序。对于这样一个排序需求,我们怎么来做呢?

最先想到的方法是:我们先按照金额对订单数据进行排序,然后,再遍历排序之后的订单数据,对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难,但是实现起来会很复杂。
借助稳定排序算法,这个问题可以非常简洁地解决。解决思路是这样的:

  1. 先按照下单时间给订单排序,注意是按照下单时间,不是金额。
  2. 排序完成之后,用稳定排序算法,按照订单金额重新排序。
    两遍排序之后,得到的订单数据就是按照金额从小到大排序,金额相同的订单按照下单时间从早到晚排序的。因为稳定排序算法可以保持金额相同的两个对象,在排序之后的前后顺序不变。

冒泡排序(Bubble Sort)

原理:

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

代码实现:


// 冒泡排序,a表示数组,n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换,提前退出
  }
}

算法分析:

  • 原地排序算法,即空间复杂度为O(1),因为只有在进行数据交换时申请一个临时空间用于交换数据
  • 稳定排序算法,相同的元素排序前后顺序没有改变
  • 时间负复杂度:最好O(n),最坏O(n2),平均O(n2)
    TODO:平均复杂度的计算过程
    借助于有序度,逆序度和满有序度进行计算
    有序度:数组中具有有序关系的元素对的个数。有序元素对:a[i] <= a[j], 如果i < j。


    有序度

对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是 n(n-1)/2,也就是 15。
我们把这种
完全有序的数组的有序度叫作满有序度*。

逆序度:

插入排序

原理:

一个有序的数组,我们往里面添加一个新的数据后,如何继续保持数据有序呢?

  • 遍历数组,找到数据应该插入的位置将其插入即可。
    插入数据前,要把要插入位置之后的数据进行后移,腾挪出空间给新插入的数据


    有序数组插入一个新元素

上面一个动态排序的过程,即动态地往有序集合中添加数据,我们可以通过这种方法保持集合中的数据一直有序。

而对于一个静态的数组,我们如何借鉴上面的插入思想保证其有序呢?

  • 将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。
    插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

插入排序也包含两种操作,一种是元素的比较,一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时,需要拿 a 与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 a 插入。

思考:对于一个给定的数据序列,使用插入排序算法使其有序,需要移动多少次元素?
解答:移动次数是固定的,等于逆序度

代码实现:

// 插入排序,a表示数组,n表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

算法分析:

  • 原地排序算法
  • 稳定排序算法
  • 时间复杂度:最好O(n),最坏O(n2),平均O(n2)

选择排序

原理:

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

代码:

算法分析

  • 原地排序算法
  • 非稳定排序算法
  • 最好,最坏和平均时间复杂度都是O(n2)

排序画图工具:https://visualgo.net/en

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

推荐阅读更多精彩内容