1. 插入排序，折半插入排序，希尔排序
2. 冒泡排序
3. 快速排序
4. 选择排序
5. 堆排序
6. 归并排序
7. 基数排序

常考

稳定：插入排序，折半插入排序，冒泡排序，归并排序，基数排序

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

比较次数与初始状态有关：插入排序，希尔排序，冒泡，快排，堆排序，归并

比较次数与初始状态无关：选择排序，折半插入排序

注：这里的比较次数不是比较次数的数量级，更不是时间复杂度

趟数与初始状态有关：冒泡，快排

趟数与初始状态无关：插入排序，折半插入排序，希尔排序，选择排序，归并，堆排序，基数排序

元素的移动次数与关键字的初始排列次序无关的是：基数排序

时间复杂度和初始状态有关：插入排序，快排，冒泡

时间复杂度和初始状态无关：选择排序，堆排序，归并，基数排序

插入排序

代码:

void InsertSort(int a[], int n){
	int i,j;
	for(i=2;i<=n;++i)
		 if(a[i]<a[i-1]){
			a[0]=a[i];
			for(j=i-1;a[j]>a[0];--j)
				a[j+1]=a[j];
			a[j+1]=a[0];
		 }
}

算法分析:

空间复杂度 ：\(O(1)\)

时间复杂度 ： \(O(n^2)\)，在最好情况下（完全顺序）可以达到\(O(n)\)

趟数 ：固定\(n-1\)趟

比较次数 :

最坏情况下（完全逆序）为\(\sum_{i=2}^{n}i\)

最好情况下（完全顺序）为\(n-1\)

移动次数：

最坏情况下（完全逆序）为\(\sum_{i=2}^{n}(i+1)\)

最好情况下（完全顺序）为\(0\)

稳定性：稳定

全局有序性：否

适用情形：顺序存储和链表存储的线性表

折半插入排序

代码:

void InsertSort(int a[], int n){
	int i,j,l,r,mid;
	for(i=2;i<=n;++i){
		a[0]=a[i];
		l=1,r=i-1;
		while(l<=r){
			mid=(l+r)/2;
			if(a[mid]>a[0])r=mid-1;
			else l=mid+1;
		}  //找到不大于a[0]的最后一个位置
		//l=0,r=i-1;
		//while(l<r){
			//mid=l+r+1>>1;
			//if(a[mid]<=a[0]) l=mid;
			//else r=mid-1;
		//}
		for(j=i-1;j>=r+1;--j)
			a[j+1]=a[j];
		a[r+1]=a[0];
	}
}

算法分析:

空间复杂度 ：\(O(1)\)

时间复杂度 ： \(O(n^2)\)，在最好情况下（完全顺序）可以达到\(O(n)\)

趟数 ：固定\(n-1\)趟

比较次数 : 与初始状态无关，为\(O(nlog_2n)\)

移动次数：

与朴素插入算法相同

最坏情况下（完全逆序）为\(\sum_{i=2}^{n}(i+1)\)

最好情况下（完全顺序）为\(0\)

稳定性：稳定

全局有序性：否

适用情形：顺序存储的线性表，二分必须支持随机访问

希尔排序

代码:

void ShellSort(int a[],int n){
	int d,i,j;
	for(d=n/2;d>=1;d/=2)
		for(i=d+1;i<=n;++i)
			if(a[i]<a[i-d]){
				a[0]=a[i];
				for(j=i-d;j>0&&a[j]>a[0];j-=d)
					a[j+d]=a[j];
				a[j+d]=a[0];
			}
}

算法分析:

空间复杂度 ：\(O(1)\)

时间复杂度 ： \(O(n^{1.3})\)，最坏\(O(n^2)\). 涉及到数学领域未解决的难题

稳定性：不稳定

全局有序性：否

适用情形：顺序存储的线性表

主要是选择题判断增量d.

冒泡排序

代码:

void BubbleSort(int a[],int n){
	int i,j;
	bool flag;
	//数组下标从1开始
	for(i=1;i<=n-1;++i){
		flag=false;
		for(j=n;j>i;--j)
			if(a[j-1]>a[j]){
				swap(a[j-1],a[j]);
				flag=true;
			}
		if(flag==false)
			return;
	}
}

算法分析:

空间复杂度 ：\(O(1)\)

时间复杂度 ： \(O(n^2)\),在最好情况下（完全顺序）可以达到\(O(n)\)

趟数 ：最坏\(n-1\),最好\(1\)

比较次数 :

最坏情况下（完全逆序）为\(\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}\)

最好情况下（完全顺序）为\(n-1\)

移动次数：

最坏情况下（完全逆序）为\(\sum_{i=1}^{n-1}(n-i)=\frac{3n(n-1)}{2}\), (一次swap移动3次）

最好情况下（完全顺序）为\(0\)

稳定性：稳定

全局有序性：是（每一趟都将某个元素放在了其最终的位置上）

适用情形：顺序存储线性表, 双链表

快速排序

代码:

int Pratition(int a[],int l,int r){
	int x=a[l]; //选第一个为枢纽
	while(l<r){
		while(l<r&&a[r]>=x) --r;
		a[l]=a[r];
		while(l<r&&a[l]<=x) ++l;
		a[r]=a[l];
	}
	a[l]=x;
	return l;
}

void QuickSort(int a[],int l,int r){
	if(l<r){
		int p=Pratition(a,l,r);
		QuickSort(a,l,p-1);
		QuickSort(a,p+1,r);
	}
}

算法分析:

空间复杂度 ：为递归栈的深度,最好\(O(log_2n)\),最坏\(O(n)\),平均\(O(log_2n)\)

时间复杂度 ：\(O(nlog_2n)\), 在序列基本有序或逆序会影响速度(导致划分不对称)，最坏\(O(n^2)\)，内部排序中平均性能最优

稳定性：不稳定

全局有序性：不产生有序子序列，但每次将枢纽元素放在其最终的位置上

适用情形：顺序存储线性表

选择排序

代码:

void SelectSort(int a[],int n){
	int i,j,mn;
	for(i=1;i<=n-1;++i){
		mn=i;
		for(j=i+1;j<=n;++j)
			if(a[j]<a[mn]) mn=j;
		if(mn!=i) swap(a[mn],a[i]);
	}
}

算法分析:

空间复杂度 ：\(O(1)\)

时间复杂度 ：严格\(O(n^2)\)

比较次数 : 严格\(\frac{n(n-1)}{2}\)

稳定性：不稳定

全局有序性：是

适用情形：顺序存储线性表

堆排序

代码:

void HeadAdjust(int a[],int k,int len){
	//调整以k为根的子树
	a[0]=a[k];
	for(int i=2*k;i<=len;i*=2){
		if(i<len&&a[i]<a[i+1])
			i++;
		if(a[0]>=a[i]) break;
		else{
			a[k]=a[i];
			k=i;
		}
	}
	a[k]=a[0];
}

void BuildMaxHeap(int a[],int len){
	for(int i=len/2;i>0;i--)
		HeadAdjust(a,i,len);
}

void HeapSort(int a[],int len){
	BuildMaxHeap(a,len);
	for(int i=len;i>1;i--){
		swap(a[i],a[1]);
		HeadAdjust(a,1,i-1);
	}	
}

算法分析:

空间复杂度 ：\(O(1)\)

时间复杂度 ：建堆\(O(n)\)，之后\(n-1\)次向下调整，每次\(O(log_2n)\),因此最终平均复杂度\(O (nlog_2n)\)

添加元素比较次数：新元素从堆底不断向上调整的次数

删除堆顶比较次数：

swap(a[i],a[1]);
HeadAdjust(a,1,i-1);

即将堆底换上来后向下调整的次数.

稳定性：不稳定

适用情形：顺序存储线性表

归并排序

代码:

int b[N];
void Merge(int a[],int l,int mid,int r){
	int i,j,k;
	for(i=l;i<=r;++i)	
		b[i]=a[i];
	for(i=l,j=mid+1,k=i;i<=mid&&j<=r;++k)
		if(b[i]<=b[j]) 
			a[k]=b[i++];
		else
			a[k]=b[j++];

	while(i<=mid) 
		a[k++]=b[i++];
	while(j<=r) 
		a[k++]=b[j++];
}

void MergeSort(int a[],int l,int r){
	if(l<r){
		int mid=(l+r)/2;
		MergeSort(a,l,mid);
		MergeSort(a,mid+1,r);
		Merge(a,l,mid,r);
	}	
}

算法分析:

空间复杂度 ：\(O(n)\)

时间复杂度 ： 每趟归并复杂度\(O(n)\), 一共\(\lceil log_2n \rceil\)趟，总复杂度\(O(nlog_2 n)\)

趟数 ：\(\lceil log_2n \rceil\)，对于\(k\)路归并趟数\(m\)满足\(k^m=N\)，\(m=\lceil log_kN\rceil\)

稳定性：稳定

基数排序

算法分析:

空间复杂度 ：需要\(r\)个队列，\(O(r)\)

时间复杂度 ：\(d\)趟分配和收集，一趟分配\(O(n)\)，一趟收集\(O(r)\)，总共\(O(d(n+r))\)

稳定性：稳定