简单排序算法的实现

/*以下是本人根据常见排序算法的思想，在visual c++6.0中进行实现，由于算法方面不是很擅长，所以如果您发现其中的错误，
或有更好的实现策略，希望您能不吝赐教！*/

/*
  简单选择排序第i趟需比较n-i次，交换记录至多3次
  共需比较次数(n-1)+(n-2)+(n-3)+.....+2+1=n*(n-1)/2;即时间复杂度为O（n2)
  空间复杂度为0（1）；
*/
#include<iostream>
using namespace std;
void sort(int a[],int length)
{
	int i,j;
	int temp,port;
	for(i=0;i<length-2;i++)
	{
		temp=a[i];
		port=i;
		for(j=i+1;j<length-1;j++)
		{
			if(a[j]<temp)
			{
				temp=a[j];
				port=j;
			}
		}
		if(port!=i)
		{
			a[port]=a[i];
			a[i]=temp;
		}
	}
}
void main()
{
	int a[5]={5,8,2,4,9};
	sort(a,5);
	for(int i=0;i<5;i++)
		cout<<a[i]<<" ";
}



/*
 起泡排序  时间复杂度O(n^2)  空间复杂度 O(1)
   比较次数n*(n-1)/2    
*/
#include<iostream>
using namespace std;
void sort(int a[],int length)
{
	int temp;
	for(int i=0;i<length-1;i++)
		for(int j=i+1;j<length;j++)
			if(a[j]<a[i])
			{
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
}
void main()
{
	int a[5]={8,6,2,9,1};
	sort(a,5);
	for(int i=0;i<5;i++)
		cout<<a[i]<<" ";
}



/**
希尔排序 又称缩小增量排序    本程序步长为5/3/1
*/
#include<iostream>
using namespace std;
void sort(int a[],int length,int step,int start)
{
	int i,j;
	int temp;
	for(i=step+start;i<length;i+=step)
	{
		temp=a[i];
	
		for(j=i-step;j>=0;j-=step)
		{
			if(temp<a[j])
			{
				a[j+step]=a[j];
				a[j]=temp;
				
			}
		    else
				break;
		}
	}
}
void xiersort(int a[],int length)
{
	int i;
	int step=5;
	for(i=0;i<step;i++)
		sort(a,length,step,i);
	step=3;
	for(i=0;i<step;i++)
		sort(a,length,step,i);
	step=1;
	for(i=0;i<step;i++)
		sort(a,length,step,i);
}
void main()
{
	int a[10]={7,6,9,11,4,10,2,5,16,8};
	xiersort(a,10);
	for(int i=0;i<10;i++)
		cout<<a[i]<<" ";
}


/**
Fun:直接插入排序
*/
#include<iostream>
using namespace std;
void sort(int a[],int length)
{
	int temp;
	for(int i=1;i<=length;i++)
	{
		temp=i;
		for(int j=i-1;j>=0;j--)
		{
			if(a[j]>a[i])
				temp=j;
			else
				break;
		}
		if(temp!=i)
		{
			int tempnum=a[i];
			for(int k=i-1;k>=temp;k--)
				a[k+1]=a[k];
			a[temp]=tempnum;
		}
	}
}
	void main()
	{
		int a[6]={4,6,8,1,3,9};
		sort(a,5);
		for(int k=0;k<=5;k++)
			cout<<a[k]<<" ";
	}