UC知道问两个关于排序的问题
来源：百度知道 编辑：UC知道 时间：2024/06/15 19:01:59
1.对下面四个序列快速排序，以序列的第一个元素为基础进行划分，在第一趟划分过程中，元素移动次数最多的序列是：
A。82 75 70 16 10 90 68 23
B。23 10 16 70 82 75 68 90
C。70 75 68 23 10 16 90 82
D。70 75 82 90 23 16 10 68
2.在插入和选择排序中,若初始数据基本反序,应选用:
望详细解答,谢谢!
A。82 75 70 16 10 90 68 23
B。23 10 16 70 82 75 68 90
C。70 75 68 23 10 16 90 82
D。70 75 82 90 23 16 10 68
2.在插入和选择排序中,若初始数据基本反序,应选用:
望详细解答,谢谢!
快速排序：
1.将输入的序列p[m..n]划分成两个非空子序列p[m..k]和p[k+1..n]，使p[m..k]中任一元素的值不大于p[k+1..n]中任一元素的值。
2.对p[m..k]和p[k+1..n]分别重复1和2步骤
3.把最终的有序子序列合并起来。
因此：在第一趟排序后与原来序列元素位置比较如下：
A:23 75 70 16 10 68 82 90
82 75 70 16 10 90 68 23
B:16 10 23 70 82 75 68 90
23 10 16 70 82 75 68 90
C:16 10 68 23 70 75 90 82
70 75 68 23 10 16 90 82
D:68 10 16 23 70 90 82 75
70 75 82 90 23 16 10 68
由此可见应该是D
2.应该选择：选择排序
因为插入排序在反序时：比较的次数和移动数据的次数都是：
选择排序则是比较的次数为O(1)+O(2)+...+O(n-1);
移动数据的次数为0；