对于一个初始无序的关键字序列,在下面的排序方法中()第一趟排序结束后,一定能将序列中的某个元素在最终有序序列中的位置确定下来

①直接插入排序 ②冒泡排序 ③简单选择排序 ④堆排序 ⑤快速排序 ⑥归并排序

答案:

C、②③④⑤

请先 登录 后评论

1 个回答

亚里士德
擅长:互联网

冒泡排序:这个应该是我们在学习编程的时候学习的最简单的一个排序算法了。排序规则就是,从第一个和第二个元素开始,依次两个两个进行比较(1和2比较完,就比较2和3),把大的(或者小的)往后面放。所以到第一趟排完过后一定能把大的(或者最小的)移动到最后去,固定在这里。特点是一趟会和所有数据进行比较。

简单选择排序:简单记忆就是从还所有的没有比较的数据中找(选择)一个最小的和当前比较,比较成功就进行交换。简单规则是:从第一个元素开始,和后面所有的元素进行一次比较,在后面所有元素中找到比当前元素小的,而且是是最小的,如果找到了,就把这个最小的和第一个元素交换位置,然后再依次第二个元素,去后面找。所以按照这样来,第一趟一定能把最小的元素固定在第一个位置上。特点是一趟会和所有数据进行比较。

堆排序:需要借助二叉树(就这么记忆就可以了)。把一行要排序的数据,构建成一个二叉树(完全二叉树的形状,值的放置其实也不能随便,要先从左到右再从上到下的依次放置值),然后再把每一棵子树中,不断的把最大的孩子节点交换到根上面去,第一次所有子树都交换完后,最大的那一个一定在整棵树的根上面。然后把它拿下来和二叉树中最下一层的最右边(简称右下角)的节点进行交换值,并把右下角这个节点断开二叉树关联。第二次(趟)所有子树比较完毕后,把找出来的最大的和最底层的倒数第二个值进行交换。这么比较交换下去,最后就可以比较出顺序来。所以如果这么找,很明显第一趟排序一定可以将最大的找出来。

快速排序:这个老朋友了,考了很多次了,这个一趟之后可以把一个数交换到正确的位置上去固定了(但是在第一趟完成之前无法确定这个值的位置具体会固定在哪里),详细过程可以看一下这一题:www.z21.org/question/77


另外两个:

直接插入排序:这个应该也是最简单的排序之一了。顾名思义,它的第一趟执行顺序是:第一个数作为基准,往后面去找比它小的,一旦找到一个比当前元素小的,就立马把这个小的插入到第一个位置上去,后面的元素往后移动就行了。然后以第二个元素为依据,往后面找比它小的。后面的选择出来的元素就需要和前面的排好序的元素进行比较,找到合适的位置插入。如此往下就能完成排序。这个第一趟排序可能(大概率)不会对每一个元素进行比较,所以可能无法确定一个最小或者最大值的一个可以确定固定位置的值。

归并排序:这个其实也简单,不过可能不能顾名思义了,如果翻译成合并排序、并入排序、融入排序可能更好理解。过程是:把一个要排序的序列平均分成两段,对这两段分别再进行归并排序。不断的拆分,然后把子序列排序,然后把子序列合并,合并到最后就可以得到一个排好序的序列。这个第一趟排序之后只能排好其中一个子序列,而且这个排好的子序列在后面还很有可能在中间前后排上新的数据。所以一趟排序也没有完全对比所有数据,所以它也不能确定一个位置。(其实也是常考的算法中的分治法)

至于它们的时间复杂度,请自行去查找记忆了(或者其他题目也有)。

请先 登录 后评论