【数据结构】排序习题
8.对n个元素执行快速排序，需要的额外空间的大小为（ ）
A.O(1)
B.O(n)
C.O(logn)
D.O(nlogn)
答案：C
解析:
如果是递归算法，由于递归调用需要额外的O(logN)栈空间，所递归的深度大概为二叉树的深度，即logN
如果是非递归算法，需要模拟递归的过程，即需要保存子区间的索引，每次都会成对的保存，最多保存的索引也和二叉树的高度有关：2 * logN
所以空间复杂度为logN
2.使用选择排序对长度为100的数组进行排序，则比较的次数为（ ）
A.5050
B.4950
C.4851
D.2475
答案：B
解析：
选择排序，每次都要在未排序的所有元素中找到最值，
如果有n个元素，则
第一次比较次数： n - 1
第二次比较次数： n - 2
…
第n - 1次比较次数： 1
所有如果n = 100
则比较次数的总和：99 + 98 + … + 1
共4950次。