排序算法練習——代碼匯總

之前寫的插入排序，合並排序，堆排序，快速排序，計數排序算法，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];
	}