七种排序算法

1.直接插入排序

#include<stdio.h>
void insertSort(int a[],int n)
{
	int i,j,temp;
	for(i=0;i<n-1;i++)
	{
		temp = a[i+1];
		j = i;
		while(j>-1 && a[j]>temp)
		{
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = temp;
	}
}
void main()
{
	int i,n=6;
	int m[] = {12,3,5,0,34,29};
	insertSort(m,n);
	for(i=0 ; i<n ; i++)
	{
		printf("%d  ",m[i]);
	}
}

 

2.shell排序

#include<stdio.h>
void shellSort(int a[],int n,int d[],int h)
{
	int m,i,j,temp,span,k;
	for(m=0 ; m<h ; m++)  //共循环h次
	{
		span = d[m];  //取本次的增量
		for(k=0 ; k<span ; k++)   //共分span个小组
		{
			for(i=k ; k<n-span ; k=k+span)   //对每个小组进行直接插入排序
			{
				temp = a[i+span];
				j = i;
				while(j>-1 && a[j]>temp)
				{
					a[j+span] = a[j];
					j = j - span;
				}
				a[j+span] = temp;
			}
		}
	}
}
void main()
{
	int i,n=6,h=2;
	int m[] = {12,3,5,0,34,29};
	int d[] = {3,1};
	shellSort(m,n,d,h);
	for(i=0 ; i<n ; i++)
	{
		printf("%d  ",m[i]);
	}
}

 

3. 直接选择排序

#include<stdio.h>
void selectSort(int a[],int n)
{
	int i,j,small,temp;
	for(i=0 ; i<n-1 ; i++)
	{
		small = i;  //设第i个数据元素最小
		for(j=i+1 ; j<n ; j++)  //从第i个元素以后寻找最小的数据元素
		{
			if(a[j] < a[small])
			{
				small = j;  //记住最小元素的下标
			}
		}
		if(small != i)  //当最小元素的下标不为i时交换数据
		{
			temp = a[i];
			a[i] = a[small];
			a[small] = temp;
		}
	}
}
void main()
{
	int i,n=6;
	int m[] = {12,3,5,0,34,29};
	selectSort(m,n);
	for(i=0 ; i<n ; i++)
	{
		printf("%d  ",m[i]);
	}
}

 

4.堆排序

#include<stdio.h>
void creatHeap(int a[],int n,int h)
{
	int i=h;     //i为要建堆的二叉树根结点下标
	int j=2*i+1; //j为i的左孩子结点的下标
	int tag=0;
	int temp=a[i];
	while(j<n && tag!=1) //沿左右孩子中值较大者重复向下筛选
	{
		//寻找左右孩子节结中的较大者，j为其下标
		if(j<n-1 && a[j]<a[j+1])
		{
			j++;
		}
		if(temp > a[j])
		{
			tag = 1;  //标记结束筛选条件
		}
		else //否则把a[j]上移
		{
			a[i] = a[j];
			i = j;
			j = 2*i+1;
		}
	}
	a[i] = temp; //把最初的a[i]赋予最后的a[j]
}
void intiCreatHeap(int a[],int n)
{
	int i;
	for(i=(n-1)/2 ; i>=0 ; i--)
	{
		creatHeap(a,n,i);
	}
}
void heapSort(int a[],int n)
{
	int i,temp;
	intiCreatHeap(a,n);  //初始化创建最大堆
	for(i=n-1 ; i>0 ; i--)  //当前最大堆个数每次递减1
	{//把堆顶a[0]元素与当前最大堆的最后一个元素交换
		temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		creatHeap(a,i,0); //调整根结点满足最大堆
	}
}
void main()
{
	int i,n=6;
	int m[] = {12,3,5,0,34,29};
	heapSort(m,n);
	for(i=0 ; i<n ; i++)
	{
		printf("%d  ",m[i]);
	}
}

 

5. 冒泡排序

#include<stdio.h>
void bubbleSort(int a[],int n)
{
	int i,j,temp,tag=1;
	for(i=1 ; i<n && tag==1 ; i++)
	{
		tag = 0;
		for(j=0 ; j<n-i ; j++)
		{
			if(a[j]>a[j+1])
			{
				tag = 1;
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}
}
void main()
{
	int i,n=6;
	int m[] = {12,3,5,0,34,29};
	bubbleSort(m,n);
	for(i=0 ; i<n ; i++)
	{
		printf("%d  ",m[i]);
	}
}

 

6.快速排序

#include<stdio.h>
void quickSort(int a[],int low,int high)
{
	int i=low,j=high,temp=a[low];
	while(i < j)
	{
		while(i<j && temp<=a[j])
		{
			j--;
		}
		if(i < j)
		{
			a[i] = a[j];
			i++;
		}
		while(i<j && temp>a[i])
		{
			i++;
		}
		if(i < j)
		{
			a[j] = a[i];
			j--;
		}
	}
	a[i] = temp;
	if(i > low)
	{
		quickSort(a,low,i-1);
	}
	if(i < high)
	{
		quickSort(a,i+1,high);
	}
}
void main()
{
	int i,n=6;
	int m[] = {12,3,5,0,34,29};
	quickSort(m,0,n-1);
	for(i=0 ; i<n ; i++)
	{
		printf("%d  ",m[i]);
	}
}

 

7. 归并排序

#include<stdio.h>
void merge(int a[],int n,int swap[],int k)//k为有序子数组的长度
{
	int l1=0,u1,l2,u2,i,j,m=0;//第一个有序子数组下界为0
	while(l1+k <= n-1)
	{
		u1=l1+k-1;//第一个有序子数组上界
		l2=u1+1;  //第二个有序子数组下界
		u2=l2+k-1<=n-1 ? l2+k-1 : n-1;  //第二个有序子数组上界
		for(i=l1,j=l2 ; i<=u1&&j<=u2 ; m++)//两个有序子数组合并
		{
			if(a[i] <= a[j])
			{
				swap[m] = a[i];
				i++;
			}
			else
			{
				swap[m] = a[j];
				j++;
			}
		}
		while(i <= u1)//将子数组1中剩余的元素存放到swap中
		{
			swap[m] = a[i];
			m++;
			i++;
		}
		while(j <= u2)//将子数组2中剩余的元素存放到swap中
		{
			swap[m] = a[j];
			m++;
			j++;
		}
		l1 = u2+1;
	}
//将原始数组中只够一组的数据元素顺序存放到数组swap中
	for(i=l1 ; i<n ; i++,m++)	
{
		swap[m] = a[i];
	}
}
void mergeSort(int a[],int n)
{
	int i,k=1;//归并长度从1开始
	int *swap=(int *)malloc(sizeof(int)*n);//申请动态数组空间
	while(k < n)
	{
		merge(a,n,swap,k);
		for(i=0 ; i<n ; i++)
		{
			a[i] = swap[i];//将元素从临时数组swap放回数组a中
		}
		k = k*2;  //归并长度加倍
	}
	free(swap);//释放动态数组空间
}
void main()
{
	int i,n=6;
	int m[] = {12,3,5,0,34,29};
	mergeSort(m,n);
	for(i=0 ; i<n ; i++)
	{
		printf("%d  ",m[i]);
	}
}