数据结构与算法学习笔记之如何分析一个排序算法?

数据结构与算法学习笔记之如何分析一个排序算法?

前言

现在IT这块找工作,不会几个算法都不好意思出门,排序算法恰巧是其中最简单的,我接触的第一个算法就是它,但是你知道怎么分析一个排序算法么?有很多时间复杂度相同的排序算法,在实际编码中,那又如何选择呢?下面我们带着问题一起学习一下。

正文

一、常见经典的排序方法

(图片来自于一像素

插入排序

image

希尔排序(递减增量排序算法)

image

归并排序

image

快速排序

image

冒泡排序

image

选择排序

image

计数排序

image

计数排序

image

堆排序

image

二、 按照时间复杂度归类

时间复杂度O(n2):

冒泡排序、插入排序、选择排序

时间复杂度O(nlogn):
快速排序、归并排序

时间复杂度O(n):

计数排序、基数排序、桶排序

三、如何分析一个“排序算法”?

从三个方面入手

a、算法的执行效率

1.最好、最坏、平均情况时间复杂度。

从算法的核心,复杂度入手,给出最好最坏,平均情况下的时间复杂度,便于分析

  1. 时间复杂度的系数、常数和低阶。

时间复杂度表示的是规模很大的一种增涨趋势,很容易就忽略系数,低阶,常数等,实际开发中排序的规模都是像10.100.1000这种小规模

  1. 比较次数,交换(或移动)次数。

排序算法执行过程中,涉及两种操作,一种是元素比较大小,一种是元素交换或移动位置,所以比较次数,交换次数都得考虑进去。

b、排序算法的内存消耗

算法消耗可以通过空间复杂度来衡量

原地排序算法:特指空间复杂度是O(1)的排序算法。

c、排序算法的稳定性

  1. 稳定性概念:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
  2. 稳定性重要性:可针对对象的多种属性进行有优先级的排序。
  3. 举例:给电商交易系统中的“订单”排序,按照金额大小对订单数据排序,对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序,排序完成后用稳定排序算法按照订单金额重新排序。

四、详解冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。

冒泡排序只涉及相邻数据的交换,只需要常量级的临时空间,所以它的空间复杂度未O(1)是原地排序算法

稳定性:当有相邻的两个元素大小相等时,不做交换,冒泡排序是稳定的排序算法。

引入两个概念:

默认从小到大未有序

有序度:数组中具有有序关系的元素对的个数。

满有序度:完全有序的数组

逆序度:数组中具有无序关系的元素对的个数。

逆序度=满有序度-有序度

排序的过程实际上就是增加有序度,减少逆序度的过程

时间复杂度:

  1. 最好情况(满有序度):O(n)。
  2. 最坏情况(满逆序度):O(n^2)。
  3. 平均情况:
    “有序度”和“逆序度”:对于一个不完全有序的数组,如4,5,6,3,2,1,有序元素对为3个(4,5),(4,6),(5,6),有序度为3,逆序度为12;对于一个完全有序的数组,如1,2,3,4,5,6,有序度就是n(n-1)/2,也就是15,称作满有序度;逆序度=满有序度-有序度;冒泡排序、插入排序交换(或移动)次数=逆序度。
    最好情况下初始有序度为n
    (n-1)/2,最坏情况下初始有序度为0,则平均初始有序度为n(n-1)/4,即交换次数为n(n-1)/4,因交换次数<比较次数<最坏情况时间复杂度,所以平均时间复杂度为O(n2)。

代码实现:

<pre style="margin: 0px 0px 15px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px !important; line-height: 1.72222; color: inherit; border-radius: 2px; background: rgb(238, 238, 238); border: 0px; overflow: auto;">// 冒泡排序,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; // 没有数据交换,提前退出
}
}</pre>

五、详解插入排序

将数据分为两个区间,已排序区间和未排序区间,初始已排序区间只有一个元素(即第一个数据),我们取未排序区间的元素,在已排序的区间中找到合适的位置插入位置插入,并保证已排序区间数据一直有序,重复过程,直到未排序区间中没有元素

运行过程中看得出来,不需要额外的存储空间,所以空间复杂度为0(1),也是原地排序算法

同样值的元素,前后顺序保持不变,是稳定的排序算法

时间复杂度:

最好时间复杂度为O(n)

最坏时间复杂度为O(n2)

平均时间复杂度为O(n2)

代码实现:

<pre style="margin: 0px 0px 15px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px !important; line-height: 1.72222; color: inherit; border-radius: 2px; background: rgb(238, 238, 238); border: 0px; overflow: auto;">// 插入排序,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; // 插入数据
}
}</pre>

六、详解选择排序

选择排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素,即数组第一个元素。在未排序区间找到最小的数据,将其放在已排序区间的末尾

空间复杂度为O(1),选择排序是原地排序算法。

未排序区间的元素和已排序区间的元素相同时,它可以放在已排序区间相同值的前或后,所以为不稳定的排序

时间复杂度:

  1. 最好情况:O(n2)。
  2. 最坏情况:O(n2)。
  3. 平均情况:O(n2)(往数组中插入一个数的平均时间复杂度是O(n),一共重复n次)。

七、各种排序方法的汇总比较

image

八、选择排序和插入排序的时间复杂度相同,都是O(n^2),在实际的软件开发中,为什么我们更倾向于使用插入排序而不是冒泡排序算法呢?

答:它们的元素比较次数以及交换元素的次数都是原始数据的逆序度,是一个固定值,但是从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要3个赋值操作,而插入排序只需要1个,他们 的时间复杂度上都是O(n2),但是为了追求极致的性能,所以首选插入排序算法

结尾

大家不妨试着分析一下其他的几种算法。

看再多遍都不如写一篇来得深刻,建议大家多敲。

相关文章

数据结构与算法学习笔记之写链表代码的正确姿势(下)

数据结构与算法学习笔记之 提高读取性能的链表(上)

数据结构与算法学习笔记之 从0编号的数组

数据结构与算法学习笔记之后进先出的“桶”

数据结构与算法学习笔记之先进先出的队列

数据结构与算法学习笔记之高效、简洁的编码技巧“递归”

以上内容为个人的学习笔记,仅作为学习交流之用。

Dawnzhang公众号.jpg

欢迎大家关注公众号,不定时干货,只做有价值的输出

作者:Dawnzhang
出处:https://www.cnblogs.com/clwydjgs/p/9815690.html

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

推荐阅读更多精彩内容