对下列四种排序方法,在排序中关键字比较次数同记录初始排列无关的是()_关键字比较的次数与记录的初始排序次序无关的

作者：很楠不爱3 | 2024-02-29 06:11:00

踩

关键字比较的次数与记录的初始排序次序无关的

对下列四种排序方法,在排序中关键字比较次数同记录初始排列无关的是()

A直接插入
B折半插入
C快速排序
D归并排序

直接插入排序很明显，在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；

折半插入排序，比较次数是固定的，与初始排序无关；

快速排序，初始排序不影响每次划分时的比较次数，都要比较n次，但是初始排序会影响划分次数，所以会影响总的比较次数；

归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，所以与初始排序有关。

归并排序
假设二路归并
1234
12 34   2次
2<4 2<3 2次   不用再继续共4次
1 2 3 4 有序

2314
23 14 2次
3<4 3>1 2次   再用2比较
2>1       1次   插入
1 2 3 4 有序共5次

可见归并排序的比较次数就不固定，随着初始状态不同而不同

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/164070