排序 C语言实现

时间:2022-01-05 12:29:28
//冒泡排序
#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);
}

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