数据结构习题（填空、判断、选择）

(E)快速排序__________

(1)从待排序序列中依次取出元素与己排序序列中的元素作比较将其放入己排序序列中的正确的位置上。

(2)从待排序序列中挑选元素,并将其放入己排序序列的一端。 (3)依次将相邻的有序表合并成一个有序表。

(4)每次把待排序的区间划分为左、右两个子区间,其中左区间中元素的键值均小于等于基准元素的键值,右区间中元素的键值均大于等于基准元素的键值。 (5)当两个元素比较出现反序(即逆序)时就相互交换位置。 2.在对一组记录（4,38,96,23,15,72,60,45,83）进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较____3___次。

3.在利用快速排序方法对一组记录(54,38,96,23,15,72,60,45,83)进行快速排序时,递归调用而使用的栈的所能达到的最大深度为____2____,共需递归调用的次数为____4___,其中第二次递归调用是对____（23，38，15）_____一组记录进行快速排序。

4.在堆排序,快速排序和归并排序中,若只从存储空间考虑,则应首先选取___堆排序__方法,其次选取____快速排序____方法,最后选取____归并排序____方法:若只从排序结果的稳定性考虑,则应选取___归并排序_____方法:若只从平均情况下排序最快考虑,则应选取___快速排序_____方法:若只从最坏情况下排序最快并且要节省内存考虑,则应选取___堆排序___方法。 5.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,排序是不稳定的有____希尔排序；选择排序；快速和堆排序____。

6.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是____快速排序___需要内存容量最多的是____基数排序___。

7.在堆排序和快速排序中,若原始记录接近正序或反序,则选用_____堆排序______若原始记录无序则最好选用______快速排序_______。

8.在插入和选择排序中,若初始数据基本正序,则选用_____插入排序______若初始数据基本反序,则选用_____选择排序______。

9.对n个元素的序列进行起泡排序时,最少的比较次数是____ n-1_____ 10.两个序列如下： L1＝{25，57，48，37，92，86，12，33} L2＝{25，37，33，12，48，57，86，92}

用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列_____ L2_____。