PTA排序易错题 基金按照风险和收益从大到小的排序

仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。 A.对 B.错

原因：常见的最坏的时间复杂度如下第四列，最优是O(NlogN)。 对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。 A.对 B.错 原因：归并趟数为log2n

对N个记录进行简单选择排序，比较次数和移动次数分别为O(N​2)和O(N) A.对 B.错 原因：简单排序遍历并比较最大的（或最小的）仅仅交换头部与最大或最小的位置，因此比较次数和移动次数分别为O(N​2)和O(N)

对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。 A.对 B.错 原因：顺序逆序 时间复杂度为O(N​2)

对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。 A.对 B.错 原因：当元素基本有序时，交换元素元素肯定较少，冒泡和直接插入排序都会较少。

要从50个键值中找出最大的3个值，选择排序比堆排序快。 A.对 B.错 原因：找出元素最大，快速选择就是专门找最大，最小，遍历3遍就解决事情

(neuDS)直接插入排序算法在最好情况下的时间复杂度为O(n)。 A.对 B.错 原因：直接插入与冒泡排序最好都是有序一遍过。

直接选择排序算法在最好情况下的时间复杂度为O（N） A.对 B.错 原因：直接选择算法，无论如何都需要遍历整个数组选择最大的，比来比去都要O(N​2)

快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。 A.对 B.错 原因：没有绝对最快的算法，只有相对好用的场景，而且部分算法基本上空间复杂度都是O1，而快速排序为log2n。

在待排序数据基本有序的情况下，快速排序效果最好。 A.对 B.错

若数据元素序列{ 11，12，13，7，8，9，23，4，5 }是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是： A.冒泡排序 B.选择排序 C.插入排序 D.归并排序 原因：冒泡和选择需要选择最大最小，两边都不是最大最小，直接排除；插入排序符合11，12，13排序符合；归并，看两路归并，13，7不符合，三路也不符合因此只能说插入

数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？ A.冒泡排序 B.选择排序 C.插入排序 D.快速排序 原因：冒泡和选择不符合两边都不是最大最小，直接排除，插入数组开头并未有序，只能是快排

对一组数据{ 2，12，16，88，5，10 }进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能是： A.冒泡排序 B.希尔排序 C.归并排序 D.基数排序

下面四种排序算法中，稳定的算法是： A.堆排序 B.希尔排序 C.归并排序 D.快速排序

在基于比较的排序算法中，哪种算法的最坏情况下的时间复杂度不高于O(NlogN)？ A.冒泡排序 B.归并排序 C.希尔排序 D.快速排序 原因：冒泡,快速都是O(N​2) 归并是O(NlogN)，希尔平均是N1.3，下图比较在2-3之后希尔比归并更大，最坏的情况下，且排序比较是多数的比较，因此选择归并更加合理。 对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？ A.从小到大排好的 B.从大到小排好的 C.元素无序 D.元素基本有序

对N个记录进行归并排序，空间复杂度为： A.O(logN) B.O(N) C.O(NlogN) D.O(N​2 ) 原因：因为考察的是空间复杂度，所以是O(N)

排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法称为： A.插入排序 B.选择排序 C.快速排序 D.归并排序

设有100个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是： A.7 B.10 C.25 D.50 原因：个人小技巧都除以2得到答案，一共除了 27 ，我直接说26 =64 SqList sqList; sqList.length = 0; string tmp; while (tmp != "#"){ cin >> tmp; if (tmp == "#"){ break; } sqList.data[sqList.length++] = tmp; } return sqList;}void swap_num(string &a, string &b){ string tmp = a; a = b; b = tmp;}​void BubbleSort(SqList *sqList){ for (int i = 0; i length ; ++i) { bool flag = false; for (int j = 0; j length -1; j++) { if (sqList->data[j].size() > sqList->data[j+1].size()){ swap_num(sqList->data[j], sqList->data[j+1]); flag = true; } } if (flag == false){ return; } }}​void printList(SqList *sqList){ for (int i = 0; i length; ++i) { cout int data[MAXSIZE]; int length;};SqList initSList(int N){ SqList sqList; sqList.length = 0; int tmp; for (int i = 0; i int tmp = a; a = b; b = tmp;}​void BubbleSort(SqList *sqList,int times){ for (int i = 0; i if (sqList->data[j] > sqList->data[j+1]){ swap_num(sqList->data[j], sqList->data[j+1]); flag = true; } } if (flag == false){ return; } }}​void printList(SqList sqList){ for (int i = 0; i cout int N,times; cin >> N; cin >> times; SqList sqList = initSList(N); BubbleSort(&sqList,times); printList(sqList); return 0;}