各种排序算法（c语言）

c语言小白，写文章方便复习记忆。

冒泡排序

从第一个元素开始，依次与后面元素进行比较，较大者放在后面，比较完一轮后，最大的在最后一个。然后再对除最大的元素外进行比较。

直接插入排序

a[0]作哨兵，将待插入的记录与有序区中的各记录自右向左依次比较其关键字值的大小，较大者放在后面，先比较前两个，依次增大范围，相当于插入。

快速排序

a[0]做哨兵，从后或前向中间遍历，保证后面的比他大，前面的比他小，否则将其放在相应位置并转到前或后继续遍历。

选择排序

将第一个元素与其他元素比较，小的放在第一个位置，这样前面的都是最小的。

二路归并排序

先对所要进行排序的序列进行分解，直到分为单个元素为止，然后将其进行两两合并。由于最终分解成单个元素，因此在合并的时候.将小数放在前面，大数放在后面，得到一个有序序列。接下来对两个相连的有序序列进行排序，先比较有序序列中的第一个元素，将较小的元素放入临时数组中，接着将较小元素所在数组的下一个元素与另一个数组中的较小元素比较，同样将较小元素放入临时数组中，依次进行，直到两个数组的所有元素都放入临时数组中，最后再将临时数组的元素放入原始数组中的对应位置。

希尔排序

将排序的序列按固定增量分成若干组，等距者在同二组中，然后再在组内进行直接插入排序，然后间距减半，继续进行直接插入排序。

时间复杂度

时间复杂度（平均）
直接插入排序 O(n^2)
希尔排序 O(n^1.3)
选择排序 O(n^2)
冒泡排序 O(n^2)
快速排序 O(nlogn)
归并排序 O(nlogn)

#include<stdio.h>
//冒泡
void maopao(int *num,int n)
{
	int tmp,i;
	for(i=0;i<n;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(num[j]>num[j+1])
			{
				tmp = num[j];
				num[j] = num[j+1];
				num[j+1] = tmp;
			}
		}
	}
	for(i = 0;i<n;i++)
	{
		printf("%d ",num[i]);
	}
}
//直接插入排序
void zhicha(int *num,int n)
{
	int a[100];
	int j;
	for(int i=1;i<n+1;i++)
	{
		a[i]=num[i-1];
	}
	for(i=2;i<=n;i++)
	{
		a[0]=a[i];
		j=i-1;
		while(a[j]>a[0])
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=a[0];
	}
	for(i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
}
//快速排序
void qusort(int *a,int start,int end)
{
	int i,j;
	i=start;
	j=end;
	a[0]=a[start];
	while(i<j)
	{
		while(i<j&&a[0]<a[j])
			j--;
		if(i<j)
		{
			a[i]=a[j];
			i++;
		}
		while(i<j&&a[0]>a[i])
			i++;
		if(i<j)
		{
			a[j]=a[i];
			j--;
		}
	}
	a[i]=a[0];
	if(start<i)
		qusort(a,start,j-1);
	if(i<end)
		qusort(a,j+1,end);
}
//选择排序
void xuanze(int *a,int n)
{
	int temp;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]>a[j])
			{
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
	}
}
//二路归并排序
void merge(int a[],int start,int mid,int end)
{
	int tmp[100];
	int i=start;
	int j=mid+1;
	int k=0;
	while(i<=mid&&j<=end)
	{
		if(a[i]<a[j])
		{
			tmp[k++]=a[i++];
		}
		else
		{
			tmp[k++]=a[j++];	
		}
	}
	if(i<=mid)
	{
		while(i<=mid)
			tmp[k++]=a[i++];
	}
	if(j<=end)
	{
		while(j<=end)
			tmp[k++]=a[j++];
	}
	for(j=0,i=start;j<k;i++,j++)
	{
		a[i]=tmp[j];
	}
}
void mergesort(int a[],int start,int end)
{
	if(start>=end)
		return;
	int mid=(start+end)/2;
	mergesort(a,start,mid);
	mergesort(a,mid+1,end);
	merge(a,start,mid,end);
}
//希尔排序
void shsort(int a[],int n)
{
	int i,j,d;
	d=n/2;
	while(d>=1)
	{
		for(i=d+1;i<=n;i++)
		{
			a[0]=a[i];
			j=i-d;
			while(a[j]>a[0]&&j>0)
			{
				a[j+d]=a[j];
				j=j-d;
			}
			a[j+d]=a[0];
		}
		d=d/2;
	}
	
}
void main()
{
	int n;
	printf("请输入数组长度");
	scanf("%d",&n);
	int num[100];
	printf("请输入数组内容");
	for(int i = 1;i<=n;i++)
	{
		scanf("%d",&num[i]);
	}
	shsort(num,n);
	for(i=1;i<=n;i++)
		printf("%d ",num[i]);
}

主函数要稍作改变。

最后

以上就是沉默蜻蜓为你收集整理的各种排序算法（c语言）的全部内容，希望文章能够帮你解决各种排序算法（c语言）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。