对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序,最省时间的算法是___________

Question

对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序,最省时间的算法是___________

Answer 1

对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的算法是冒泡排序。

冒泡排序的最好比较次数为n次，最差比较次数为n＾2次，最差比较次数为0次，最差比较次数为n＾2次，最差比较次数为1次，最差比较次数为1次。

快速排序的最好比较次数为nlogn次，最差比较次数为n＾2次，最差比较次数为logn次，最差比较次数为n次，最差比较次数为logn次，最差比较次数为n次。

堆排序的最好比较次数为nlogn次，最差比较次数为nlogn次，最差比较次数为nlogn次，最差比较次数为nlogn次，最差比较次数为1次，最差比较次数为1次。

扩展资料：

冒泡排序（BubbleSort）重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

由于冒泡排序比较是相邻的两个元素，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

Answer 2

是冒泡排序，冒泡排序、快速排序、堆排序的性能比较对照
排序方法 比较次数 移动次数 稳定性 辅助空间
最好 最差 最好 最差 最好 最差
冒泡排序 n n^2 0 n^2 是 1 1
快速排序 nlogn n^2 logn n 否 logn n
堆排序 nlogn nlogn nlogn nlogn 否 1 1

而当待排序列已基本有序时，对冒泡排序来说是最好情况，对快速排序来说就是最差情况，而堆排序则最好最差都一样。因此本题答案是冒泡排序。

Answer 3

快速排序，因为从平均性能而言，快速排序最佳，其所需时间最省