[数据结构与算法]数据结构与算法分析（C++语言版）_张琨版 第九章排序课后习题答案

一、选择题

1.B 2.B 3.A 4.B C 5. A 6.A 7.D 8.A 9.C 10.C

二、填空题

1. 170,275,154,503,512,765,612,897,512,677,908
2. 堆排序 快速排序
3. n-1
4. O(nlogn)
5. 希尔排序 快速排序 堆排序
6. 60,51,121,142,15,575,185,46,57,68,89
7. n+2）(n-1)/2
8. 9,15,7,8,20,-1,4
9. 简单选择排序
10. 13

三、判断题

1. × 2. √ 3. × 4. × 5. × 6. × 7. × 8. × 9. ×10. √

四、简答题

4. （1）直接插入排序 简单选择排序 冒泡排序 希尔排序 折半插入排序 快速排序
   （2）堆排序 希尔排序 快速排序 两路归并排序
   （3）直接插入排序 简单选择排序 冒泡排序 堆排序 希尔排序 折半插入排序
   （4）堆排序 希尔排序 快速排序

平均时间复杂度O(d(n+r)) 空间复杂度O(n+r)
其中d为关键字位数 r为基数 n为关键字个数

五、计算题

1. 思路】先从底向上从无序区冒一个最小的元素，在从上向底从无序区冒一个最大的元素。算法如下:

void DBubble(SqList R[],int n)
{
	int i,j;
	SqList temp;
	int exchange=1;
	i=0;
	while(exchange==1)
	{
		exchange=0;
		for(j=n-i-1;j>1;j--)
		{
			if(R[j].key<R[j-1].key)
			{
				exchange=1;
				temp=R[j];
				R[j]=R[j-1];
				R[j-1]=temp;
			}

		}
		for(j=i;j<n-1;j++)
		{
			if(R[j].key>R[j+1].key)
			{
				exchange=1;
				temp=R[j];
				R[j]=R[j+1];
				R[j+1]=temp;
			}

		}
		i++;
	}
}

2. //折半插入排序

void Binsert_sort(ElemType array[],int length){
	int inner,outer,i;
	int temp,position;
	int low,high,median;
	if(array == NULL || length == 0)
		exit(-1);
	for(outer = 1; outer < length ;outer++){
		//取出待插入元素
		temp = array[outer];
		low = 0;
		high = outer - 1;
		//查找插入位置
		while(low <= high){
			median = (low + high) >> 1;
			if(array[median] < temp)
				low = median + 1;
			else
				high = median - 1;
		}
		position = low;
		//相应元素后移
		i = outer;
		while(i > position){
			array[i] = array[i-1];
			i--;
		}
		//将待插入元素插入到position
		array[position] = temp;
	
	}
}

3. 解析：
   
   代码：

void counting_sort(int *ini_arr, int *sorted_arr, int n)
{
       int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE);
       int i, j, k;

	   //统计数组中，每个元素出现的次数
       for(k=0; k<NUM_RANGE; k++){
               count_arr[k] = 0;
       }
       
	   for(i=0; i<n; i++){
               count_arr[ini_arr[i]]++;
       }


       for(k=1; k<NUM_RANGE; k++){
               count_arr[k] += count_arr[k-1];
       }

       for(j=n-1 ; j>=0; j--){
		   int elem = ini_arr[j];
		   int index = count_arr[elem]-1;
           sorted_arr[index] = elem;
           count_arr[elem]--;
       }
       free(count_arr);
}

4. (1)代码如下：

#include<iostream>
using namespace std;
typedef int KeyType;
typedef struct node
{
	KeyType key;
	struct node * next;
}SNode;

void createLink(SNode *&h, KeyType R[], int n)
{
	int i;
	SNode *s, *r;
	h = (SNode *)malloc(sizeof(SNode));
	r = h;
	for (i = 0; i < n;i++)
	{
		s = (SNode *)malloc(sizeof(SNode));
		s->key = R[i];
		r->next = s;
		r = s;
	}
	r->next=NULL;
}
void InsertSort(SNode *&h)
{
	SNode *p, *p1, *q, *pre;
	if (h->next)
	{
		p = h->next->next;
		h->next->next = NULL;
		while (p)
		{
			pre = h;
			q = pre->next;
			while (q && q->key<p->key)
			{
				pre = q;
				q = q->next;
			}
			p1 = p->next;
			p->next = pre->next;
			pre->next = p;
			p = p1;
		}
	}
}
void Display(SNode *h)
{
	SNode *p = h->next;
	while (p!=NULL)
	{
		cout << p->key << " ";
		p = p->next;
	}
	cout << endl;
}
int main()
{
	int a[] = { 30, 10, 70, 50, 70, 60 };
	int n = sizeof(a) / sizeof(a[0]);
	SNode *h;
	createLink(h, a, n);
	cout << "排序前：" << endl;
	Display(h);
	InsertSort(h);
	cout << "排序后：" << endl;
	Display(h);
	return 0;
}

（2）
10,30
10,30,70
10,30,50,70
10,30,50,70,70
10,30,50,60,70,70

(3) 最好情况下为O(n)

六、说明

本人已毕业多年，读研时撰写了一份 《数据结构与算法分析（C++语言版）_张琨版 课后习题答案》，每年依旧有大量考研的学弟学妹们来找这份答案，现将其公布在blog上，仅供学术交流，上述解答如有问题，可私信沟通。