排序算法练习——代码汇总

之前写的插入排序，合并排序，堆排序，快速排序，计数排序算法，C++源码，发出来，大家共同学习。^_^

//排序算法汇总练习

#include "stdafx.h"
#include <iostream>

using namespace std;

	void InsertSort();//声明插入排序函数

	void MergeSort(int num[],int left,int right);//声明合并排序函数
	void Merge(int num[],int left,int right);//声明合并排序中要用到的合并函数

	void HeapSort();//声明堆排序函数
	void BuildHeap();//声明堆排序中用到的建立堆函数
	void HeapIfy(int i);//声明建立堆时要用到的保证堆性质的函数

	void QuickSort(int start,int end);//声明快速排序函数
	int Partition(int start,int end);//声明快速排序中用到的分割函数

	void CountingSort();//声明计数排序函数

	int num[5];
	int main()
	{
		for(int i=0;i<=4;i++)
		cin>>num[i];
		int length=sizeof(num)/sizeof(num[0]);
		CountingSort();
		//QuickSort(0,length-1);
		//HeapSort();
		//InsertSort();
		//MergeSort(num,0,4);
		for(int i=0;i<5;i++)
		cout<<num[i]<<endl;
		system("PAUSE");
		return 0;
	}

	//插入排序函数
	void InsertSort()
	{
		int n=sizeof(num)/sizeof(num[0]);//获取要排序数组的元素个数
		int j,key;
		for(int i=1;i<n;i++)
		{
			j=i-1;
			key=num[i];
			while(j>=0&&num[j]>key) 
			{
				num[j+1]=num[j];
				j--;
			}
			num[j+1]=key;
		}
	}

	//合并排序函数
	void MergeSort(int num[],int left,int right)
	{
		if(left<right)
		{
			int i=(left+right)/2;
			MergeSort(num,left,i);
			MergeSort(num,i+1,right);
			Merge(num,left,right);
		}
	}

	void Merge(int num[],int left,int right)
	{
		int i=left,j=(left+right)/2;
		int temp[10];
		for(int q=0;q<10;q++)
			temp[q]=0;
		int m=left,n=j+1;
		while(m<=j&&n<=right)
		{
			if(num[m]<num[n])
				temp[i++]=num[m++];
			else if(num[m]>=num[n])
				temp[i++]=num[n++];
		}
		if(m>j)
		{
			while(n<=right)
				temp[i++]=num[n++];
		}
		else
		{
			while(m<=j)
				temp[i++]=num[m++];
		}
		for(i=left;i<=right;i++)
		{
			num[i]=temp[i];
		}
	}

	//堆排序函数，注意堆排序时考虑树节点排序是从1开始，数组下标从0开始，所以相应减1
	void HeapIfy(int i,int length)
	{
		int l=2*i;
		int r=2*i+1;
		int largest,temp;
		if(num[l-1]>num[i-1]&&l<=length)
			largest=l;
		else
			largest=i;
		if(num[r-1]>num[largest-1]&&r<=length)
			largest=r;
		if(largest!=i)
		{
			temp=num[i-1];
			num[i-1]=num[largest-1];
			num[largest-1]=temp;
			HeapIfy(largest,length);
		}
	}
	void BuildHeap()
	{
		int length=sizeof(num)/sizeof(num[0]);
		for(int i=length/2;i>=1;i--)
			HeapIfy(i,length);
	}
	void HeapSort()
	{
		int length=sizeof(num)/sizeof(num[0]);
		int temp;
		BuildHeap();
		for(int i=length;i>=1;i--)
		{
			temp=num[i-1];
			num[i-1]=num[0];
			num[0]=temp;
			HeapIfy(1,i-1);
		}
	}

	//快速排序算法函数
	int Partition(int start,int end)
	{
		int x=num[start];
		int i=start;
		int j=end;
		int temp;
		while(num[i]<x){
			i++;
		}
		while(num[j]>x){
			j--;
		}
		if(i<j)
		{
			temp=num[j];
			num[j]=num[i];
			num[i]=temp;
		}
		else
		{
			return j;
		}
	}

	void QuickSort(int start,int end)
	{
		if(start<end)
		{
			int m=Partition(start,end);
			QuickSort(start,m);
			QuickSort(m+1,end);
		}
	}

	//计数排序，适用于被排序元素大小在1~k之间的排序
	void CountingSort( )
	{
		int n=sizeof(num)/sizeof(num[0]);
		int numTemp[5]; //临时存储排序结果
		int temp[6];//数组元素个数为排序元素中的最大值+1
		for(int i=0;i<6;i++)
		{
			temp[i]=0;
		}
		for(int j=0;j<n;j++)
		{
			temp[num[j]]=temp[num[j]]+1;
		}
		for(int k=1;k<6;k++)
		{
			temp[k]=temp[k]+temp[k-1];
		}
		for(int l=n-1;l>=0;l--)
		{
			numTemp[temp[num[l]]-1]=num[l];
			temp[num[l]]--;
		}
		for(int m=0;m<n;m++)
			num[m]=numTemp[m];
	}

补充：软件开发 , C++ ,