空间复杂度为o(1)的排序算法（空间复杂度 排序）

本篇文章给大家谈谈空间复杂度为o(1)的排序算法，以及空间复杂度 排序对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、排序算法的时间复杂度和空间复杂度
• 2、数据结构(八)排序
• 3、冒泡排序、插入排序、选择排序时间复杂度都是O(n2)
• 4、排序算法总结
• 5、【讨论】哪种排序算法的平均复杂性最优？

排序算法的时间复杂度和空间复杂度

时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。空间复杂度：庆卖就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

1、时间复杂度

时间复杂度可以认为是对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

常见的时间复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n2)。

时间复杂度O(1)：算法中语句执行次数为一个常数，则时间复杂度为O(1)。

2、空间复杂度

空间复杂度是指算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数。

空间复杂度O(1)：当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改誉段逗变时，可表示为O(1)。

空间复杂度O(log2N)：当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)。     燃宽  

空间复杂度O(n)：当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n)。

经处理后的数据便于筛选和计算，大大提高了计算效率。对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的，不允许混淆不清。

[img]

数据结构(八)排序

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程

算法的稳定性：对于相同关碰颤键字 使用某一排序算法后不改变其相对位置，则称该算法是稳定的

对任意n个关键字排序比较次数至少为

每次将一个待排序记录按其关键字大小插入到前面已排好的序列的子序列中，直到全部记录插入完成

算法空间复杂度为O(1)，时间复杂度为O(n 2 )

先⽤折半查找找到应该插⼊的位置，再移动元素

算法时间复杂度为O(n 2 )

将排序分割成若干的特殊子表，对各个子表进行直接插入排序，缩小增量d，重复上述过程，直到d=1为止

算法时间复杂度为O(n 2 )

算法时间复杂度为O(n 2 )

算法时间复杂度为O(n 2 )，空间复拍吵绝杂度O(递归层数袭姿)

但平均时间复杂度O(nlog 2 n)

选择排序：每一趟在待排元素中选取关键字最小的元素加入有序子序列

算法时间复杂度为O(n 2 )

n个关键字序列 称为堆

思路：把所有⾮终端结点都检查⼀遍，是否满⾜⼤根堆的要求(根≥左、右)，如果不满⾜，则将当前结点与更⼤的⼀个孩⼦互换

时间复杂度O(nlog 2 n)

关键字对比次数不超过4n

归并：把两个或多个已经有序的序列合并成一个

n个记录可视为n个有序子表，两两归并，直到得到长度为n的有序表

n个元素归并并排序，需要归并 躺

时间复杂度O(nlog 2 n) ，空间复杂度为O(n)

基数排序不基于比较和移动排序，而基于关键字各位的大小进行排序

递减序列过程：

空间复杂度O(r),时间复杂度O(d(m+n))

使用归并排序，最小只需在内存中分配3块大小的缓冲区，即可对任意一个大文件进行排序

归并排序要求各个子序列有序，每次读入两个块内容进行内部排序后写回磁盘

外部排序的时间开销=读写外村时间+内部排序时间+内部归并时间

读写磁盘次数=32*3+32=128次读写，其中3为归并躺数，可以采用多路归并减小归并趟数，即减小IO次数

对于k叉树(k路归并)，若树高为h，

败者树如比赛图，可以视为一颗完全二叉树

对于k路归并使用败者树选出最小元素需要比较 次

用于内部排序的内存工作区WA可容纳l个记录，则每个初始归并段也只能包含l个记录，若文件右n个记录，则归并段数量

使用置换排序可以摆脱这个限制

归并过程中的I/O次数=归并数的WPL 2*

对于k叉归并，段数量无法构成严格k叉归并树，则需要补充n个长度为0的虚段，再进行k叉哈夫曼树的构造

初始归并段数量+虚段数量=n 0

若

则补充(k-1)-u个虚段

冒泡排序、插入排序、选择排序时间复杂度都是O(n2)

(相邻元素交换顺序）

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)， 是一个原地排序算法。

第二，冒泡排序是稳定的排序算法吗? 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有 相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以 冒泡排序是稳定的排序算法。

第三，冒泡排序的时间复杂度是多少?

最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以 最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n 次冒泡操作，所以最坏情况时间复杂度为O(n2)。

（第一个数是排序好的和后面是无序的数字，左边是排序好的，右边是没排序好的，从右边拿第一个数和左边倒叙循环判断插入到指定位置）

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

第一，插入排序是原地排序算法吗?

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

第二，插入排序是稳定的排序算法吗? 在插入排序中，对于值相同的元明圆素，我们可以稿档选择将后面出现的元素，插入到前面出现元素的后 面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。 第三，插入排序的时间复杂度是多少? 如果要排序键槐乱的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里 面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复 杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。 如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数

2

据，所以最坏情况时间复杂度为O(n2)。 还记得我们在数组中插入一个数据的平均时间复杂度是多少吗?没错，是O(n)。所以，对于插入排 序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复 杂度为O(n2)。

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

选择排序是一种不稳定的排序算法。

排序算法总结

排序算法是什么?有多少种?排序算法总结又是怎样?以下是为您整理的排序算法总结，供您参考!

【排序算法总结】

排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。

排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。

稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。

以下来总结常用的排序算法，加深对排序的理解。

冒泡排序

原理

俩俩比较相邻记录的排序码，若发生逆序，则交旅派配换;有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。

性能

时间复杂度为O(N^2)，空间复杂度为O(1)。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。

优化

若初始序列就是排序好的，对于冒泡排序仍然还要比较O(N^2)次，但无交换次数。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。

代码

　 　插入排序

原理

依次选择一个待排序的数据，插入到前边已排好序的序列中。

性能

时间复杂度为O(N^2)，空间复杂度为O(1)。算法是稳定的，比较次数和交换次数都与初始序列有关。

优化

直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。

折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至O(NlogN)，排序是稳定的，但排序的比较次数与初始序列无关，总是需要foor(log(i))+1次排序比较。

使用场景

当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。

代码

希尔排拆指序

原理

插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：

插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。

但插入排序在每次往前插入时只能将数据移动一位，效率比较低。

所以希尔排序的思想是：

先是取一个合适的gap

缩小间隔gap，例如去gap=ceil(gap/2)，重复上述子序列划分和排序

直到，最后gap=1时，将所有元素放在同一个序列中进行插入排序为止。

性能

开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点;其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。

代码

选择排序

原理

每次从未排序的序列中找到最小值，记录并最后存放到已排序序羡碰列的末尾

性能

时间复杂度为O(N^2)，空间复杂度为O(1)，排序是不稳定的(把最小值交换到已排序的末尾导致的)，每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。

代码

快速排序

原理

分而治之思想：

Divide：找到基准元素pivot，将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1…q]，左边的元素都比基准小，右边的元素都比基准大;

Conquer：对俩个划分的数组进行递归排序;

Combine：因为基准的作用，使得俩个子数组就地有序，无需合并操作。

性能

快排的平均时间复杂度为O(NlogN)，空间复杂度为O(logN)，但最坏情况下，时间复杂度为O(N^2)，空间复杂度为O(N);且排序是不稳定的，但每次都能确定一个元素所在序列中的最终位置，复杂度与初始序列有关。

优化

当初始序列是非递减序列时，快排性能下降到最坏情况，主要因为基准每次都是从最左边取得，这时每次只能排好一个元素。

所以快排的优化思路如下：

优化基准，不每次都从左边取，可以进行三路划分，分别取最左边，中间和最右边的中间值，再交换到最左边进行排序;或者进行随机取得待排序数组中的某一个元素，再交换到最左边，进行排序。

在规模较小情况下，采用直接插入排序

代码

归并排序

原理

分而治之思想：

Divide：将n个元素平均划分为各含n/2个元素的子序列;

Conquer：递归的解决俩个规模为n/2的子问题;

Combine：合并俩个已排序的子序列。

性能

时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。

优化

优化思路：

在规模较小时，合并排序可采用直接插入;

在写法上，可以在生成辅助数组时，俩头小，中间大，这时不需要再在后边加俩个while循环进行判断，只需一次比完。

代码

堆排序

原理

堆的性质：

是一棵完全二叉树

每个节点的值都大于或等于其子节点的值，为最大堆;反之为最小堆。

堆排序思想：

将待排序的序列构造成一个最大堆，此时序列的最大值为根节点

依次将根节点与待排序序列的最后一个元素交换

再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列

性能

时间复杂度为O(NlogN)，空间复杂度为O(1)，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。

使用场景

想知道最大值或最小值时，比如优先级队列，作业调度等场景。

代码

计数排序

原理

先把每个元素的出现次数算出来，然后算出该元素所在最终排好序列中的绝对位置(最终位置)，再依次把初始序列中的元素，根据该元素所在最终的绝对位置移到排序数组中。

性能

时间复杂度为O(N+K)，空间复杂度为O(N+K)，算法是稳定的，与初始序列无关，不需要进行比较就能排好序的算法。

使用场景

算法只能使用在已知序列中的元素在0-k之间，且要求排序的复杂度在线性效率上。

代码

桶排序

原理

根据待排序列元素的大小范围，均匀独立的划分M个桶

将N个输入元素分布到各个桶中去

再对各个桶中的元素进行排序

此时再按次序把各桶中的元素列出来即是已排序好的。

性能

时间复杂度为O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空间复杂度为O(N+M)，算法是稳定的，且与初始序列无关。

使用场景

算法思想和散列中的开散列法差不多，当冲突时放入同一个桶中;可应用于数据量分布比较均匀，或比较侧重于区间数量时。

基数排序

原理

对于有d个关键字时，可以分别按关键字进行排序。有俩种方法：

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序

LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

性能

时间复杂度为O(d*(N+K))，空间复杂度为O(N+K)。

　 　总结

以上排序算法的时间、空间与稳定性的总结如下：

【讨论】哪种排序算法的平均复杂性最优？

快速排序啊！族唤！袭绝！！拍穗姿

平均复杂度O(nlogn)，已被证明O(nlogn)是基于关键字比较的排序算法中最低的时间复杂度！！！

满意望采纳谢谢！！！

关于空间复杂度为o(1)的排序算法和空间复杂度 排序的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。