【算法复习1】时间复杂度同为n2冒泡排序 插入排序 选择排序三者分析

在这里插入图片描述

今天 看了极客时间的 数据结构之美的专栏 有感而发 记录一下自己的 笔记 存在主观推断 不保证准确性

交换次数

• 冒泡排序 可能次次都交换 感觉更适合 数组的交换方法 相邻直接进行交换
• 插入排序 也可能次次都交换，感觉更适合链表的方法 中间插入 向后移动
• 选择排序 每轮只用交换一次 但是后面的 有可能换到前面去 ，反而不稳定了，也是适合 链表，但是没有插入排序快。

因为我认为 选择 排序 和 插入排序 相比

• 选择排序是从未排序数据中找到合适的 和 前面的换，打乱了顺序不稳定，链表和数组没有太大区别。
• 插入排序 是从 未排序的数据中 找到合适的 从前面插入，不打乱顺序 更稳定，天生适合 链表的 结构 适合增删改查 节点，

移动赋值操作

冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，选择排序每轮也需要移动一个，适用于 数组连续空间下标访问，但是不稳定

个人感觉 链表适合 插入排序 稳定 适合向后移动 数组适合 冒泡排序和 选择排序，插入排序会出现 大量数据向后移动1位的状况，选择排序会不稳定

评论区大佬的总结

总结 一、排序方法与复杂度归类 （1）几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。 （2）复杂度归类 冒泡排序、插入排序、选择排序 O(n^2) 快速排序、归并排序 O(nlogn) 计数排序、基数排序、桶排序 O(n) 二、如何分析一个“排序算法”？ <1>算法的执行效率 1. 最好、最坏、平均情况时间复杂度。 2. 时间复杂度的系数、常数和低阶。 3. 比较次数，交换（或移动）次数。 <2>排序算法的稳定性 1. 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 2. 稳定性重要性：可针对对象的多种属性进行有优先级的排序。 3. 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。 <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(n^2)。 四、插入排序 插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。 空间复杂度：插入排序是原地排序算法。 时间复杂度： 1. 最好情况：O(n)。 2. 最坏情况：O(n^2)。 3. 平均情况：O(n^2)（往数组中插入一个数的平均时间复杂度是O(n)，一共重复n次）。 稳定性：插入排序是稳定的排序算法。 五、选择排序 选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。 空间复杂度：选择排序是原地排序算法。 时间复杂度：（都是O(n^2)） 1. 最好情况：O(n^2)。 2. 最坏情况：O(n^2)。 3. 平均情况：O(n^2)。 稳定性：选择排序不是稳定的排序算法。 思考 选择排序和插入排序的时间复杂度相同，都是O(n^2)，在实际的软件开发中，为什么我们更倾向于使用插入排序而不是冒泡排序算法呢？ 答：从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个，所以在对相同数组进行排序时，冒泡排序的运行时间理论上要长于插入排序。