现有待排序序列{25,84,21,47,15,27,68,35,20},请写出利用归并排序进行排序的过程。
时间: 2024-06-04 12:09:39 浏览: 129
归并排序是一种分治思想的排序算法,其基本思路是将待排序序列分成若干个子序列,对每个子序列进行排序,然后再将已排序的子序列合并成更大的有序序列,直到整个序列有序为止。
下面是利用归并排序对给定序列进行排序的过程:
1. 将待排序序列分成左右两部分,分别为{25,84,21,47}和{15,27,68,35,20}。
2. 对左右两部分分别进行归并排序,得到排好序的左右两个子序列:
- 对左半部分{25,84,21,47}进行排序:
1. 将左半部分继续拆分为两个子序列{25,84}和{21,47},分别进行排序。
2. 对左子序列{25,84}进行排序,得到{25,84}。
3. 对右子序列{21,47}进行排序,得到{21,47}。
4. 将排好序的左右子序列合并成{25,21,47,84}。
- 对右半部分{15,27,68,35,20}进行排序:
1. 将右半部分继续拆分为两个子序列{15,27,68}和{35,20},分别进行排序。
2. 对左子序列{15,27,68}进行排序,得到{15,27,68}。
3. 对右子序列{35,20}进行排序,得到{20,35}。
4. 将排好序的左右子序列合并成{15,20,27,35,68}。
3. 将排好序的左右两个子序列{25,21,47,84}和{15,20,27,35,68}合并成一个有序序列{15,20,21,25,27,35,47,68,84}。
因此,利用归并排序对给定序列进行排序后,得到的有序序列为{15,20,21,25,27,35,47,68,84}。
阅读全文