GESP-C++四级 题库
排序算法是稳定的(Stable Sorting),就是指排序算法可以保证,在待排序数据中有两个相等记录的关键字 R 和 S(R 出现在 S 之前),在排序后的列表中 R 也一定在 S 前。下面关于排序稳定性的描述,正确的是()。
冒泡排序和插入排序都是稳定排序算法。
对整数数组 {4, 1, 3, 1, 5, 2} 进行冒泡排序(将最大元素放到最后),执行一轮之后是 {4, 1, 3, 1, 2, 5} 。
无论初始数组是否有序,选择排序都执行 次比较。( )
选择排序基本思想是每次从未排序的部分中选择最小(或最大)的元素,放到已排序部分的末尾。
每次选择最小元素时,都必须遍历整个未排序的部分,所以是 n^2 次比较。
考虑最坏情况下冒泡排序算法的时间复杂度, T(n)为待排序数字的数目为 n的复杂度,则其递推关系式为 T(n) = T(n - 1) + n ,T(0) = 1 。
对数组 arr[]={4, 3, 1, 5, 2} 进行升序排序,执行第—轮选择排序后数组arr 中的内容是 {1, 4, 3, 5, 2} 。
错误。正确结果应为 {1, 3, 4, 5, 2} 。
插入排序的时间复杂度总是比冒泡排序低。
不完全正确。插入排序在最佳情况下(已经排序的数组)时间复杂度为O(n),而冒泡排序在最佳情况下也为O(n)。但在平均和最坏情况下,插入排序的时间复杂度为O(n^2),与冒泡排序相同。因此,不能说插入排序总是比冒泡排序低。
插入排序算法中,平均时间复杂度是 ,最坏的情况逆序情况下,达到最大时间复杂度。
在最坏的逆序情况下,每一个元素都会被插入到已排好序部分的最前面。
对 int a[]={2,0,2,4,3,1,6} ,执行第一趟选择排序处理后 a 中数据变为 {0,2,2,4,3,1,6} 。( )
