排序学习

学习记录

堆排序+冒泡+选择+插入+折半插入+快排

#include\"stdio.h\"
#include<iostream>
using namespace std;
void adjustHeap(int a[],int i,int length)
{
	int temp=a[i];
	for(int k=i*2+1;k<length;k=k*2+1)
	{
		if(k+1<length&&a[k]<a[k+1])
		k++;

		if(a[k]>temp)
		{
			a[i]=a[k];
			i=k;
		}
		else
		break;
	}
	a[i]=temp;
}
void heapSort(int a[],int n)
{
	//construct big peak heap
	for(int i=n/2-1;i>=0;i--)
	{
		adjustHeap(a,i,n);
	}

	for(int j=n-1;j>0;j--)
	{
		int temp;
		temp=a[0];
		a[0]=a[j];
		a[j]=temp;

		adjustHeap(a,0,j);
	}
}


void chooseSort(int a[],int n)
{
	int i,j,min,pos;
	
	for(i =0;i<n;i++)
	{
		pos=0;
		min=999999998;
		for(j=i;j<n;j++)
		{
			if(a[j]<min)
			{
				min=a[j];
				pos=j;
			}
		}
		a[pos]=a[i];
		a[i]=min;
	}
}

void halfInsertSort(int a[],int n)
{
	int i,j,temp,low,high,mid;
	for(i=1;i<n;i++)
	{
		if(a[i]<a[i-1])
		{
			temp=a[i];
			low=0,high=i-1;
			while(low<=high)
			{
				mid=(low+high)/2;
				if(a[mid]>temp) high=mid-1;
				else low=mid+1;
			}
			for(j=i-1;j>=high+1;j--) a[j+1]=a[j];

			a[high+1]=temp;
		}
	}
}

void insertSort(int a[],int n)
{
	int i,j,temp;
	for(i=1;i<n;i++)
	{
		if(a[i]<a[i-1])
		{
			temp=a[i];
			for(j=i-1;a[j]>temp&&j>=0;j--)
			{
				a[j+1]=a[j];
			}
			a[j+1]=temp;
		}
	}
}


void bubbleSort(int a[],int n)
{
	int i,j,temp;
	for(i=0;i<n;i++)
	{
		for(j = 0;j<n-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
}
void quickSort(int a[],int left,int right)
{
	if(left>=right)
		return;
	int j=left,k=right;
	int   = a[j];
	while(j<k)
	{
		for(;j<k;k--)
		{
			if(a[k]< )
			{
				a[j]=a[k];
				break;
			}
		}
		for(;j<k;j++)
		{
			if(a[j]> )
			{
				a[k] = a[j];
				break;
			}
		}
	}
	a[j] =  ;

	quickSort(a,left,j-1);
	quickSort(a,j+1,right);
}
int main()
{
	int i = 0;
	int a[20]={20,3,5,78,90,54,95,1,3,5,9,7,97,11,115,599,48,794,322,233};
	int b[20]={20,3,5,78,90,54,95,1,3,5,9,7,97,11,115,599,48,794,322,233};
	int c[20]={20,3,5,78,90,54,95,1,3,5,9,7,97,11,115,599,48,794,322,233};
	int d[20]={20,3,5,78,90,54,95,1,3,5,9,7,97,11,115,599,48,794,322,233};
	int e[20]={20,3,5,78,90,54,95,1,3,5,9,7,97,11,115,599,48,794,322,233};
	int f[20]={20,3,5,78,90,54,95,1,3,5,9,7,97,11,115,599,48,794,322,233};
	int length = 20;

	
	quickSort(a,0,length-1);
	bubbleSort(b,length);
	insertSort(c,length);
	halfInsertSort(d,length);
	chooseSort(e,length);
	heapSort(f,length);

	cout<<\"quickSort conclusion:\";
	for(i = 0;i<length;i++)
		cout<<a[i]<<\" \";

	cout<<endl;
	cout<<\"bubbleSort conclusion:\";
	for(i = 0;i<length;i++)
		cout<<b[i]<<\" \";

	cout<<endl;
	cout<<\"insertSort conclusion:\";
	for(i = 0;i<length;i++)
		cout<<c[i]<<\" \";

	cout<<endl;
	cout<<\"halfInsertSort conclusion:\";
	for(i = 0;i<length;i++)
		cout<<d[i]<<\" \";

	cout<<endl;
	cout<<\"chooseSort conclusion:\";
	for(i = 0;i<length;i++)
		cout<<e[i]<<\" \";

	cout<<endl;
	cout<<\"chooseSort conclusion:\";
	for(i = 0;i<length;i++)
		cout<<f[i]<<\" \";

	return 0;

}

堆排序参考：https://www.cnblogs.com/chengxiao/p/6129630.html