以关键码序列(503,087,512,061,908,170,897,275,653,426)为例,手工执行以下排序算法,写出每一趟排序结束时的关键码状态: (1)直接插入排序; (2)希尔排序(增量d[1]=5); (3)快速排序; (5)归并排序;
时间: 2023-03-20 15:01:28 浏览: 168
(1) 直接插入排序:
首先将第一个元素(503)看成一个有序序列,然后将后面的元素一个一个插入该序列中。每次插入一个元素,就将该元素与前面有序序列的元素进行比较,找到其正确的位置插入。
第1趟排序结束时的关键码状态:503
第2趟排序结束时的关键码状态:087, 503
第3趟排序结束时的关键码状态:087, 503, 512
第4趟排序结束时的关键码状态:061, 087, 503, 512
第5趟排序结束时的关键码状态:061, 087, 503, 512, 908
第6趟排序结束时的关键码状态:061, 087, 170, 503, 512, 908
第7趟排序结束时的关键码状态:061, 087, 170, 503, 512, 897, 908
第8趟排序结束时的关键码状态:061, 087, 170, 275, 503, 512, 897, 908
第9趟排序结束时的关键码状态:061, 087, 170, 275, 503, 512, 653, 897, 908
第10趟排序结束时的关键码状态:061, 087, 170, 275, 426, 503, 512, 653, 897, 908
(2) 希尔排序(增量d[1]=5):
将序列按照一定的增量分为若干子序列,对每个子序列进行插入排序。然后逐渐缩小增量,继续进行插入排序,直到增量为1时,进行最后一次插入排序即可。
第1趟排序结束时的关键码状态:170, 087, 512, 061, 908, 503, 897, 275, 653, 426
第2趟排序结束时的关键码状态:170, 087, 512, 061, 908, 503, 897, 275, 653, 426
第3趟排序结束时的关键码状态:061, 087, 512, 170, 897, 275, 908, 503, 653, 426
第4趟排序结束时的关键码状态:061, 087, 275, 170, 426, 512, 908, 503, 653, 897
第5趟排序结束时的关键码状态:061, 087, 170, 275, 426, 512, 897, 503, 653, 908
第6趟排序结束时的关键码状态:061, 087, 170, 275, 426, 503, 512, 897, 653, 908
第7趟排序结束时的关键码状态:061, 087, 170, 275, 426, 503, 512, 653, 897, 908
第8趟排序结束时的关
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)