关于数据结构排序算法的问题

Question

插入排序、选择排序、冒泡排序、基数排序、堆排序的算法中其比较次数与初始数据集顺序无关的是？请说明理由。

Answer 1

选择排序

插入排序：每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。

选择排序：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数
据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情
况下将快于冒泡排序。

冒泡排序：在最优情况下只需要经过n-1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。
堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。

基数排序：在程序中采用的是以数值的十进制位分解，然后对空间采用一次性分配，因此它需要较多的辅助空间(10*n+10), （但我们可以进行其它分解，如以一个字节分解，空间采用链表将只需辅助空间n+256）。基数排序的时间是线性的(即O(n))。由此可见，基数排序非常吸引人，但它也不是就地排序，若节点数据量大时宜改为索引排序。但基数排序有个前提，要关键字能象整型、字符串这样能分解，若是浮点型那就不行了。

Answer 2

选择排序。
选择排序的算法原理是：第一趟从n个待排关键字中找出最小的关键字放到第一个位置，如果要找到最小关键字则必须所有元素都进行比较，所以第一趟要比较n-1次；第二趟从剩下的n-1的元素中再通过n-2次的比较找出最小的元素…………以此类推，不管初始有没有序，它都一共要进行n-1趟排序共n(n-1)/2次比较，时间复杂度始终是O（n平方）
至于其他的，拿插入排序举例：插入排序的基本思想是每次将一个待排的记录按其关键字大小插入到前面已经排好序的子序列中。试想，如果已经排好序的子序列是123，待排记录为45，插入4时，只要和3比较一次就知道排在3后面，对5排序时只要与4比较一次就知道该排在4后面，共比较2次。如果已经排好序的子序列是234，待排记录为15，插入1时，它要从后往前依次比较3次才能找到自己的位置，同样对5排序时只要与4比较一次，共比较4次。由上例可知，插入排序会随着初始数据集的顺序不同而比较次数不同。
BTW，基数排序不是基于关键字比较的排序算法。
纯手打，望采纳，不清楚还可共同探讨。追问

嗯，回答的很好，不过，你对插入排序的举例中有一点我不太清楚：就是你最后的结论“由上例可知，插入排序会随着初始数据集的顺序不同而比较次数不同。”这句话中的初始数据集的顺序，你的意思是123这个顺序与234这个顺序不同？我理解的“初始数据集的顺序不同”的意思是这样的：比如说123与132或者321等，而不是123与234的不同，我理解的对吗？

追答

我的意思不是123这个顺序与234这个顺序不同，而是整个数据集合12345的顺序不同，你可以这样理解：初始有序序列为0，第一次的插入顺序是12345，第二次插入的顺序是23415，它们的比较次数不同。 这样有没有更好理解一点？你的理解是对的，是我的例子没有说清楚，不好意思啊OWO

本回答被提问者和网友采纳

Answer 3

来这看的是不是都是sdu的...我咋觉得选择排序可以及时终止而最好情况下n-1呢？？？？