数据结构--排序

#include "stdafx.h"

#define uint8 unsigned char 

void swap(uint8 *a,uint8 *b)
{
	uint8 temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

void printf_array(uint8 *a,uint8 n)
{
	uint8 i;
	for(i=0;i<n;i++) 
	{ 
		printf( "%d  ",a[i]);
	} 
	printf("\n");
}
//直接插入排序
void simple_insert_sort(uint8 *a,uint8 len)
{
	uint8 i,j,k,temp;
	for(i=1;i<len-1;i++)
	{
		temp=a[i];
		for(j=0;j<i;j++)
		{
			if(temp<=a[j])         
			{
				for(k=i;k>=j+1;k--)      //记录后移
					a[k]=a[k-1];
				a[j]=temp;              //插入较小的记录
				break;
			}
		}
	}
}

//起泡排序

void buble_sort(uint8 *a,uint8 len)
{
	uint8 i,j,temp;
	for(i=len-1;i>=1;i--)  
	{
		for(j=0;j<=i-1;j++)         
		{
			if(a[j]>a[j+1])
				swap(&a[j],&a[j+1]);
		}
	}
}

//快速排序

uint8 partition(uint8 *a,uint8 low,uint8 high)
{
	uint8 key;
	key=a[low];
	while(low<high)
	{
		while(low<high&&a[high]>=key)
			high--;
		a[low]=a[high];
		while(low<high&&a[low]<=key)
			low++;
		a[high]=a[low];
	}
	a[low]=key;
	return low;
}

void fast_sort(uint8 *a,uint8 low,uint8 high)
{
	uint8 mid;
	if(low<high)
	{
		mid=partition(a,low,high);
		fast_sort(a,low,mid);
		fast_sort(a,mid+1,high);
	}
}

//简单选择排序
uint8 get_min(uint8 *a,uint8 first,uint8 last)  //从first 和last直接找到最小值
{
	uint8 min,i;
	min=first;
	for(i=first+1;i<=last;i++)
	{
		if(a[min]>a[i])
			min=i;
	}
	return min;
}
void select_sort(uint8 *a,uint8 len)
{
	uint8 min,i;
	for(i=0;i<=len-2;i++)
	{
		min=get_min(a,i,len-1);      //获得i~len-1之间的最小值
		if(min!=i)
			swap(&a[i],&a[min]);     //交换两个元素
	}
}


//堆排序
uint8 get_max_heap(uint8 *a,uint8 index,uint8 len)
{
	uint8 max,left,right;
	max=index;
	left=max*2;
	right=max*2+1;
	if(left<len&&a[left]>a[max])
		max=left;
	if(right<len&&a[right]>a[max])
		max=right;
	return max;
}

void heap_adjust(uint8 *a,uint8 index,uint8 len)
{
	uint8 i,max;
	for(i=index;i<len;)
	{
		max=get_max_heap(a,i,len);
		if(max==i)
			return;
		else
		{
			swap(&a[max],&a[i]);
			i=max;
		}
	}
}

void heap_sort(uint8 *a,uint8 len)
{
	int i;
	for(i=(len-1)/2;i>=0;i--)
		heap_adjust(a,i,len);       //将0~len-1调整成大堆
	for(i=len-1;i>0;i--)
	{
		swap(&a[i],&a[0]);
		heap_adjust(a,0,i);       //将0~i-1调整成大堆
	}
}

//归并排序

void merge(uint8 *a,uint8 first,uint8 mid,uint8 last)
{
	uint8 i,j,m,n;
	uint8 b[20];
	m=first;
	n=mid+1;
	for(i=first;i<=last;i++)
	{
		if(m>mid) //第一段复制完毕
		{
			for(j=n;j<=last;j++)
			{
				b[i-first]=a[j];
				i++;
			}
		}
		if(n>last)  //第二段复制完毕
		{
			for(j=m;j<=mid;j++)
			{
				b[i-first]=a[j];
				i++;
			}
		}
		if(a[m]<=a[n])
		{
			b[i-first]=a[m];
			m++;
		}
		else
		{
			b[i-first]=a[n];
			n++;
		}
	}
	for(i=first;i<=last;i++)
		a[i]=b[i-first];
}

void merge_sort(uint8 *a,uint8 first,uint8 last)
{
	uint8 mid;
	if(first<last)
	{
		mid=(first+last)/2;
		merge_sort(a,first,mid);
		merge_sort(a,mid+1,last);
		merge(a,first,mid,last);
	}
}

void main() 
{ 
	int location,i,len;
	unsigned char mydata[20]={64,12,55,40,27,36,73,49,81,98};
	len=10;
	printf_array(mydata,len);
	merge_sort(mydata,0,len-1);
	printf_array(mydata,len);
	while(1);
}