在下列排序算法中，哪几个算法的时间复杂度与初始排序无关()_

小虎牙

自己总结的口诀：选快希堆不稳（是不稳定的排序），

堆归选基均不变（运行时间不发生变化，与初始状态无关）

发表于 2015-12-08 09:42:24 回复(10)

瓜牛77

选堆快希不稳选堆归基不变感觉这样更好记。

发表于 2016-09-20 18:56:24 回复(3)

向宁同桌

题目没有说清楚，冒泡排序如果是没有优化过的，那么就跟初始序列无关

发表于 2016-05-19 16:35:21 回复(4)

陆嘉杰

答案：BDE。选择排序，堆排序，归并排序，基数排序在平均情况，最坏情况，最好情况下的时间复杂度均一致，与初始排序无关。

发表于 2016-02-13 22:57:57 回复(0)

大星星和小猩猩

排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。举个例子：如果Ai = Aj，Ai原来在位置前，排完序后Ai还是要在Aj位置前。

发表于 2018-01-23 17:26:11 回复(0)

永远的树

冒泡排序消耗的时间计算包括：比较和交换；比较次数与元素排列情况无关，但交换次数与元素排列情况有关。

详细参见：算法（第四版）中文版 Robert Sedgewick等著谢路云译人民邮电出版社

P218 表2.5.1

算法	是否稳定	是否为原地排序	时间复杂度	空间复杂度	备注
选择排序	否	是	N²	1
插入排序	是	是	介于N和N²	1	取决于输入元素的排列情况
希尔排序	否	是	NlogN？ N^6/5	1
快速排序	否	是	NlogN	lgN	运行效率由概率提供保证
归并排序	是	否	NlogN	N
堆排序	否	是	NlogN	1
三向快速排序	否	是	介于N和NlogN之间	lgN	运行效率由概率保证，同时取决于输入元素的分布情况

编辑于 2017-11-21 08:23:17 回复(0)

牛客876661689号

快速排序、希尔排序、简单选择排序、堆排序是不稳定的

记忆口诀：“快希选堆不稳定”

（~快些选对~）

＜（＾－＾）＞

发表于 2020-08-10 20:35:00 回复(0)

天行健_地势坤

直接插入排序：

算法思想：将第i个记录插入到前面已经排好序的i - 1个记录中去。
算法要点：

使用监视哨r[0]临时保存带插入记录
从后往前查找应插入的位置
查找与移动用同一循环完成

算法时间复杂度：o(n^2)

折半插入排序：

算法思想：利用折半查找的思想找到需要插入的位置
算法时间复杂度：o(n^2)，虽然减少了查找插入位置的次数，但是移动元素的时间仍未改变

希尔排序：

算法思想：将待排序的关键字序列分成若干个较小的子序列，对子序列进行直接插入排序，使整个待排序序列排好序。
算法时间复杂度：o(n^1.5)

快速排序：

算法思想：从待排序记录中选择一个记录为枢纽，设为K，将其余大于K的记录移动至K的后面，小于K的移动至前面，此过程称为一趟快速排序。当然就是对接下来的两个字表进行相同的操作，直到子表的长度不超过1
算法时间复杂度：o(Knlog2n),K为常数因子，且在所有O(nlogn)复杂度中,快排的K值最小

简单选择排序：

算法思想：
第一趟：从第一个记录开始，通过n-1次关键字比较，从n个记录中选出最小的并和第一个记录交换；
第二趟：从第二个记录开始，通过n-2次关键字比较，从n -1个记录中选出最小的并和第二个记录交换；
...
算法时间复杂度：o(n^2)

堆排序：

算法思想：将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲节点和孩子节点之间的内在关系选择关键字最小的记录。
大根堆：各节点关键字满足：a[i] >= a[2i]并且a[i] >= a[2i + 1]
小根堆：各节点关键字满足：a[i] <= a[2i]并且a[i] <= a[2i+1]
算法时间复杂度：o(nlogn)