1、问题
对n个不同的数构成的数组A[1…n]进行排序，其中n=2^k

思路：

归并排序是多次将相邻两个或两个以上的有序表合并成一个新的有序表。

最简单的归并是将两个有序的子表合并成一个有序的表，即二分归并排序。
2、解析
设待排序表有10个记录，其关键字分别为{18,2，20,34,12,32,6，16,1，5}。

采用二分归并排序方法排序过程：


3、设计
void MergeSort(RecType R[],int n) {
	int length;
	for(length=1;length<n;length=length*2){
		MergePass(R,length,n);
	}
}

void Merge(RecType R[],int low,int mid,int high){
	RecType *R1;
	int i=low,j=mid+1,k=0;
	R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
	while(i<=mid&&j<=high){
		if(R[i].key<=R[j].key){
			R1[k]=R[i];
			i++;
			k++;
		}
		else{
			R1[k]=R[j];
			j++;
			k++;
		}
	}
	while(i<=mid){
		R1[k]=R[i];
		i++;
		k++;
	}
	while(j<=high){
		R1[k]=R[j];
		j++;
		k++;
	}
	for(k=0,i=low;i<=high;i++,k++){
		R[i]=R1[k];
	}
} 
void MergePass(RecType R[],int length,int n){  //一趟二路归并 
	int i;
	for(i=0;i+2*length-1<n;i=i+2*length){   //归并length长的两相邻子表 
		Merge(R,i,i+length-1,i+2*length-1);
	}
	if(i+length-1<n){  //余下两个子表，后者长度小于length 
		Merge(R,i,i+length-1,n-1);//归并两个子表 
	}
}

4、分析
每一趟归并的时间复杂度为O(n)。

总共需进行[log2 n]趟。

二分归并排序的时间复杂度为O(nlog2 n)。

1-1

仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。

T

1-2

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

F

1-3

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

F

1-4

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

T

1-5

对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。

F

1-6

希尔排序是稳定的算法。

F

1-7

对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。

F

1-8

要从50个键值中找出最大的3个值，选择排序比堆排序快。

T

1-9

用3条磁带对55个有序段做2路归并，初始的段分配成（34，21）比分配成（30，25）要好。

T

1-10

采用递归方式对顺序表进行快速排序，每次划分后，先处理较短的分区可以减少递归次数。

T

2-1

在对N个元素进行排序时，基于比较的算法中，其“最坏时间复杂度”中最好的是：

A.O(logN)

B.O(N)

C.O(NlogN)

D.O(N​^2​​ )

C

2-2

下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数N>2）
A.冒泡排序

B.插入排序

C.堆排序

D.快速排序

B

2-3

对一组数据{ 2，12，16，88，5，10 }进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能是：
A.冒泡排序

B.希尔排序

C.归并排序

D.基数排序

A

2-4

下面四种排序算法中，稳定的算法是：
A.堆排序

B.希尔排序

C.归并排序

D.快速排序

C

2-5

对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？
A.从小到大排好的

B.从大到小排好的

C.元素无序

D.元素基本有序

A

2-6

有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为：
A.79，46，56，38，40，80

B.84，79，56，46，40，38

C.84，56，79，40，46，38

D.84，79，56，38，40，46

D

2-7

有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：
A.{38,46,79,56,40,84}

B.{38,79,56,46,40,84}

C.{38,46,56,79,40,84}

D.{40,38,46,56,79,84}

D

2-8

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

B.2

C.3

D.4

D

2-9

对N个元素采用简单选择排序，比较次数和移动次数分别为：
A.O(N^​2​​ ), O(N)

B.O(N), O(logN)

C.O(logN), O(N^​2​​ )

D.O(NlogN), O(NlogN)

A

2-10

对N个记录进行堆排序，最坏的情况下时间复杂度是：
A.O(logN)

B.O(N)

C.O(NlogN)

D.O(N^​2​​ )

C

2-11

在基于比较的排序算法中，哪种算法的最坏情况下的时间复杂度不高于O(NlogN)？
A.冒泡排序

B.归并排序

C.希尔排序

D.快速排序

B

2-12

对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：
(I). 直接插入排序过程中元素之间的比较次数更少

(II). 直接插入排序过程中所需要的辅助空间更少

(III). 直接插入排序过程中元素的移动次数更少
A.仅 I

B.仅 III

C.仅 I、II

D.I、II 和 III

A

2-13

若数据元素序列{ 11，12，13，7，8，9，23，4，5 }是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是：
A.冒泡排序

B.选择排序

C.插入排序

D.归并排序

C

2-14

就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是：
A.堆排序 < 归并排序 < 快速排序

B.堆排序 > 归并排序 > 快速排序

C.堆排序 < 快速排序 < 归并排序

D.堆排序 > 快速排序 > 归并排序
作者

C

2-15

对于7个数进行冒泡排序，需要进行的比较次数为：
A.7

B.14

C.21

D.49

C

2-16

对N个记录进行归并排序，空间复杂度为：
A.O(logN)

B.O(N)

C.O(NlogN)

D.O(N^2)

B

2-17

下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(NlogN)的是：
A.冒泡排序

B.直接选择排序

C.堆排序

D.快速排序

C

2-18

排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法称为：
A.插入排序

B.选择排序

C.快速排序

D.归并排序

A

2-19

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

B.100, 54

C.54, 63

D.45, 44

D

2-20

对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：
A.O(N)

B.O(NlogN)

C.O(N​^2​​ )

D.O(N^2​​ logN)

C

2-21

对N个记录进行堆排序，需要的额外空间为：
A.O(1)

B.O(logN)

C.O(N)

D.O(NlogN)

A

2-22

给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？
A.→331→431→33→63→24→56→46→57→7→28

B.→56→28→431→331→33→24→46→57→63→7

C.→431→331→33→63→24→56→46→57→7→28

D.→57→46→28→7→33→24→63→56→431→331

C

2-23

将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：
第1趟排序后：2, 12, 16, 10, 5, 34, 88

第2趟排序后：2, 5, 10, 12, 16, 34, 88

则可能的排序算法是：
A.冒泡排序

B.归并排序

C.快速排序

D.插入排序

C

2-24

数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果？
A.冒泡排序

B.快速排序

C.插入排序

D.堆排序

B

2-25

设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：
A.1000

B.999

C.500

D.10

D

  设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（
    ）。 


15，25，35，50，20，40，80，85，36，70
15，25，35，50，80，20，85，40，70，36
15，25，35，50，80，85，20，36，40，70
15，25，35，50，80，20，36，40，70，85


解析过程！

 
堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前，先讲解下什么是数据结构中的二叉堆。
堆排序是利用堆的特性对记录序列进行排序的一种排序方法。

即小顶堆：父结点的值小于左右孩子结点的值，大顶堆的相反




假设我们要排序的序列是{50,10,90,30,70,40,80,60,20}
堆排序分为两个步骤：
1.构造大顶堆(或者小顶堆)
如图所示：将输入的数组不断调整，使得其构成大顶堆



void HeapAjust(int* arr,int start,int end)
{
	int temp,j;
	temp = arr[start];
	for (j = 2*s;j <= end;j*=2)
	{
		if(j < m && arr[j] < arr[j+1])//左孩子小于右孩子
			j++;
		if(temp >= arr[j])
			break;
		arr[start] = arr[j];
	    start = j;
	}
	arr[start] = temp;
}



在这里我们使用大顶堆，依次输出元素如下图：
依次类推输出所有元素


程序如下：

void HeapSort(int* arr,int len)
{
	int i;
	for(i = len/2;i>= 0;i--)//构造大顶堆
		HeapAjust(arr,i,len-1);

	for (i = len-1;i > 0;i--)
	{
		swap(arr[0],arr[i]);//取堆顶的记录和当前未经排序子序列的最后一个记录交换
		HeapAjust(arr,1,i-1);
	}
}

这里给出完整代码(仅供参考)：

#include <stdio.h>
#include <stdlib.h>

void swap(int& data1,int &data2)
{
	int temp = data1;
	data1 = data2;
	data2 = temp;
}

//返回i的父结点
int parent(int i)
{
	return (i-1)/2;
}

//返回i的左孩子结点
int leftchild(int i)
{
	return 2*i+1;
}

//返回i的右孩子结点
int rightchild(int i)
{
	return 2*i+2;
}

void MaxHeapify(int *arr,int len,int i)
{
	int lchild = leftchild(i);
	int rchild = rightchild(i);
	int nmax;

	if(lchild < len && arr[lchild] > arr[i])
		nmax = lchild;
	else
		nmax = i;

	if(rchild < len && arr[rchild] > arr[nmax])
		nmax = rchild;

	if (nmax != i)
	{
		swap(arr[nmax],arr[i]);
		MaxHeapify(arr,len,nmax);
	}
}

//堆排序
void HeapSort(int* arr,int len)
{
   for (int i = parent(len - 1);i >= 0;i--)
       MaxHeapify(arr,len,i);
   
   for (int j = len -1;j > 0;j--)
   {
	   swap(arr[j],arr[0]);
	   len--;
	   MaxHeapify(arr,len,0);
   }
}

void print(int* arr,int len)
{
	int i =0;
	while (i < len)
		printf("%d ",arr[i++]);
// 	for (int i = 0;i < len;i++)
// 	{
// 		printf("%d ",arr[i]);
// 	}

}
int main()
{
    int nArr[10] = {4,1,3,2,16,9,10,14,8,7};
    
	printf("排序前：");
    print(nArr, 10);
    HeapSort(nArr, 10);
	printf("\n排序后：");
    print(nArr, 10);
	
	system("pause");
    return 0;
}






复杂度分析：
运行时间主要是消耗在初始建堆和重建堆时的反复筛选上，在构建堆的过程中，因为是完全二叉树最下层最右边的非终端结点开始构建，将它与其孩子比较若有必要进行交换，对于每个非终端结点来说，其实最多进行两次比较和呼唤操作，因此整个构建过程的时间复杂度为O(n)，在排序时，第i次取堆顶记录重建时需要使用O(logi)的时间，并需要取
 n-1 次堆顶记录，因此重建堆时的时间复杂度为 O(nlogn).因此总体来说堆排序的时间复杂度为  O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此他无论是最好、最坏和平均时间复杂度均为  O(nlogn)。这在性能是要超过
 冒泡排序、简单选择排序、直接插入排序的 O(n^2) 的时间复杂度。空间复杂度上，他只有一个用来交换的暂存单元，也非常不错。但是由于记录的比较与交换是跳跃式进行，因此堆排序是一种不稳定的排序方法。