设待排序的关键字序列为(15, 21, 6, 30, 23, 6', 20, 17),若使用直插排序法,需要排序()趟,第三趟的结果为()。(每个关键字以两个空格分隔,,单引号为英文状态下的符号)。 第1空 第2空
时间: 2024-06-13 17:08:20 浏览: 15
设待排序的关键字序列为(15, 21, 6, 30, 23, 6', 20, 17),若使用直插排序法,需要排序4趟,第三趟的结果为(6 6' 15 21 23 30 20 17)。
解释如下:
第一趟排序:(15 21 6 30 23 6' 20 17) -> (15 21 6 30 23 6' 20 17)
第二趟排序:(15 21 6 30 23 6' 20 17) -> (6 15
相关问题
设待排序的关键字序列为(15, 21, 6, 30, 23, 6', 20, 17),若使用冒泡排序方法,需要排序()趟,第三趟的结果为()。(每个关键字以两个空格分隔,单引号为英文状态下的符号, 如:6 23 6' 20 )
使用冒泡排序方法,需要排序 n-1 趟,n 为关键字序列的长度,即 7 趟。
第三趟的排序过程为:
第一次比较:15 21 6 30 23 6' 20 17,无需交换;
第二次比较:15 21 6 30 23 6' 20 17,需要交换 21 和 6,得到 15 6 21 30 23 6' 20 17;
第三次比较:15 6 21 30 23 6' 20 17,无需交换;
第四次比较:15 6 21 30 23 6' 20 17,需要交换 30 和 23,得到 15 6 21 23 30 6' 20 17;
第五次比较:15 6 21 23 30 6' 20 17,需要交换 30 和 6',得到 15 6 21 23 6' 30 20 17;
第六次比较:15 6 21 23 6' 30 20 17,需要交换 30 和 20,得到 15 6 21 23 6' 20 30 17;
第七次比较:15 6 21 23 6' 20 30 17,需要交换 30 和 17,得到 15 6 21 23 6' 20 17 30。
因此,第三趟的结果为:15 6 21 23 6' 20 17 30。
{15,21,6,30,23,6',20,17}采用快速排序法
快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行。具体步骤如下:
1. 选择一个基准元素(pivot),通常选择第一个元素作为基准元素;
2. 将待排序序列划分为两个子序列,使得所有小于基准元素的元素都位于基准元素的左边,所有大于基准元素的元素都位于基准元素的右边;
3. 对左右两个子序列分别进行快速排序,直到所有子序列的长度都为1,排序完成。
按照快速排序算法的步骤,对给定序列{15,21,6,30,23,6',20,17}进行排序的过程如下:
1. 选择第一个元素15为基准元素;
2. 从右向左扫描,找到第一个小于15的元素,将其移到15的左边,位置为1,即序列变为{6,21,15,30,23,6',20,17};
3. 从左向右扫描,找到第一个大于15的元素,将其移到15的右边,位置为3,即序列变为{6,6',15,30,23,21,20,17};
4. 对左右两个子序列{6,6',15,30,23}和{21,20,17}分别进行快速排序。
对子序列{6,6',15,30,23}进行排序:
1. 选择第一个元素6为基准元素;
2. 从右向左扫描,找到第一个小于6的元素,将其移到6的左边,位置为0,即序列不变;
3. 对左右两个子序列{6}和{6',15,30,23}分别进行快速排序。
对子序列{6',15,30,23}进行排序:
1. 选择第一个元素6'为基准元素;
2. 从右向左扫描,找到第一个小于6'的元素,将其移到6'的左边,位置为0,即序列不变;
3. 对左右两个子序列{6'}和{15,30,23}分别进行快速排序。
对子序列{15,30,23}进行排序:
1. 选择第一个元素15为基准元素;
2. 从右向左扫描,找到第一个小于15的元素,将其移到15的左边,位置为0,即序列不变;
3. 对左右两个子序列{15}和{30,23}分别进行快速排序。
对子序列{30,23}进行排序:
1. 选择第一个元素30为基准元素;
2. 从右向左扫描,找到第一个小于30的元素,将其移到30的左边,位置为0,即序列不变;
3. 对左右两个子序列{30}和{23}分别进行快速排序。
子序列{30}已经有序,不需要排序。
子序列{23}已经有序,不需要排序。
左右两个子序列都已排序完成,将它们合并起来得到子序列{23,30}。
左右两个子序列都已排序完成,将它们合并起来得到子序列{15,23,30}。
左右两个子序列都已排序完成,将它们合并起来得到子序列{6',15,23,30}。
左右两个子序列都已排序完成,将它们合并起来得到子序列{6,6',15,23,30}。
对子序列{21,20,17}进行排序:
1. 选择第一个元素21为基准元素;
2. 从右向左扫描,找到第一个小于21的元素,将其移到21的左边,位置为1,即序列变为{17,20,21};
3. 对左右两个子序列{17}和{20,21}分别进行快速排序。
子序列{17}已经有序,不需要排序。
对子序列{20,21}进行排序:
1. 选择第一个元素20为基准元素;
2. 从右向左扫描,找到第一个小于20的元素,将其移到20的左边,位置为0,即序列不变;
3. 对左右两个子序列{20}和{21}分别进行快速排序。
子序列{20}已经有序,不需要排序。
子序列{21}已经有序,不需要排序。
左右两个子序列都已排序完成,将它们合并起来得到子序列{20,21}。
左右两个子序列都已排序完成,将它们合并起来得到子序列{17,20,21}。
左右两个子序列都已排序完成,将它们合并起来得到最终的有序序列{6,6',15,17,20,21,23,30}。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)