欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序 C语言实现

程序员文章站 2022-03-24 15:33:42
...
//冒泡排序
#define ElementType int
void x_sort(ElementType a[],int n)
{
	for (int i = 1; i < n; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - i; j++)
		{
			if (a[j]>a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = 1;
			}
		}
		if (flag == 0)
			break;
	}
}


//插入排序

void Insertion_Sort(ElementType a[], int n)
{
	for (int p = 1; p < n; p++)
	{
		int temp = a[p];
		int i = p;
		for (i; i>0 && a[i - 1] > a[i]; i--)
			a[i] = a[i - 1];
		a[i] = temp;
	}
}

//希尔排序
void Shell_Sort(ElementType a[], int n)
{
	for (int d = n / 2; d > 0;d/=2)
	for (int p = d; p < n; p++)
	{
		int temp = a[p];
		int i = p;
		for (i; i>0 && a[i - d] > a[i]; i--)
			a[i] = a[i - d];
		a[i] = temp;
	}
}

//归并排序
void Merge(ElementType a[], ElementType b[],int L,int R,int RightEnd)
{
	int LeftEnd = R - 1;
	int Temp = L;
	int NumElements = RightEnd - L + 1;
	while (L <= LeftEnd&&R <= RightEnd)
	{
		if (a[L] <= a[R])
			b[Temp++] = a[L++];
		else
			b[Temp++] = a[R++];

	}
	while (L <= LeftEnd)
		b[Temp++] = a[L++];
	while (R <= RightEnd)
		b[Temp++] = a[R++];
	for (int i = 0; i < NumElements; i++, RightEnd--)
	{
		a[RightEnd] = b[RightEnd];
	}
}
//分治归并递归体现
void MSort(ElementType a[], ElementType b[], int L,int RightEnd)
{
	int Center;
	if (L < RightEnd)
	{
		Center = (L + RightEnd) / 2;
		MSort(a,b,L,Center);
		MSort(a,b,Center+1,RightEnd);
		Merge(a,b,L,Center+1,RightEnd);
	}
}
void Merge_sort(ElementType a[], int n)
{
	ElementType *b;
	b = (ElementType*)malloc(n*sizeof(ElementType));
	if (b)
	{
		MSort(a, b, 0, n - 1);
		free(b);
	}
	else
		printf("空间不足");
}

//快速排序
void swap(int *a, int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void quickSort(ElementType a[],int L,int R)
{
	if (L >= R)
		return;
	int p = a[L];
	int i = L;
	int j = R;
	while (i != j)
	{
		while (i < j&&a[j] >= p)
			j--;
		swap(&a[i], &a[j]);
		while (i < j&&a[i] <= p)
			i++;
		swap(&a[i], &a[j]);
	}
	quickSort(a,L,i-1);
	quickSort(a,i+1,R);
}

//基数排序(自我实现)