sortclass.cpp

各种排序算法设计。 包括简单的：冒泡

#include "stdafx.h"
#include "SortClass.h"
#include <cmath>
#include <cstdlib>

using namespace std;
#define MaxLen 1000000
int m[MaxLen];
int g_nOriginal[MaxLen+10],g_nFinished[MaxLen+10];
int g_nTemp1[MaxLen+10],g_nTemp2[MaxLen+10];
Allsort::Allsort(int num[],int n)
{
	m_nTotalSwap=0;
	m_nTotalCmp=0;
	m_nLen=n;

	for(;n>=0;n--)
	{
		g_nOriginal[n+1]=num[n];
		g_nFinished[n+1]=num[n];
	}
}

Allsort::~Allsort()
{
	//delete[] g_nOriginal;
}
void Allsort::Reset()
{
	m_nTotalSwap=0;
	m_nTotalCmp=0;
	for(int i=0;i<m_nLen;i++)
		g_nFinished[i]=g_nOriginal[i];
}


void Allsort::InsertSort(int r[], int n)
{

	for (int i=2; i<n; i++,m_nTotalCmp++)
	{ 
		r[0]=r[i];                        
		for (int j=i-1; r[0]<r[j]; j--,m_nTotalCmp++)   
		{r[j+1]=r[j];
		m_nTotalSwap++;}
		r[j+1]=r[0];                 
	}

}
void Allsort::BinaryInsert(int r[], int n)//n is the location of the array
{

	int left = 1,right = n-1;
	int temp = g_nOriginal[n];
	while(left <=right)
	{
		m_nTotalCmp++;
		int mid = (left + right)/2;
		if(temp > r[mid])left=mid+1;
		else right=mid-1;
		m_nTotalSwap++;
	}
	for(int j =n-1;j >= left;j--,m_nTotalCmp++)
	{
		m_nTotalSwap++;
		r[j +1] = r[j];
	}
	r[left] = temp;

}
void Allsort::BinaryInsertSort(int r[], int n)
{
	for(int i = 1;i <=n;i++)
		BinaryInsert(r,i);
}

void Allsort::ShellSort(int r[], int n)
{	
	int i;
	int d;
	int j;
	for (d=n/2; d>=1; d=d/2,m_nTotalCmp++)            //以增量为d进行直接插入排序
	{
		for (i=d+1; i<n; i++,m_nTotalCmp++)   
		{   
			r[0]=r[i];                 //暂存被插入记录
			for (j=i-d; j>0 && r[0]<r[j]; j=j-d,m_nTotalCmp++)
			{
				m_nTotalSwap++;
				r[j+d]=r[j]; 
			}//记录后移d个位置
			r[j+d]=r[0];
		}
	}

}

void Allsort::BubbleSort(int r[], int n)
{
	int temp;
	int exchange;
	int bound;
	exchange=n-1;                       //第一趟起泡排序的范围是r[0]到r[n-1]	
	while (exchange)                    //仅当上一趟排序有记录交换才进行本趟排序
	{
		m_nTotalCmp++;
		bound=exchange; 
		exchange=0;  
		for (int j=0; j<bound; j++,m_nTotalCmp++)     //一趟起泡排序
			if (r[j]>r[j+1]&&m_nTotalCmp++) 
			{
				m_nTotalSwap++;
				temp=r[j];
				r[j]=r[j+1];
				r[j+1]=temp;
				exchange=j;                   //记录每一次发生记录交换的位置
			}
	}

}

int Allsort::Partition(int r[], int first, int end)
{	
	int i=first;                        //初始化
	int j=end;
	int temp;        

	while (i<j)	
	{  
		m_nTotalCmp++;
		while (i<j && r[i]<= r[j])
		{
			m_nTotalCmp++;
			j--;    
		}//右侧扫描
		if (i<j)
		{ 
			m_nTotalCmp++;
			temp=r[i];                 //将较小记录交换到前面
			r[i]=r[j];
			r[j]=temp;
			i++; 
			m_nTotalSwap++;
		}
		while (i<j && r[i]<= r[j]) 
		{
			m_nTotalCmp++;
			i++;  
		}//左侧扫描
		if (i<j)
		{
			m_nTotalCmp++;
			temp=r[j];
			r[j]=r[i];
			r[i]=temp;                //将较大记录交换到后面
			j--; 
			m_nTotalSwap++;
		}
	}
	return i;                           //i为轴值记录的最终位置
}

//快速排序
void Allsort::QuickSort(int r[], int first, int end)
{
	if (first<end) 
	{                                   
		int pivot=Partition(r, first, end);  
		QuickSort(r, first, pivot-1);
		QuickSort(r, pivot+1, end);  
	}

}

//简单选择排序
void Allsort::SelectSort(int r[ ], int n)
{ 
	int i;
	int j;
	int index;
	int temp;
	for (i=0; i<n-1; i++,m_nTotalCmp++)  	            //对n个记录进行n-1趟简单选择排序
	{  
		index=i; 		
		for (j=i+1; j<n; j++,m_nTotalCmp++)            //在无序区中选取最小记录
			if (r[j]<r[index]&&m_nTotalCmp++)
				index=j;
		if (index!=i&&m_nTotalCmp++) 
		{
			m_nTotalSwap++;
			temp=r[i];
			r[i]=r[index];
			r[index]=temp;
		}
	}

}


//筛选法调整堆
void Allsort::Sift(int r[], int k, int m)
{

	int i;
	int j;
	int temp;
	i=k; 
	j=2*i+1;                            //置i为要筛的结点，j为i的左孩子
	while (j<=m&&m_nTotalCmp++)                          //筛选还没有进行到叶子
	{
		m_nTotalCmp++;
		if (j<m && r[j]<r[j+1]&&m_nTotalCmp++&&m_nTotalCmp++) 
			j++;                          //比较i的左右孩子，j为较大者
		if (r[i]>r[j]&&m_nTotalCmp++&&m_nTotalCmp++) break;             //根结点已经大于左右孩子中的较大者
		else 
		{
			m_nTotalSwap++;
			temp=r[i];
			r[i]=r[j];
			r[j]=temp;                   
			i=j;
			j=2*i+1;                     //被筛结点位于原来结点j的位置
		}
	}
}
//堆排序
void Allsort::HeapSort(int r[ ], int n)
{

	int i;
	int temp;
	for (i=n/2; i>=0; i--)                //初始建堆，从最后一个非终端结点至根结点
		Sift(r, i, n) ;     
	for (i=n-1; i>0; i--)                //重复执行移走堆顶及重建堆的操作
	{
		m_nTotalSwap++;
		temp=r[i];
		r[i]=r[0];
		r[0]=temp;
		Sift(r, 0, i-1);
	}

}


//一次归并
void Allsort::Merge(int r[], int r1[], int s, int m, int t)
{

	int i=s;
	int j=m+1;
	int k=s;

	while (i<=m && j<=t&&m_nTotalCmp++)
	{   
		if (r[i]<=r[j]&&m_nTotalCmp++) 
		{
			m_nTotalSwap++;
			r1[k++]=r[i++];  
		}//取r[i]和r[j]中较小者放入r1[k]
		else 
		{
			m_nTotalSwap++;
			r1[k++]=r[j++]; 
		}
	}
	if (i<=m&&m_nTotalCmp++) 
		while (i<=m&&m_nTotalCmp++)                     
		{
			m_nTotalSwap++;
			r1[k++]=r[i++]; 
		}
	else  
		while (j<=t&&m_nTotalCmp++)                  //收尾处理        
		{
			m_nTotalSwap++;
			r1[k++]=r[j++]; 
		}
}


//一趟归并
void Allsort::MergePass(int r[ ], int r1[ ], int n, int h)
{
	int i=0;
	int k;

	while (i<=n-2*h&&m_nTotalCmp++)                     //待归并记录至少有两个长度为h的子序列
	{
		Merge(r, r1, i, i+h-1, i+2*h-1);
		i+=2*h;
	}
	if (i<n-h&&m_nTotalCmp++) 
		Merge(r, r1, i, i+h-1, n);       //待归并序列中有一个长度小于h
	else for (k=i; k<=n; k++&&m_nTotalCmp++)            //待归并序列中只剩一个子序列
		r1[k]=r[k];
}

//归并排序的非递归算法
void Allsort::MergeSort1(int r[ ], int r1[ ], int n )
{ 
	int h=1;
	while (h<n)
	{
		MergePass(r, r1, n-1, h);           //归并
		h=2*h;
		MergePass(r1, r, n-1, h);
		h=2*h;
	}

}

//归并排序的递归算法
void Allsort::MergeSort2(int r[], int r1[], int r2[],int s, int t)
{ 

	int m;
	if (s==t) 
	{
		r1[s]=r[s];

	}
	else 
	{ 
		m=(s+t)/2;
		MergeSort2(r, r2, r1, s, m);        //归并排序前半个子序列		
		MergeSort2(r, r2, r1, m+1, t);      //归并排序后半个子序列
		Merge(r2, r1, s, m, t);             //将两个已排序的子序列归并 		
	}	 
}

void Allsort::Distribute1(int r[],int temp[10][MaxLen+10], int n,int wide2)
{
	for(int i=1;i<n;i++)
	{
		int intended=r[i]%int((pow(10,wide2)));
		intended=intended/int(pow(10,wide2-1));

		temp[intended][temp[intended][0]+1]=r[i];
		temp[intended][0]++;
		m_nTotalSwap++;
	}


}

void Allsort::Collect1(int r[],int temp[10][MaxLen+10], int n)
{
	int rebuild=0;
	for(int i=0;i<10;i++&&m_nTotalCmp++)
	{
		for(int j=temp[i][0];j>0;j--&&m_nTotalCmp++)
		{
			m_nTotalSwap++;
			r[++rebuild]=temp[i][temp[i][0]-j+1];
		}
	}

}

void Allsort::RadixSort(int r[], int n,int wide1)
{
	int temp[10][MaxLen+10];

	for(int j=1;j<=wide1;j++&&m_nTotalCmp++)
	{
		for(int i=0;i<10;i++)
			temp[i][0]=0;
		Distribute1(r,temp,n,j);//将数组分配到temp[10][MaxLen+10]
		Collect1(r,temp,n);//重新收集，排成新数组
	}


}


void Allsort::PrintData()
{
	for(int i=1;i<m_nLen;i++)
		cout<<g_nFinished[i]<<"  ";
	cout<<endl;
	cout<<"total of comparison is:  "<<m_nTotalCmp<<"   total of exchange:  "<<m_nTotalSwap<<endl;
	cout<<endl;
}