sortarithmetis.cpp

学习数据结构写的排序代码

// SortArithmetis.cpp: implementation of the CSortArithmetis class.
//
//////////////////////////////////////////////////////////////////////

#include "SortArithmetis.h"
#include "iostream.h"
#include "iomanip.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CSortArithmetis::CSortArithmetis(int *val,int n)
{
	m_nCount=n;
    m_nArray=val;
	m_nNumber=0;
}


CSortArithmetis::~CSortArithmetis()
{

}


void CSortArithmetis::ShowArray()//显示排列好的数组
{
  	cout<<"*********************the sorting results******************* "<<endl;  
	cout<<"Elements number: "<<m_nCount<<endl;
	cout<<"Runing times: "<<m_nNumber<<endl;
	for(int i=0;i<m_nCount;i++)
		cout<<setw(5)<<m_nArray[i]; 
	cout<<endl;    
}


void CSortArithmetis::DirectInsert()//直接插入排序
{
	cout<<"直接插入排序:"<<endl;
	int i,j;
	int value;

	m_nNumber=0;
	for(i=1;i<m_nCount;i++)
	{
		value=m_nArray[i];//保留结点值
	    for(j=i-1;j>=0&&value<m_nArray[j];j--)//移动位置
		{
			m_nArray[j+1]=m_nArray[j];
			m_nNumber++;
		}
		m_nArray[j+1]=value;
/*		for(j=0;j<i&&value>m_nArray[j];j++)//寻找插入位置
		{
		}
		k=j;//保留插入位置
	    for(j=i;j>k;j--)//移动位置
			m_nArray[j]=m_nArray[j-1];
		m_nArray[k]=value;
*/
	}
}

void CSortArithmetis::Bubble()//冒泡排序
{
	cout<<"冒泡排序:"<<endl;
    int i,k;
	int value;

	m_nNumber=0;
	for(k=m_nCount;k>0;k--)//一趟排序将使一个结点处在合适的位置
		for(i=0;i<k-1;i++)
		{
			if(m_nArray[i]>m_nArray[i+1])//进行交换
			{
				value=m_nArray[i];
				m_nArray[i]=m_nArray[i+1];
				m_nArray[i+1]=value;
			}
			m_nNumber++;
		}
}
	

void CSortArithmetis::SimpleChoose()//简单选择排序
{
	cout<<"简单选择排序:"<<endl;
	int i,j,k;
	int min,value;

	m_nNumber=0;
	for(i=0;i<m_nCount-1;i++)
	{
		min=m_nArray[i];
		for(j=i+1;j<m_nCount;j++)//寻找最小者
		{
			if(min>m_nArray[j])
			{
				min=m_nArray[j];
				k=j;
			}
			m_nNumber++;
		}
		if(min<m_nArray[i])//交换位置
		{
			value=m_nArray[k];
			m_nArray[k]=m_nArray[i];
			m_nArray[i]=value; 
		}
//		ShowArray();
	}
}

void CSortArithmetis::ShellSort()//希尔排序
{
	int dec,i,j,k,value;//dec是每一趟的增量

	m_nNumber=0;
    for(dec=m_nCount/2;dec>0;dec/=2)//需要N趟排序
	{
		for(i=0;i<dec;i++)//获取间隔元素组成新数组
		{
			//对新数组直接插入排序
			for(j=i;j<m_nCount;j+=dec)//依次得到新数组元素
			{
				value=m_nArray[j];//保留结点值
	            for(k=j-dec;k>=i&&value<m_nArray[k];k-=dec)//移动位置
				{
					m_nArray[k+dec]=m_nArray[k];
					m_nNumber++;
				}
		        m_nArray[k+dec]=value;
			}

		}
	}
}


void CSortArithmetis::QuickSort()//快速排序
{
	int low,high;

	m_nNumber=0;
	low=0;
	high=m_nCount-1;
	Quick(low,high,m_nNumber);
}

void CSortArithmetis::Quick(int low,int high,int count)//快速排序的子函数
{
	int i,j,keyValue;

    if(low<high)
	{
		keyValue=m_nArray[low];
		i=low;
		j=high;
		while(i<j)
		{
			while(i<j&&m_nArray[j]>=keyValue)
			{
				j--;
				m_nNumber++;
			}
			if(i<j)
				m_nArray[i++]=m_nArray[j];
			while(i<j&&m_nArray[i]<=keyValue)
			{
				i++;
				m_nNumber++;
			}
			if(i<j)
				m_nArray[j--]=m_nArray[i];
            
		}
		m_nArray[i]=keyValue;//和数组最后一位交换
		Quick(low,i-1,count++);
		Quick(i+1,high,count++);
	}
}


void CSortArithmetis::HeapSort()
{
	for(int i=m_nCount;i>1;i--)
		Heap(1,i);
}

void CSortArithmetis::Heap(int start,int end)
{
	int i,j,l,r,n,val;

	n=end-start+1;
	for(i=(n-1)/2;i>=start;i--)
	{
//		for(j=i;j<=(n-1)/2;j=2*j)
		{
			l=2*i;//左子结点   
		    r=2*i+1;//右子结点
		    if(m_nArray[l-1]>m_nArray[i-1])//与左子结点进行比较
			{
			val=m_nArray[i-1];
			m_nArray[i-1]=m_nArray[l-1];
			m_nArray[l-1]=val;
			}
 	    	if(r<n&&m_nArray[r-1]>m_nArray[i-1])//与右子结点进行比较
			{
			val=m_nArray[i-1];
			m_nArray[i-1]=m_nArray[r-1];
			m_nArray[r-1]=val;
			}
	    	m_nNumber++;
//			ShowArray();
		}
	}
	if(m_nArray[0]>m_nArray[end-1])//将最大结点放在末尾
	{
		val=m_nArray[end-1];
		m_nArray[end-1]=m_nArray[0];
		m_nArray[0]=val;
	} 
}