数据结构基础--排序

1-1对N个记录进行堆排序,需要的额外空间为O(N)。

这是错的,其实只需要记录temp的一个,也就是O(1),这里给个统计好的表

1-2对N个记录进行简单选择排序,比较次数和移动次数分别为O(N2)和O(N)。

这个对的,选择排序的时间基本都浪费在比较上了。。。

1-3希尔排序是稳定的算法。 (1分)

最不稳定的还差不多

1-5对N个记录进行归并排序,归并趟数的数量级是O(NlogN)。

上面总结的表里给了

2-1对一组包含10个元素的非递减有序序列,采用直接插入排序排成非递增序列,其可能的比较次数和移动次数分别是

直接插入排序每回合的比较次数和元素移动次数等于其原始位置和插入位置之间的偏移。最好情况下(有序),需要比较(n-1)次,移动0次;最差情况下,需要比较1+2+…+(n-1)=n(n-1)/2次,移动n(n-1)/2次。所以答案都要小于50

2-2设有1000个元素的有序序列,如果用二分插入排序再插入一个元素,则最大比较次数是

log~2~N,不再重复了

2-3用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数最少的是()。

逆序对越少比较次数越少

2-4在快速排序的一趟划分过程中,当遇到与基准数相等的元素时,如果左右指针都会停止移动,那么当所有元素都相等时,算法的时间复杂度是多少2-5

在快速排序的一趟划分过程中,当遇到与基准数相等的元素时,如果左右指针都不停止移动,那么当所有元素都相等时,算法的时间复杂度是多少?

在快速排序的一趟划分过程中,当遇到与基准数相等的元素时,如果左指针停止移动,而右指针在同样情况下却不停止移动,那么当所有元素都相等时,算法的时间复杂度是多少?

推荐记住吧。。都停止是O(NlogN),不停止的话就是O(N^2^)

2-7对N个不同的数据采用冒泡算法进行从大到小的排序,下面哪种情况下肯定交换元素次数最多?

答案就是。。。完全反着的呗

2-8对于7个数进行冒泡排序,需要进行的比较次数为:

冒泡最差就是7+6+5+4+3+2+1,也就是21,其实就是等差数列的公式,n(n-1)/2

2-9有组记录的排序码为{ 46,79,56,38,40,84 },则利用堆排序的方法建立的初始堆为:

简单说一下怎么建立初始堆,首先将给的记录按照层序构建一个完全二叉树,接着进行调整(以大顶堆为例)

  • 自己最大,不用调整

  • 左孩子最大,交换该非叶结点与其左孩子的值,并考察以左孩子为根的子树是否满足大顶堆的要求,不满足递归向下处理

  • 右孩子最大,交换该非叶结点与其右孩子的值,并考察以右孩子为根的子树是否满足大顶堆的要求,不满足递归向下处理

2-10采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是:

递归次数与每次划分后得到的分区处理顺序无关

2-11对N个记录进行快速排序,在最坏的情况下,其时间复杂度是:

上面的表中给出了,不再多说

2-12有组记录的排序码为{46,79,56,38,40,84 },采用快速排序(以位于最左位置的对象为基准而)得到的第一次划分结果为:

base = 46

  1. i = 0; j = 5
    此时 46, 79, 56, 38, 40, 84
    从右往左找比base小的数,如果找到,则替换i处的值
  2. i = 0; j = 4
    此时 40, 79,56,38,40,84
    从左往右找比base大的数,如果找到,则替换j处的值
  3. i = 1;j = 4
    此时 40, 79,56,38,79,84
    从右往左找比base小的数,如果找到,则替换i处的值
  4. i = 1;j = 3
    此时 40, 38,56,38,79,84
    从左往右找比base大的数,如果找到,则替换j处的值
  5. i = 2;j = 3
    此时 40, 38,56,56,79,84
  6. i=2 处填上base值46
    此时 40, 38,46,56,79,84
    选C

2-13对于序列{ 49,38,65,97,76,13,27,50 },按由小到大进行排序,下面哪一个是初始步长为4的希尔排序法第一趟的结果?

希尔排序应该说是亲民的一种排序了。。。代码亲民,选择做起来也不难。下面来简单说一下希尔排序的过程。

首先选择len/2作为增了,然后前len/2个分别和后len/2个一一对应算是一组,然后这俩组成的一组进行比较交换。

第二步让增量/2得到新的增量,然后重复上面的操作,直至增量为1,进行最后一次排序

2-14给定初始待排序列{ 15,9,7,8,20,-1,4 }。如果希尔排序第一趟结束后得到序列为{ 15,-1,4,8,20,9,7 },则该趟增量为

会了希尔排序之后这个就很简单了

2-16对于10个数的简单选择排序,最坏情况下需要交换元素的次数为:

就是每两个都得交换,也就是9次