UC知道数据结构 排序问题
来源：百度知道 编辑：UC知道 时间：2024/05/22 09:49:41
在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为
（ ）
A．i B．i+1
C．n-i D．n-i+1
我的选择是C为什么答案是D
我是这样分析的：刚开始排序时无序区中有n-1个元素（因为第一个元素是直接选择的），进行一次排序序后无序区中减少一个元素。在进行第i趟排序之前，一共进行了i-1次排序，所以无序区一共有(n-1)-(i-1)=n-i个元素，可是答案是D不明白啊，请指教
目前没有满意的答案，大家踊跃回答啊~~
谢谢1898098的回答
但是你似乎忽略了这样一个事实：在直接选择排序中，是把第一个元素作为有序区的第一个元素，无需比较的啊。
（ ）
A．i B．i+1
C．n-i D．n-i+1
我的选择是C为什么答案是D
我是这样分析的：刚开始排序时无序区中有n-1个元素（因为第一个元素是直接选择的），进行一次排序序后无序区中减少一个元素。在进行第i趟排序之前，一共进行了i-1次排序，所以无序区一共有(n-1)-(i-1)=n-i个元素，可是答案是D不明白啊，请指教
目前没有满意的答案，大家踊跃回答啊~~
谢谢1898098的回答
但是你似乎忽略了这样一个事实：在直接选择排序中，是把第一个元素作为有序区的第一个元素，无需比较的啊。
第一个元素是直接选择的?我不太明白，这个元素是大是小呢？
＝＝＝＝＝＝＝＝＝
一开始肯定是n个无序元素吧。
选第一个元素，把它和其余n-1个元素比较，比如第j个元素最小，这一趟的最后，要把a[1]和a[j]交换。这时候（第二次排序之前），无序区是n-1个元素。
第i次排序前，也就是说有序区选择了i-1个元素，无序区还剩余n-(i-1)个。
如果按你的分析：“刚开始排序时无序区中有n-1个元素”，那么这时有序区就有一个元素。这就意味着第一次排序已经结束了，即将开始第二次排序。而你的理解是此时刚开始第一次排序，与事实不符。所以是第二次排序之前无序区中有n-1个元素。
这样你就应该知道第一次排序之前无序区中有多少个元素了吧，是n个。
第一次排序之前：无序区-------n个 有序区-------0个
第二次排序之前（即第一次排序之后）：无序区-------n-1个 有序区-------1个。
所以答案选D。
简单！
第i趟排序之前，意即已经排了i-1趟，那么，因为每排一趟就会在无序区中取走一个最小数，所以此时一共已经取走了i-1个数，剩下n-(i-1)=n-i+1
读题仔细一点就行了！
按照你说的方法进行计算好像并没有错误，但是从答案上来看，第一次排序之前就剩下的无序元素应该是n，所以个人认为你分析方法不对头。