排序算法一览（c语言实现）

本文主要介绍四大排序思想，详情看旁栏目录。
先附上用于检验的主函数以及相关准备工作。

#include 
#include 
#define LeftChild(i) (2*(i)+1)
#define cutoff (3)

void print(int arr[],int N) {
	for(int i=0; i 
截止我发文章前，在调用最后一个排序的算法，有想法的小伙伴可以挨个把注释去掉，试试前面几个的正确性。
 
正文 
- 插入排序 
时间复杂度：O（N^2）
 平均时间复杂度：O（N^2）
 最好情况：O（N） （内层for循环无需执行）
 
-直接插入 
//direct_insert sort
void directinsertsort(int arr[],int N) {
	int tmp,i,j;
	for(i=1; i0&&arr[j-1]>tmp; j--) {
			arr[j]=arr[j-1];
		}
		arr[j]=tmp;
		print(arr,N);
	}
}
 
- 二分插入 
//binary insert sort
void binaryinsertsort(int arr[],int N) {
	int tmp,i,j,left,right,mid;
	for(i=1; itmp) right=mid-1;
			else left=mid+1;
		}
		for(j=i; j>0&&arr[j-1]>tmp; j--) {
			arr[j]=arr[j-1];
		}
		arr[j]=tmp;
		print(arr,N);
	}
}
 
- shell排序 
//shellsort
void shellsort(int arr[],int N) {
	int i,j,increase,tmp;
	for(increase=N/2; increase>0; increase/=2) {
		//确定每次的增量值
		for(i=increase; i=increase&&arr[j-increase]>tmp; j-=increase) {
				//最内层的循环就是插入排序
				arr[j]=arr[j-increase];

			}
			arr[j]=tmp;

		}
		print(arr,N);
	}
}
 
- 选择排序 
- 直接选择排序 
void Directselect(int arr[],int N) {
	int i,j,k,tmp;//tmp标记待交换的值，k标记下标
	for(i=0; i 
- 堆排序 
基于优先队列实现，
 时间复杂度：O（NlogN）
 （其中，建立二叉堆所需时间为N，logN为执行N次删除最小元素再放入第二个数组的操作。）
 特点：不稳定
 （注意：《数据结构与算法分析——c语言描述》翻译版提到该算法“稳定”，但要结合语境，作者说的稳定指的是 平均情况与最坏情况相差不大，即比较次数与序列初始状态无关，与中文书概念中的适应性（不强）概念相对应，而中文一般提到的的 稳定 指的是对于相同的数据，排序过程中其先后顺序不变）
 
void PercDown(int arr[],int i,int N) {
	int child;//下标
	int tmp;
	for(tmp=arr[i]; LeftChild(i)arr[child]) {
			child++;
		}//这一层的关系满足了就往下一层次去找

		if(tmp=0; i--) {
		PercDown(arr,i,N);
	}
	//deletemax
	for(i=N-1; i>0; i--) {
		Swap(&arr[0],&arr[i]);
		PercDown(arr,0,i);
		print(arr,N);
	}
}
 
- 归并排序 
分治思想的递归算法
 最坏情形：O（NlogN）
 比较次数几乎是最优
 
//归并排序
//shell排序类似，都是一种思维方式，归并排序是一种分治递归思想
//归并排序的关键在于合并两个 已排序 的表，不关心这个表中的元素排序的细节 ，可与简单排序法组合使用
//下面给出实现方案之一
void Merge(int arr[],int tmparr[],int Lpos,int Rpos,int Rightend) {
	int i,Leftend,Numele,tmppos;
	Leftend=Rpos-1;//这里一开始错写成了=Rightend-1,导致的结果是运行时长长达25s，且排序的最后两个元素95 96的值变成了最小的11 12
	//上述提到的错误 容易从语法上发现问题，逻辑上则比较难发现
	tmppos=Lpos;
	Numele=Rightend-Lpos+1;
	while(Lpos<=Leftend&&Rpos<=Rightend) {
		if(arr[Lpos]<=arr[Rpos]) {
			tmparr[tmppos]=arr[Lpos];
			tmppos++;
			Lpos++;
		} else {
			tmparr[tmppos]=arr[Rpos];
			tmppos++;
			Rpos++;
		}
	}

	//其中一个表已经全部排完，将另一表的元素直接整合（本身已排序）
	while(Lpos<=Leftend) {
		tmparr[tmppos]=arr[Lpos];
		tmppos++;
		Lpos++;
	}
	while(Rpos<=Rightend) {
		tmparr[tmppos]=arr[Rpos];
		tmppos++;
		Rpos++;
	}

//将排好序的tmparr对arr进行覆盖，个人认为一般情况下返回tmparr也是可以的，但是这个归并实现方式嵌套了几次函数，又用到了递归，还是尽力避免歧义比较好
	for(i=0; i 
- 交换排序 
- 快速排序 
分治思想的递归算法
 
//quicksort
//分治的递归思想
int Median3(int arr[],int left,int right) {
	int center=(left+right)/2;
	if(arr[left]>arr[center]) {
		Swap(&arr[left],&arr[center]);
	}
	if(arr[left]>arr[right]) {
		Swap(&arr[left],&arr[right]);
	}
	if(arr[right]>arr[center]) {
		Swap(&arr[right],&arr[center]);
	}
	
	Swap(&arr[center],&arr[right-1]);//将枢纽元从待排序的数据段中分离
	return arr[right-1];//实际返回的是枢纽元 

}

void Qsort(int arr[],int left,int right) {
	int i,j;
	int pivot;
	if(left+cutoff<=right) {
		pivot=Median3(arr,left,right);
		i=left;
		j=right-1;
		while(1) {
			while(arr[i]pivot) --j; //最终使j指向小于枢纽元的元素
			if(i 
- 冒泡排序 
//升序 
void Bubblesort(int arr[],int N){
 int i,j,tmp;
 
 for(i=0;iarr[j+1]){
 			tmp=arr[j];
 			arr[j]=arr[j+1];
 			arr[j+1]=tmp;
 			Isswap=1;
		 }
	 }
	 if(Isswap==0) break;
	 else print(arr,N);
 }
}
 
总结 
直接插入
二分插入
shell
直接选择
堆排序
冒泡
快速
归并
稳定性
好
好
好
好
适应性
好
好
好
（不清楚）
最好
O(N)
O(N-1)
O(N)
O(NlogN)
最坏
O(N^2)
O(N^2/2)
O(N^2)
O(N^2)
平均
O(N^2)
O(N^2)
O(N^1.3)
O(N^2)
O(NlogN)
O(N^2)
O(NlogN)
O(NlogN)
稳定性与适应性一栏没注明的默认为不好
 
结语 
本文的参考书籍：
 《数据结构与算法分析——c语言描述（原书第二版) Mark Allen Weiss》
 《算法与数据结构——c语言描述 （第三版） 张乃孝等编著》
 
趁着期末复习之际，希望自己好好巩固一下算法基础，相信这对未来的深入学习也会很有帮助。
 感谢你能看到这里！
 时间仓促，如有错漏之处恳请指正，非常感谢！