第10章内排序
教材中练习题及参考答案
1. 直接插入排序算法在含有n个元素的初始数据正序、反序和数据全部相等时，时间复杂度各是多少？
答：含有n个元素的初始数据正序时，直接插入排序算法的时间复杂度为O(n)。
含有n个元素的初始数据反序时，直接插入排序算法的时间复杂度为O(n2)。
含有n个元素的初始数据全部相等时，直接插入排序算法的时间复杂度为O(n)。
2. 回答以下关于直接插入排序和折半插入排序的问题：
（1）使用折半插入排序所要进行的关键字比较次数，是否与待排序的元素的初始状态有关？
（2）在一些特殊情况下，折半插入排序比直接插入排序要执行更多的关键字比较，这句话对吗？
答：（1）使用折半插入排序所要进行的关键字比较次数，与待排序的元素的初始状态无关。无论待排序序列是否有序，已形成的部分子序列是有序的。折半插入排序首先查插入位置，插入位置是判定树失败的位置（对应外部节点），失败位置只能在判定树的最下两层上。
（2）一些特殊情况下，折半插入排序的确比直接插入排序需要更多的关键字比较，例如，在待排序序列正序的情况下便是如此。
3. 有以下关于排序的算法：
void fun(int a[],int n)
{ int i,j,d,tmp;
d=n/3;
while (true)
{ for (i=d;i<n;i++)
{ tmp=a[i];
j=i-d;
while (j>=0 && tmp<a[j])
{ a[j+d]=a[j];
j=j-d;
}
a[j+d]=tmp;
}
if (d==1) break;
else if (d<3) d=1;
else d=d/3;
}
}
（1）指出fun(a ，n )算法的功能。
（2）当a []={5，1，3，6，2，7，4，8}时，问fun(a ，8)共执行几趟排序，各趟的排序结果是什么？
答：（1）fun(a ，n )算法的功能是采用增量递减为1/3的希尔排序方法对a 数组中元素进行递增排序。
（2）当a []={5，1，3，6，2，7，4，8}时，执行fun(a ，8)的过程如下： d =2：2 1 3 6 4 7 5 8 d =1：1 2 3 4 5 6 7 8 共有两趟排序。 4.  在实现快速排序的非递归算法时，可根据基准元素，将待排序序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log 2n )。
答：由快速排序的算法可知，所需递归工作栈的深度取决于所需划分的最大次数。在排序过程中每次划分都把整个待排序序列根据基准元素划分为左、右两个子序列，然后对这两个子序列进行类似的处理。设S (n )为对n 个记录进行快速排序时平均所需栈的深度，则：
S (n )=
∑∑
-===
-+-1
1
)(2
))()1((1
n i n
k i S n
k n S k S n
当n =1时，所需栈空间为常量，由此可推出：S (n )=O(log 2n )。
实际上，在快速排序中下一趟首先对较短子序列排序，并不会改变所需栈的深度，所以所需栈的深度仍为O(log 2n )。
5. 将快速排序算法改为非递归算法时通常使用一个栈，若把栈换为队列会对最终排序结果有什么影响？
答：在执行快速排序算法时，用栈保存每趟快速排序划分后左、右子区间的首、尾地址，其目的是为了在处理子区间时能够知道其范围，这样才能对该子区间进行排序，但这与处理子区间的先后顺序没什么关系，而仅仅起存储作用（因为左、右子区间的处理是独立的）。因此，用队列同样可以存储子区间的
首、尾地址，即可以取代栈的作用。在执行快速排序算法时，把栈换为队列对最终排序结果不会产生任何影响。
6. 在堆排序、快速排序和二路归并排序中：
（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？
（3）若只从最坏情况下的排序时间考虑，则不应选取哪种排序方法？
答：（1）若只从存储空间考虑，则应首先选取堆排序（空间复杂度为O(1)），其次选取快速排序（空间复杂度为O(log 2n )），最后选取二路归并排序（空间复杂度为O(n )）。
（2）若只从排序结果的稳定性考虑，则应选取二路归并排序，其他两种排序方法是不
稳定的。
（3）若只从最坏情况下的排序时间考虑，则不应选取快速排序方法。因为快速排序方法最坏情况下的时间复杂度为O(n2)，其他两种排序方法在最坏情况下的时间复杂度为O(n log2n)。
7. 如果只想在一个有n个元素的任意序列中得到其中最小的第k（k<<n）个元素之前的部分排序序列，那么最好采用什么排序方法？为什么？例如有这样一个序列（57，40，38，11，13，34，48，75，6，19，9，7），要得到其第4个元素（k=4）之前的部分有序序列，用所选择的算法实现时，要执行多少次比较？
答：采用堆排序最合适，建立初始堆（小根堆）所花时间不超过4n，每次选出一个最小元素所花时间为log2n，因此得到第k个最小元素之前的部分序列所花时间大约为4n+k log2n，而冒泡排序和简单选择排序所花时间为kn。
对于序列（57，40，38，11，13，34，48，75，6，19，9，7），形成初始堆（小根堆）并选最小元素6，需进行18次比较；选次小元素7时，需进行5次比较；再选元素9时，需进行6次比较；选元素11时，需进行4次比较，总共需进行33次比较。整个过程如图10.2所示。
8. 基数排序过程中用队列暂存排序的元素，是否可以用栈来代替队列？为什么？
答：不能用栈来代替队列。
基数排序是一趟一趟进行的，从第2趟开始必须采用稳定的排序方法，否则排序结果可能不正确，若用栈代替队列，这样可能使排序过程变得不稳定。
9.线性表有顺序表和链表两种存储方式，不同的排序方法适合不同的存储结构。对于常见的内部排序方法，说明哪些更适合于顺序表？哪些更适合于链表？哪些两者都适合？
答：更适合于顺序表的排序方法有希尔排序、折半插入排序、快速排序、堆排序和归并排序。
更适合于链表的排序方法是基数排序。
两者都适合的排序方法有直接插入排序、冒泡排序和简单选择排序。
10. 设一个整数数组-1]中存有互不相同的n个整数，且每个元素的值均在1～n 之间。设计一个算法在O(n)时间内将a中元素递增排序，将排序结果放在另一个同样大小的数组b中。
解：对应的算法如下：
void fun(int a[],int n,int b[])
{ int i;
for (i=0;i<n;i++)
b[a[i]-1]=a[i];
}
11. 设计一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。
解：置i的初值为0，先从后向前从无序区-i-1]归位一个最小元素R[i]到有序区R[0..i-1]，再从前向后从无序区-i-1]归位一个最大元素到有序区-1]。当某趟没有元素交换时，则结束；否则将i增加1。对应的算法如下：
void DBubbleSort(RecType R[],int n) //对-1]按递增序进行双向冒泡排序
{ int i=0,j;
bool exchange=true; //exchange标识本趟是否进行了元素交换
while (exchange)
{ exchange=false;
for (j=n-i-1;j>i;j--)
if (R[j].key<R[j-1].key) //由后向前冒泡小元素
{ exchange=true;
swap(R[j],R[j-1]); //R[j]和R[j-1]交换
}
for (j=i;j<n-i-1;j++)
if (R[j].key>R[j+1].key)  //由前向后冒泡大元素
{ exchange=true;
swap(R[j],R[j+1]); //R[j]和R[j+1]交换
}
if (!exchange) return;
i++;
}
}
12. 假设有n个关键字不同的记录存于顺序表中，要求不经过整体排序而从中选出从大到小顺序的前m（m<<n）个元素。试采用简单选择排序算法实现此选择过程。
解：改进后的简单选择排序算法如下：
void SelectSort1(RecType R[],int n,int m)
{ int i,j,k;
for (i=0;i<m;i++) //做第i趟排序
{ k=i;
for (j=i+1;j<n;j++) //在当前无序区-1]中选key最大的R[k]
if (R[j].key>R[k].key)
k=j; //k记下目前到的最大关键字所在的位置
if (k!=i)
swap(R[i],R[k]); //交换R[i]和R[k]
}
}
13. 对于给定的含有n元素的无序数据序列（所有元素的关键字不相同），利用快速排序方法求这个序列中第k（1≤k≤n）小元素的关键字，并分析所设计算法的最好和平均时间复杂度。
数据结构与算法第二版课后题答案解：采用快速排序思想求解，当划分的基准元素为R[i]时，根据i与k的大小关系再在相应的子区间中查。对应的算法如下：
KeyType QuickSelect(RecType R[],int s,int t,int k) //在]序列中第k小的元素{ int i=s,j=t;
RecType tmp;
if (s<t)  //区间内至少存在2个元素的情况
{ tmp=R[s]; //用区间的第1个记录作为基准
while (i!=j) //从区间两端交替向中间扫描，直至i=j为止
{ while (j>i && R[j].key>=tmp.key)
j--; //从右向左扫描，第1个关键字小于tmp的R[j]
R[i]=R[j]; //将R[j]前移到R[i]的位置
while (i<j && R[i].key<=tmp.key)
i++; //从左向右扫描，第1个关键字大于tmp的R[i]
R[j]=R[i]; //将R[i]后移到R[j]的位置
}
R[i]=tmp;
if (k-1==i) return R[i].key;
else if (k-1<i) return QuickSelect(R,s,i-1,k); //在左区间中递归查
else return QuickSelect(R,i+1,t,k); //在右区间中递归查}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。