各类排序算法总结

#include "stdio.h"
#include "stdlib.h"

void swap(int a[],int i,int j)
{
	int temp;
	temp=a[i];
	a[i]=a[j];
	a[j]=temp;

}
/*选择排序数组实现 每次从无序区里面选择一个最小的数插入到有序区 有序区从0开始即开始无元素*/

void selectSort(int a[],int l)
{
	int i,j,index;
	for(i=0;i<l;i++)
	{
		index = i;
		for(j=i+1;j<l;j++)
		{
			if(a[j]<a[index])index=j;//每次找最小的值，定位最小的坐标
		}
		//for j循环后 判定最小下标是否改变
		if(index!=i)
		{
			swap(a,index,i);
		}
	}
}

/*插入排序数组实现 每次从无序区里面选择一个值，插入到有序区里面 有序区从1开始即开始是数组第一个元素*/
void insertSort(int a[],int l)
{
	int i,j;
	//i之前有序，i之后无序
	for(i=1;i<l;i++)
	{
		for(j=i;j>0;j--)
			if(a[j]<a[j-1])
			{
				swap(a,j,j-1);
			}
	}
}

/*冒泡排序数组实现 每次循环一趟,根据两相邻的数组值比较，最大的上浮，一趟结束后，数组的最后一个值即最大值,下次每次循环从数组最大下标-1开始*/
void bubbleSort(int a[],int l)
{
	int i,n;
	int flag = 0;//设置判定标示 提供冒泡效率
	n=l-1;
	//第一次要比较(冒泡)l-1次，依次类推
	while(n)
	{
		flag = 0;//每次循环前复位
		for(i=0;i<=n;i++)
		{
			if(a[i]>a[i+1])
			{
				swap(a,i,i+1);
				flag=1;//有比较则标示
			}
		}
		//判定每次循环是否有比较，无比较则退出循环
		if(!flag)break;
		n--;
	}
}
/*快速排序之一趟排序 定中间位 比较难理解，最好看看图形示意*/
int partition(int a[],int s,int e)
{
	int key=a[s];
	while(s<e)
	{
		while(s<e&&key<=a[e])e--;
		if(s<e)a[s++]=a[e];
		while(s<e&&a[s]<=key)s++;
		if(s<e)a[e--]=a[s];
	}
	a[s]=key;
	return s;
}

/*快速排序的数组实现 采用分而治之的思想，每次拿数组的第一个元素作为中间元素，其左边的比该元素小，其右边的比该元素大，递归...最后有序*/
void quickSort(int a[],int s,int e)
{
	if(s<e)//不是while 很要命
	{
		int i = partition(a,s,e);
		//printf("i=%d\n",i);
		quickSort(a,s,i-1);
		quickSort(a,i+1,e);
	}
}


/*归并排序之 二路归并排序*/

void main()
{
	int a[8]={3,4,2,8,6,4,5,1},k;
	printf("初始序列\n");
	for(k=0;k<8;k++)printf("%d ",a[k]);
	printf("\n\n");
	printf("选择排序后结果\n");
	quickSort(a,0,7);
	for(k=0;k<8;k++)printf("%d ",a[k]);
//	bubbleSort1(a,8);
//	printf("插入排序后结果\n");
	//printf("快速排序后结果\n");
	//quickSort(a,0,7);
//	for(k=0;k<8;k++)printf("%d ",a[k]);
}