常用排序算法总结（C语言描述）

最近又把排序给复(yu)习(xi)了一遍，在此总结一下~具体理论思想持续补充完善中。。。

1.交换排序

（1）普通冒泡

时间复杂度：最差、平均都是O(n^2)，最好是O(n)

空间复杂度：O(1)

  # include<stdio.h>

  void bubble(int *list,int len)

  {

  	int i,j,t,flag=0;

  	for(i=0;i<len-1;i++)

  	{

  		flag=0;//设置标记，当某一轮交换没有交换任何数，那下一轮交换也不必进行了

  		for(j=0;j<len-1-i;j++)

  		{

  			if(list[j]>list[j+1])

  			{

  				t=list[j];

  				list[j]=list[j+1];

  				list[j+1]=t;

  				flag=1;

  			}

  		}

  		if(flag==0)

  		{

  			break;

  		}

  	}

  }

  void main()

  {

  	int n,list[10];

  	printf("请输入10个整数：");

  	for(n=0;n<10;n++)

  	{

  		scanf("%d",&list[n]);

  	}

  	printf("\n");

  	bubble(list,10);

  	for(n=0;n<10;n++)

  	{

  		printf("%d\t",list[n]);

  	}

  	printf("\n");

  }

（2）鸡尾酒排序：双向冒泡

时间复杂度：最差、平均都是O(n^2)，最好是O(n)

空间复杂度：O(1)

  #include<stdio.h>

  void CocktailBubble(int *list,int n)

  {

  	int low=0,high=n-1,j,t,flag;

  	while(low<high)

  	{

  		flag=0;//一次进行两趟for循环，第一个for循环排最大值（次大值），第二个for循环排最小值（次小值），只要其中一趟没有交换任何数字就可以结束排序

  		for(j=low;j<high;j++)

  		{

  			if(list[j]>list[j+1])

  			{

  				t=list[j];

  				list[j]=list[j+1];

  				list[j+1]=t;

  				flag=1;

  			}

  		}

  		if(flag==0)

  		{

  			break;

  		}

  		high--;//上述for循环第一次结束，排完最大值；第二次，排完次大值

  		for(j=high;j>low;j--)

  		{

  			if(list[j]<list[j-1])

  			{

  				t=list[j];

  				list[j]=list[j-1];

  				list[j-1]=t;

  			}

  		}

  		if(flag==0)

  		{

  			break;

  		}

  		low++;//上述for循环第一次结束，排完最小值；第二次，排完次小值

  	}

  }

  void main(){

  	int i,list[10];

  	printf("请输入10个整数:");

  	for(i=0;i<10;i++){

  		scanf("%d",&list[i]);

  	}

  	for(i=0;i<10;i++){

  		printf("%d ",list[i]);

  	}

  	printf("\n");

  	CocktailBubble(list,10);

  	for(i=0;i<10;i++){

  		printf("%d ",list[i]);

  	}

  	printf("\n");

  	while(1){

  		;

  	}

  }

（3）快速排序法

时间复杂度：平均O(nlogn),最坏O(n^2)

空间复杂度:O(logn)

  #include<stdio.h>

  #include<stdlib.h>

  int Partition(int *list,int low,int high)//该划分算法的工作为：排好list[low]，然后返回list[low]排好后的位置

  {

  	int i=low,j=high;

  	int t=list[low];

  	while(i<j)

  	{

  		while(list[j]>=t&&i<j)

  		{

  			j--;

  		}

  		if(i<j)

  		{

  			list[i]=list[j];

  			i++;

  		}

  		while(list[i]<=t&&i<j)

  		{

  			i++;

  		}

  		if(i<j)

  		{

  			list[j]=list[i];

  			j--;

  		}

  	}

  	list[i]=t;

  	return i;

  }

  void QuickSort(int *list,int low,int high)

  {

  	int p;

  	if(low<high)

  	{

  		p=Partition(list,low,high);//每运行一次，排好list[low]，然后返回list[low]值排好后的位置，然后对其左右区间进行递归

  		QuickSort(list,low,p-1);

  		QuickSort(list,p+1,high);

  	}

  }

  main()

  {

  	int list[10],i;

  	printf("请输入10个整数：\n");

  	for(i=0;i<10;i++)

  	{

  		scanf("%d",&list[i]);

  	}

  	QuickSort(list,0,9);

  	for(i=0;i<10;i++)

  	{

  		printf("%d\t",list[i]);

  	}

  	system("pause");

  }

2.插入排序

(1)直接插入法

时间复杂度：最差、平均都是O(n^2)，最好是O(n)

空间复杂度：1

#include<stdio.h>

#include<stdlib.h>

void insertion(int *list,int n)

{

	int i,j,t;

	for(i=1;i<n;i++)//待插入的是list[1]到list[n-1]

	{

		if(list[i]<list[i-1])

		{

			t=list[i];

			list[i]=list[i-1];

			j=i;

			while(t<list[j-1]&&j>=1)

			{

				list[j]=list[j-1];

				j--;

			}

			list[j]=t;

		}

	}

}

main()

{

	int list[10],n=10,i;

	printf("请输入10个整数：\n");

	for(i=0;i<10;i++)

	{

		scanf("%d",&list[i]);

	}

	insertion(list,10);

	for(i=0;i<10;i++)

	{

		printf("%d\t",list[i]);

	}

	system("pause");

}

2）shell排序：分组的插入排序

#include<stdio.h>

#include<stdlib.h>

void ShellPass(int *list,int n,int incre)

{

	int i,j,t,k;//以第一个步长list[0]……list[incre-1]为基准，待插入的是list[incre]……list[n-1]，每个插的时候和自己的增量组比较。

	for(i=incre;i<n;i++)

	{

		if(list[i]<list[i-incre])

		{

			t=list[i];

			list[i]=list[i-incre];

			j=i;

			while(t<list[j-incre]&&j>=incre)

			{

				list[j]=list[j-incre];

				j-=incre;

			}

			list[j]=t;

		}

	}

}

void ShellSort(int *list,int n)

{

	int incre=n;

	while(1)

	{

		incre=incre/3+1;

		ShellPass(list,n,incre);

		if(incre==1)

		{

			break;

		}

	}

}

main()

{

	int list[10],n=10,i;

	printf("请输入10个整数：\n");

	for(i=0;i<10;i++)

	{

		scanf("%d",&list[i]);

	}

	ShellSort(list,10);

	for(i=0;i<10;i++)

	{

		printf("%d\t",list[i]);

	}

	system("pause");

}

3.选择排序

（1）普通选择排序

时间复杂度：最差、平均都是O(n^2)，最好是O(n)

空间复杂度：1

稳定性：不稳定

#include<stdio.h>

void SimpleSort(int *list,int n)

{

	int i,j,k,t;

	for(i=0;i<n;i++)

	{

		k=i;

		for(j=i+1;j<n;j++)

		{

			if(list[j]<list[k])

			{

				k=j;//将比list[k]小的list[j]的j存入k

			}

		}

		if(k!=i)//每进行一次循环找出list[i]到list[n-1]中最小的那个，将这个最小值与list[i]交换位置

		{

			t=list[i];

			list[i]=list[k];

			list[k]=t;

		}

	}

}

main()

{

	int list[10],n=10,i;

	printf("请输入10个整数：\n");

	for(i=0;i<10;i++)

	{

		scanf("%d",&list[i]);

	}

	SimpleSort(list,10);

	for(i=0;i<10;i++)

	{

		printf("%d",list[i]);

	}

	system("pause");

}

(2) 堆排序

#include<stdio.h>

#include<stdlib.h>

//向下调整运算

void AdjustDown(int *h,int i,int n)//待排序数组h[],待调整元素下标号i和序列长度n

{

	int l=2*i+1,j;//l为待调整元素左孩子下标

	int temp=h[i];//待调整元素

	while(l<=n-1)

	{

	  if(l<n-1&&h[l]>h[l+1])

	  {

		l++;//现在l为待调整元素左右孩子中较小孩子的下标

	  }

	  if(temp<h[l])

	  {

		break;//当待调整元素小于左右孩子时，直接退出，调整结束

	  }

	  h[i]=h[l];//交换h[i]和其较小的孩子，由于h[i]保存在temp中，所以可以直接赋值

	  i=l;//为下一次调整做好准备

	  l=l*2+1;

	}

	h[i]=temp;//填入temp，调整结束

	for(j=0;j<10;j++)

	{

		printf("%d\t",h[j]);

	}

	printf("\n");

}

//建立小根堆

void CreatHeap(int *h,int n)

{

	int i,j;

	for(i=(n-2)/2;i>=0;i--)

	{

		printf("%d\n",i);//待调整的元素下标为i

		AdjustDown(h,i,n);//待调整的元素为下标为n/2到0的元素

	}

}

//堆排序

void HeapSort(int *h,int n)

{

	int temp,i;

	CreatHeap(h,n);//得到一个小根堆

	for(i=n-1;i>=0;i--)

	{

	   temp=h[i];//首末位交换，将最小值（首位）和末位交换，排好最小值（即排在最后），再将剩余元素（除最后一个元素外）调整为小根堆

	   h[i]=h[0];

	   h[0]=temp;

	   AdjustDown(h,0,i);

	}

}

void main()

{

	int i,h[10];

	for(i=0;i<10;i++)

	{

		scanf("%d",&h[i]);

	}

	HeapSort(h,10);

	for(i=0;i<10;i++)

	{

		printf("%d\t",h[i]);

	}

	system("pause");

}

注意：堆排序所建立的树不能采用链式存储，只能采用顺序存储

4.归并排序

时间复杂度：最差、平均、最好都是O(nlogn)

空间复杂度：O(n)

#include<stdio.h>

#include<stdlib.h>

void Merge(int *list,int *newlist,int s,int m,int t)

{

	int i,j,k;

	i=s;

	j=m+1;

	k=s;

	while(i<=m&&j<=t)

	{

		if(list[i]<=list[j])

		{

			newlist[k]=list[i];

			k++;

			i++;

		}

		else

		{

			newlist[k]=list[j];

			k++;

			j++;

		}

	}

	while(i<=m)//剩余的若是前一个序列，则其直接按并入newlist

	{

		newlist[k]=list[i];

		i++;

		k++;

	}

	while(j<=t)

	{

		newlist[k]=list[j];

		j++;

		k++;

	}

}

void MSort(int *list,int *newlist,int s,int t)

{

	int *newlist2;

	int m;

	newlist2=(int *)malloc((t-s+1)*sizeof(int));//分配一个新数组，和list等长

	if(s==t)

	{

		newlist[s]=list[s];

	}

	else

	{

		m=(s+t)/2;

		MSort(list,newlist2,s,m);//将list[s]……list[m]递归归并为有序的newlist2[s]……newlist2[m]

		MSort(list,newlist2,m+1,t);//将list[m+1]……list[t]递归归并为有序的newlist2[m+1]……newlist2[t]

		Merge(newlist2,newlist,s,m,t);//将newlist2[s]……newlist2[m]和newlist2[m+1]……newlist2[t]归并到newlist[s]……newlist[t]

	}

}

void MergeSort(int *list,int *newlist,int n)

{

	MSort(list,newlist,0,n-1);

}

main()

{

	int list[10],n=10,i,newlist[10];

	printf("请输入10个整数：\n");

	for(i=0;i<10;i++)

	{

		scanf("%d",&list[i]);

	}

	MergeSort(list,newlist,10);

	for(i=0;i<10;i++)

	{

		printf("%d",newlist[i]);

	}

	system("pause");

}

最后，总结一下各种排序算法时间空间复杂度比较

大类|排序方法|时间复杂度|空间复杂度|稳定性|备注

----|-------|---------|--------|------

交换法|冒泡法|最差、平均都是O(n^2),最好是O(n)|1|稳定|n较小时较好

交换法|鸡尾酒冒泡法|最差、平均都是O(n^2),最好是O(n)|1|稳定|n较小时较好

交换法|快速排序|平均O(nlogn),最坏是O(n^2)|O(logn)|不稳定|n大时较好

插入法|直接插入法|最差、平均都是O(n^2),最好是O(n)|1|稳定|大部分已排序时较好

插入法|希尔排序（分组的插入法）|平均是O(nlogn)|1|不稳定

选择法|普通选择|最差、平均都是O(n^2)|1|不稳定|n较小时较好

选择法|堆排序|最差、平均、最好都是O(nlogn)|1|不稳定|n大时较好

归并排序|归并排序|最差、平均、最好都是O(nlogn)|O(n)|稳定|n大时较好

基数排序|基数排序|O(dn)(d是常数）|O(n)|稳定

巴特西