分别使用简单选择排序和归并排序方法对下列关键字进行从小到大排序,写出每一趟的排序序列。 28、15、25、 47、18、 12、55、10
时间: 2023-08-05 22:06:35 浏览: 51
好的,我来分别使用简单选择排序和归并排序对这些关键字进行排序。
首先是简单选择排序,其基本思路是:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
第一趟排序:10 15 25 47 18 12 55 28
第二趟排序:10 12 25 47 18 15 55 28
第三趟排序:10 12 15 47 18 25 55 28
第四趟排序:10 12 15 18 47 25 55 28
第五趟排序:10 12 15 18 25 47 55 28
第六趟排序:10 12 15 18 25 47 55 28
第七趟排序:10 12 15 18 25 28 55 47
经过七趟排序,最终得到的有序序列为:10 12 15 18 25 28 47 55。
接下来是归并排序,其基本思路是:将待排序序列分成若干子序列,每个子序列是有序的,然后再将子序列合并成整体有序的序列。
第一趟排序:(15 28) (25 47) (12 18) (10 55)
第二趟排序:(15 25 28 47) (10 12 18 55)
第三趟排序:(10 12 15 18 25 28 47 55)
经过三趟排序,最终得到的有序序列为:10 12 15 18 25 28 47 55。
相关问题
下列排序方法的时间性能不随记录序列中关键字的分布而改变。 A 简单选择排序 B 希尔排序 C 堆排序 D 归并排序
答案是 C 堆排序。堆排序的时间复杂度是 O(nlogn),不会受到记录序列中关键字的分布而改变。而简单选择排序、希尔排序和归并排序的时间复杂度都会受到记录序列中关键字的分布而改变。简单选择排序的最坏时间复杂度为 O(n^2),在记录序列中关键字分布极端不均匀的情况下,可能会出现最坏情况。希尔排序的时间复杂度介于 O(n) 和 O(n^2) 之间,也会受到记录序列中关键字的分布而改变。归并排序的时间复杂度是 O(nlogn),但需要额外的空间来存储归并后的结果。
使用归并排序方法对下列数18,22,6,42,13,15,18*,2进行排序
好的,我来帮您解答这个问题。
首先,我们使用归并排序方法对这个数列进行排序,具体过程如下:
1. 将数列不断对半拆分,直到每个子序列只剩下一个元素。
拆分后的子序列为:
18 22 6 42 13 15 18* 2
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
18 22 6 42 13 15 18* 2
↓ ↓ ↓ ↓
18 22 6 42
↓ ↓ ↓ ↓
18 22 6 42
↓ ↓
13 15
↓ ↓
18* 2
2. 将相邻的子序列进行合并,合并时比较两个子序列中的元素大小,将较小的元素放在前面。
第一次合并后的序列为:
18 22 6 42 13 15 18* 2
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
18 22 6 42 13 15 18* 2
↓ ↓ ↓ ↓ ↓ ↓
6 18 22 13 15 42 2
↓ ↓ ↓ ↓
6 13 15 18* 2 42
3. 继续合并子序列,直到将整个序列合并为一个有序序列。
最终排序后的序列为:
2 6 13 15 18 18* 22 42
所以,这个数列使用归并排序方法排序后的结果为2、6、13、15、18、18*、22、42。