排序算法總結（C++語言）

今天靜下心來對一些排序算法進行總結，全部使用c++語言。

//按名次排序
template 
void Rearrange(T a[],int n,int r[])
{
	//按序重排數組a中的元素，使用附加數組u
	T *u=new T[n+1];
	//在u中移動到正確的位置
	for(int i=1;i
void SelectionSort(T a[],int n)
{
	//對數組a[0:n-1]中的n個元素進行排序
	for(int size=n;size>1;size--)
	{
	   int j=Max(a,size);
	   Swap(a[j],a[size-1]);
	}
}

//冒泡排序
template 
void Bubble(T a[],int n)
{
	//把數組a[0:n-1]中最大的元素冒泡移到右邊
	for(int i=n;i>1;i--)
           for(int j=0;ja[j+1])
	     Swap(a[j],a[j+1]);   
}

//向一個有序數組中插入元素
template 
void Insert(T a[],int& n,const T& x)
{
	//向有序數組a中插入元素x
	//假定a的大小超過n
	int i;
	for(i=n-1;i>=0&&x
void SelectionSort(T a[],int n)
{
	//及時終止的選擇排序
	bool sorted=false;
	for(int size=n;!sorted&&(size>1);size--)
	{
	   int pos=0;
	   sorted=true;
	   //找最大元素
	   for(int i=1;i
void BubbleSort(T a[],int n)
{
	//及時終止的冒泡排序
	bool swapped=FALSE;
	for(int i=n;i>1&&!swapped;i--)
	{  
	   swapped=true;
	   for(int j=0;ja[j+1])
	     {
   	     	Swap(a[j],a[j+1]);
	     	swapped=false;
	     }
	}
}

//插入排序
template 
void InsertionSort(T a[],int n)
{
	for(int i=1;i=0&&t
void shellsort(vector& a)
{
	for(int gap = a.size()/2;gap>0;gap /= 2)
	   for(int i = gap;i < a.size();i++)
	   {
   		T tmp = a[i];
		int j = i;
		for(j=i;j>=gap&&tmp
void HeapSort(T a[],int size,int n)
{//利用堆排序算法對a[1:n]進行排序
 //創建一個最大堆
 //	MaxHeap H(1);
 //	H.Initialize(a,n,n);
 	delete [] heap;
	heap = a;
	currentsize = size;
	for(int i = currentsize/2;i>=1;i--)
	{
		T y = heap[i];
		int c = 2*i;
		while(c<=currentsize)
		{
			if(c heap[c])
				break;
			heap[c/2] = heap[c];
			c*=2;
		}
		heap[c/2] = y;
	}
 //從最大堆中逐個抽取元素
 	T x;
	for(int i = n-1;i >= 1;i--)
	{
		H.DeleteMax(x);
		a[i+1] = x;
	}
//在堆的析構函數中保存數組a
	H.Deactivate();

}

//快速排序(遞歸方法)
void quickSort(T a[],int l,int r)
{
	if (l > r)
		return;
	if (r-lpivot);
		if(i>=j)
			break;
		Swap(a[i],a[j]);
	}
	
	a[l]=a[j];
	a[j]=pivot;

	quickSort(a,l,j-1);
	quickSort(a,j+1,r);
}

//快速排序（堆棧方法）
void swap(int *a,int *b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

struct Param
{
	int *a;
	int n;
};

void sort(int *a,int n)
{
	stack sp;
	Param pm;
	for( ; ; )
	{
		if (n <= 2)//不超過兩個數據就處理完畢
		{
			if(n == 2 && a[1] < a[0])
				swap(a,a+1);
			if (sp.empty()) 
				break;//如果棧中沒有待排序數據就退出
			pm = sp.top();//如果棧中有待排序數據就取出最後入棧的一段
			sp.pop();
			a = pm.a;
			n = pm.n;
			continue;
		}
		swap(a,a+(n>>1));//把中間的那個數據交換到最前面
		int pivot = *a;//以現在最前面的數據作為分界值
		int *l = a+1;//左邊第二個數據
		int *r = a+n-1;//右邊最後一個數據
		while (l < r)
		{
			//小於分界值的留在左邊，遇到不小於的停止
			while(l < r && *l < pivot)
				l++;
			//不小於分界值的留在右邊，遇到小於的停止
			while(r > a && *r >= pivot)
				r--;
			//交換這兩個數據
			if(l < r)
				swap(l,r);
		}
		//把分界值交換回中間位置
		if(*a > *r)
			swap(a,r);
		//對左右兩組分別非遞歸排序
		pm.a = r+1;
		pm.n = n-(r-a+1);
		sp.push(pm);
		n = r-a;
	}
}

//一種分而治之排序算法
template
MergeSort(T a[],int left,int right)
{
	if(left
void MergeSort(T a[],int n)
{
	//使用歸並排序算法對a[0:n-1]進行排序
	T*b=new T[n];
	int s=1;//段的大小
	while (s
void MergePass(T a[],T b[],int s,int n)
{
	int i=0;
	while (i<=n-2*s)
	{
		Merge(a,b,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
	if(i+s
void Merge(T a[],T b[],int l,int m,int r)
{
	int i=l,//第一段的游標
		j=m+1,//第二段的游標
		k=l;//結果的游標
	//只要在段中存在i和j，則不斷進行合並
	while (i<=m&&j<=r)
	{
		if(a[i]<=a[j])
			b[k++]=a[i++];
		else
			b[k++]=a[j++];
	}
	//考慮余下的部分
	if(i>m)
		for(int q=j;q<=r;q++)
			b[k++]=a[q];
	else
		for(int q=i;q<=m;q++)
			b[k++]=a[q];
			
}