给出关键字序列{4,5,1,2,8,6,7,3,10,9}采用直接插入排序时各趟的结果。
时间: 2024-03-18 11:35:45 浏览: 30
以下是关键字序列{4,5,1,2,8,6,7,3,10,9}采用直接插入排序时各趟的结果:
第1趟:4
第2趟:4, 5
第3趟:1, 4, 5
第4趟:1, 2, 4, 5
第5趟:1, 2, 4, 5, 8
第6趟:1, 2, 4, 5, 6, 8
第7趟:1, 2, 4, 5, 6, 7, 8
第8趟:1, 2, 3, 4, 5, 6, 7, 8
第9趟:1, 2, 3, 4, 5, 6, 7, 8, 10
第10趟:1, 2, 3, 4, 5, 6, 7, 8, 9, 10
相关问题
设有一组关键字(5, 3, 7, 8, 6, 1, 4, 2) (1)使用直接插入排序算法将1插入到有序区时,1依次与哪些元素进行比较 (2)使用希尔排序算法进行排序时,写出每一次排序循环得到的序列,直到排序结束 (3)写出第一次快速排序
(1) 在使用直接插入排序算法将1插入到有序区时,1会依次与序列中的元素进行比较,直到找到合适的插入位置为止。比较的顺序分别为:5 -> 3 -> 7 -> 8 -> 6 -> 1。
(2) 使用希尔排序算法进行排序时,每一次排序循环都会将序列分成若干个子序列,每个子序列进行插入排序。希尔排序的核心在于定义一个增量序列,每次排序循环按照增量序列对子序列进行排序,直到增量为1时完成整个排序过程。
以增量序列为(4, 2, 1)为例,开始时将序列分成4个子序列:
(5, 6), (3, 1), (7, 4), (8, 2)
对每个子序列进行直接插入排序,得到:
(5, 1, 6, 3), (7, 2, 4, 8)
再按照2的增量进行排序,将子序列变为:
(5, 1, 4, 2, 6, 3, 7, 8)
最后按照1的增量进行排序,完成整个排序过程。
(3) 第一次快速排序的过程如下:
取序列的第一个元素5作为枢轴,将序列分为左右两部分:
左边部分:3, 1, 4, 2
右边部分:6, 8, 7
以左边部分为例,取第一个元素3作为枢轴,将序列分为左右两部分:
左边部分:1, 2
右边部分:4
以右边部分为例,取第一个元素6作为枢轴,将序列分为左右两部分:
左边部分:8, 7
右边部分:无
最终得到的序列为 1, 2, 3, 4, 5, 8, 7, 6。
设待排序的关键字序列为{12,2,16,30,28,10,16*,20,6,18},试分别写出使用以下排序方法,每趟排序结束后关键字序列的状态。 ① 直接插入排序 ② 希尔排序(增量选取5,3,1) ③ 冒泡排序 ④ 快速排序 ⑤ 简单选择排序
好的,我来给你写出每种排序方法每趟排序后关键字序列的状态:
① 直接插入排序
第1趟排序:{2,12,16,30,28,10,16*,20,6,18}
第2趟排序:{2,12,16,30,28,10,16*,20,6,18}
第3趟排序:{2,12,16,30,28,10,16*,20,6,18}
第4趟排序:{2,12,16,28,30,10,16*,20,6,18}
第5趟排序:{2,10,12,16,28,30,16*,20,6,18}
第6趟排序:{2,10,12,16,16*,28,30,20,6,18}
第7趟排序:{2,6,10,12,16,16*,28,30,20,18}
第8趟排序:{2,6,10,12,16,16*,18,28,30,20}
第9趟排序:{2,6,10,12,16,16*,18,20,28,30}
② 希尔排序(增量选取5,3,1)
第1趟排序:{10,2,16,20,6,12,16*,28,18,30}
第2趟排序:{6,2,16,18,10,12,16*,20,28,30}
第3趟排序:{2,6,10,12,16,16*,18,20,28,30}
③ 冒泡排序
第1趟排序:{2,12,16,28,10,16*,20,6,18,30}
第2趟排序:{2,12,16,10,16*,20,6,18,28,30}
第3趟排序:{2,12,10,16*,6,18,16,20,28,30}
第4趟排序:{2,10,12,6,16*,16,18,20,28,30}
第5趟排序:{2,10,6,12,16*,16,18,20,28,30}
第6趟排序:{2,6,10,12,16*,16,18,20,28,30}
第7趟排序:{2,6,10,12,16*,16,18,20,28,30}
④ 快速排序
第1趟排序:{12,2,16,6,10,16*,20,18,28,30}
第2趟排序:{6,2,10,12,16,16*,20,18,28,30}
第3趟排序:{2,6,10,12,16,16*,18,20,28,30}
⑤ 简单选择排序
第1趟排序:{2,12,16,30,28,10,16*,20,6,18}
第2趟排序:{2,6,16,30,28,10,16*,20,12,18}
第3趟排序:{2,6,10,30,28,16*,16,20,12,18}
第4趟排序:{2,6,10,12,28,16*,16,20,30,18}
第5趟排序:{2,6,10,12,16*,28,16,20,30,18}
第6趟排序:{2,6,10,12,16*,16,28,20,30,18}
第7趟排序:{2,6,10,12,16*,16,18,20,30,28}
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)