1、下列排序算法中，▁▁B▁▁ 是稳定的。

A.简单选择排序

B.冒泡排序

C.希尔排序

D.快速排序

解析：稳定排序是每次排序得到的结果是唯一的，不稳定排序得到的结果不唯一。

稳定：冒泡排序、归并排序、基数排序

不稳定：选择排序、希尔排序、快速排序、堆排序

2、有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为

（ C ）

A.-1，4，8，9，20，7，15，7

B.-1，7，15，7，4，8，20，9

C.-1，4，7，8，20，15，7，9

D.A，B，C均不对
解析：建立小顶堆

堆排序，建初始堆以及优先队列(priority_queue)

 3、对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数最多为( D )。

A.n+1

B.n

C.n-1

D.n(n-1)/2

解析：冒泡排序  (时间复杂度O（n^2） 稳定)

void Bubble_sort(int array[], int n) {int swap;for (int i = 1; i <= n - 1; i++) {swap = 0;for (int j = 1; j <= n - i; j++) {if (array[j] > array[j + 1]) {array[0] = array[j];array[j] = array[j + 1];array[j + 1] = array[0];swap = 1;}}if (swap == 0) {break;}}
}

比较次数最少的情况：当本来就有序的时候，一次交换也没发生，只进行了n-1次比较。（因为swap==0，从循环跳出了）

比较次数最多的情况：逆序的情况，第一次循环，比较n-1次，第二次比较n-2次……第n-1次比较1次。总的比较次数为n(n-1)/2

#include
#define MAX 1000
using namespace std;void Bubble_sort(int array[], int n) {printf("初始：         ");for (int j = 1; j <= n; j++) {cout << " " << array[j];}cout << endl;for (int i = 1; i <= n - 1; i++) {printf("第%d次比较结果：",i);for (int j = 1; j <= n - i; j++) {if (array[j] > array[j + 1]) {array[0] = array[j];array[j] = array[j + 1];array[j + 1] = array[0];}}for (int j = 1; j <= n; j++) {cout << " " << array[j];}cout << endl;}
}int main()
{int array[MAX] = { 0,49,14,38,74,96,8 };int n = 6;Bubble_sort(array, n);return 0;
}

4、对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是( B ) 

A.O(n)

B.O(n^2)

C.O(nlog2(n))

D.O(n^3)

解析：快速排序 

最好情况下，时间复杂度为O（nlog2（n））

最坏情况下，时间复杂度为O（n^2）

最好情况下，空间复杂度为O（log2（n））

最坏情况下，空间复杂度为O（n）

#include
#define MAX 1000
using namespace std;int Partition(int array[], int low, int high) {array[0] = array[low];while (low < high) {while (low < high && array[high] >= array[0]) {high--;}if (low < high) {array[low] = array[high];low++; }while (low < high && array[low] < array[0]) {low++;}if (low < high) {array[high] = array[low];high--;}}array[low] = array[0];return low;
}void Quick_Sort(int array[], int s, int t) {int i;if (s < t) {i = Partition(array, s, t);Quick_Sort(array, s, i - 1);Quick_Sort(array, i + 1, t);}
}int main()
{int array[MAX] = { 0,49,14,38,74,96,8 };int n = 6;Quick_Sort(array, 1, 6);for (int i = 1; i <= n; i++) {cout << array[i] << " ";}return 0;
}

5、

解析：堆排序时间复杂度O（nlog2（n）） 

6、对同一待排序序列分别进行折半插入排序和直接插入排序, 两者之间可能的不同之处是_D__。

A.排序的总趟数

B.元素的移动次数

C.使用辅助空间的数量

D.元素之间的比较次数

1.有向无环图才能进行拓扑排序。
2.在待排序的元素序列基本有序的前提下，效率最高的排序方法是？（比较最坏情况下的时间复杂度）
3."list采用链式结构存储，在C++ STL中的list采用双向链表存储，比较适合用快速排序进行排序，这是由快速排序不需要随机访问元素的特点决定的。冒泡排序适合list，但是算法复杂度为O(n^2)，没有快速排序快。
4.二分插入排序算法适合顺序存储情况，不适合链式存储。
5.假设你只有100Mb的内存，需要对1Gb的数据进行排序，最合适的算法是？本题考查的是对外排序的理解。外排序一般用外存存放数据，采用多路归并的方法进行排序。
6.初始数据有序时，花费的时间反而最多的排序算法通常是快排。
7.适合并行处理的排序算法是(基数排序) ；基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。可以同时操作多个元素，从而实现了并行处理。
8.算法复杂度与初始状态无关的有：选择排序、堆排序、归并排序、基数排序。（选基归堆/旋即归队）
9.元素总比较次数与初始状态无关的有：选择排序、基数排序。（选基）
10.元素总移动次数与初始状态无关的有：归并排序、基数排序。（归基）
11.不稳定的算法：堆排、选择排序、快排、希尔排序（快希选堆不稳定（记忆：快些选一堆朋友来玩耍吧!））
12.若记录的初始状态已经按关键码基本有序，则选用直接插入排序或冒泡排序发为宜。