2021-10-09 数据结构二轮复习（带代码的整理）

1. 排序：就是重新排列表中的元素，是的表中的元素满足按照关键字有序的过程；
2. 算法的稳定性：关键字相同的两个元素，若排序前和排序后的顺序都一样/排序后相对位置不变，则算法稳定。⚠注意算法稳定不是衡量算法优劣的标准。
3. 内外部排序的区分：数据元素是否完全在内存内；内部排序算法的性能取决于算法的时间复杂度（由比较和移动次数决定）和空间复杂度。

基本思想：每次将一个待排序的记录按照关键字大小插入前面已经拍好的子序列中，直到全部记录插入完成

1. 直接插入排序

void InsertSort(ElemType A[],int n){
	int i,j;
	for(i=2;i<=n;i++){		//依次将2-n个数字插入到前面的排序数列中
		if(A[i] 
比较次数和移动次数取决于待排序表的初始状态！
 稳定的排序算法，且适用于顺序存储方式和链式存储的线性表；
 
空间效率：常数个辅助单元，空间复杂度为O（1）；
 时间复杂度：O（n^2）;
 
折半插入排序
 
void InsertSort(ElemType A[], int n) {
	int i,j, mid, low, high;
	for (i = 2;i <= n;i++) {
		A[0] = A[i];
		low = 1;
		high = i - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (A[0] > A[mid]) {
				low = mid + 1;
			}
			else
				high = mid - 1;
		}
		for (j = i - 1;j >= high + 1;j--) {	//统一后移，空出插入位置
			A[j + 1] = A[j];
		}
		A[high + 1] = A[0];
	}
}

 
比较次数（O（nlogn））与待排序的初始状态无关，仅取决于表中的元素个数n；
 移动次数未改变，依赖于表中的初始状态，因此时间复杂度为O（n^2）；
 算法稳定，仅适用于顺序存储的顺序表；
 对于数据量不大的排序表，折半插入有很好的性能
 
希尔排序
 
void SellInsort(int *a, int n) {
	int dk,i,j;			//定义增量;
	for (dk = n / 2;dk >= 1;dk = dk / 2) {
		for (i = dk + 1;i <= n;i++) {
			if (a[i] < a[i - dk]) {
				a[0] = a[i];
				❓for ( j = i - dk;j > 0 && a[0] < a[j];j -= dk) {
					a[j + dk] = a[j];
				}
				a[j + dk] = a[0];
			}
		}
	}
}

 
时间复杂度：依赖于增量序列的函数，约为O（n^1/3），最坏为O（n*n）;
 不稳定，且仅适用于顺序存储的线性表；
 
***注意点***
 简单选择排序、冒泡排序、堆排序、快速排序依次排序后，会使一个记录放在最终位置上。
 
有问题的题目
 //记住公式就行
 对任意7个关键字进行基于比较的排序，至少要进行（）次关键字之间的两两比较？
 对任意n个关键字排序的比较次数至少为log（n!）。（取上整）。