2222.cpp

对一组数据运用6种常见的排序方法排序

// 2222.cpp : Defines the entry point for the console application.
//


/******************************头文件********************************/
#include "stdafx.h"
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>

/**************************************RandomNumber类的定义**************************************/
const unsigned long maxshort = 32767;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
const unsigned long n = 500;

class RandomNumber
{
private:
  unsigned long randSeed;

public:
  RandomNumber(unsigned long s=0);
  unsigned short Random(unsigned long n);
  double Random(void);
};

/**************************************RandomNumber类的实现**************************************/
RandomNumber::RandomNumber(unsigned long s)
{
  if(s==0)
  {
    randSeed = time(0);
  }
  else
  {
    randSeed = s;
  }
}

unsigned short RandomNumber::Random(unsigned long n)
{
  randSeed=multiplier*randSeed+adder;
  srand(randSeed);
 return rand()%n;
}
//end of define RandomNumber


/*************************************ArraySort类的定义******************************************/
class ArraySort
{
public:
	int * L;
	int n;
	ArraySort() {n=0;}
	ArraySort(int a[],int len)
	{
		if (len<=0){
			cerr<<"value of n is invalid!"<<endl;
			exit(1);
		}
		n=len;
		if ((L = new int[n])==NULL){
			cout<<"Can't allocate more memory,terminating."<<endl;
			exit(1);
		}
		for (int i=0;i<n;i++)
			L[i]=a[i];
	}
	double  duration;

    //1、插入排序
	void MyInsertSort ();

	//2、折半插入排序
	void BiInsertSort();
	
	//3、希尔排序
	void ShellInsert (int dk);
	void ShellSort ();
    
	//4、冒泡排序
	void BubbleSort();

	//5、快速排序
	void Swap(int& x,int& y);//交换数组元素
    int Partion (int p,int r);
    void MyQuickSort (int p,int r);

	//6、采用随机选择策略的快速排序
	int RandomizedQuickPass(int p,int r);
    void RandomQuickSort(int p,int r);

	//7、选择排序
    void SelectSort();

	//8、堆排序
    void HeapSort();
    void buildHeap();
    void insert_special( int x, int start, int end );

	//输出
	void Output();
	~ArraySort() {
		delete []L;
	}
};


/********************************ArraySort类的实现******************************************/

/*******************************插入排序********************************/
void ArraySort::MyInsertSort()
{
	int i,j,x;
	for (i=1;i<n;i++){
		x=L[i];
		for (j=i-1;j>=0;j--)
			if (x<L[j]) L[j+1]=L[j];
			else break;
		L[j+1]=x;
	}
}


/*******************************二分插入排序**************************/
void ArraySort::BiInsertSort() 
{
	for (int i=1; i<n; i++ ) {
		int sentinel;
		sentinel = L[i];      // 将 L[i] 暂存到 L[0]
		int low = 0; int high = i-1;
        while (low<=high) {
	    int m = (low+high)/2;     // 折半
    	if (sentinel < L[m])
		high = m-1;   // 插入点在低半区
    	else  low = m+1; // 插入点在高半区
		}		//在 L[1..i-1]中折半查找插入位置；
		for (int j=i-1; j>=high+1; j--)
			L[j+1] = L[j];      // 记录后移
		L[high+1] = sentinel;  // 插入
	} // for
} // BInsertSort


/******************************希尔排序*****************************/
void ArraySort::ShellInsert (int dk)
 {
 	int sentinel;
	for (int i=dk; i<n; i++ )
      if ( L[i]< L[i-dk]) {
        sentinel = L[i];            // 暂存
        for (int j=i-dk; (j>=0)&&(sentinel<L[j]); j-=dk)
           L[j+dk] = L[j];  // 记录后移，查找插入位置
        L[j+dk] = sentinel;     // 插入
      } // if
} // ShellInsert


void ArraySort::ShellSort ()
{    // 增量为dlta[]的希尔排序
    int m = (int)floor(log10(2*n+1)/log10(3));
	int * dlta = new int[m];
	dlta[0] = 1; 
	for (int i=1;i<m;i++)
		dlta[i]=3*dlta[i-1]+1;

	for (int k=m-1; k>=0; k--)
         ShellInsert(dlta[k]);
             //一趟增量为dlta[k]的插入排序

	delete []dlta;
} // ShellSort

/****************************快速排序*****************************/
void ArraySort::Swap(int& x,int& y)
{
	int temp;
	temp=x;
	x=y;
	y=temp;
}

int ArraySort::Partion (int p,int r)
{
	int i = p,
		j = r+1;
	int x = L[p];
	while (true){
		while (L[++i] < x);
		while (L[--j] > x);
		if (i >= j) break;
		Swap (L[i],L[j]);
	}
	L[p]=L[j];
	L[j]=x;
	return j;
}

void ArraySort::MyQuickSort (int p,int r)
{// 排序L [ p : r ]， L[r+1] 有大值  
if (p>= r) return;  
int i = p, // 从左至右的游标  
j = r + 1; // 从右到左的游标  
int pivot = L[p];  
// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换  
while (true) {  
do {// 在左侧寻找>= pivot 的元素  
i = i + 1;  
} while (L[i] < pivot);  
do {// 在右侧寻找<= pivot 的元素  
j = j - 1;  
} while (L[j] > pivot);  
if (i >= j) break; // 未发现交换对象  
Swap(L[i], L[j]);  
}  
// 设置p i v o t  
L[p] = L[j];  
L[j] = pivot;  
MyQuickSort( p, j-1); // 对左段排序  
MyQuickSort(j+1, r); // 对右段排序  
}  

/**********************************冒泡排序*****************************/
void ArraySort::BubbleSort()
{
	int i = n-1;
	while (i >0) {
		int lastExchangeIndex = 0;
		for (int j = 0;  j < i;  j++)
			if (L[j] > L[j+1]) { 
				Swap(L[j], L[j+1]);
				lastExchangeIndex = j;//记下进行交换的记录位置
			} //if
		i = lastExchangeIndex; // 本趟进行过交换的最后一个记录的位置
	}
} // BubbleSort

/************************采用随机选择策略的快速排序************************/
int ArraySort::RandomizedQuickPass(int p,int r)
{
	RandomNumber rnd;
	int i=rnd.Random(r-p+1)+p;//(调用随机类即可)
    Swap(L[i],L[p]);
    return Partion(p,r);
}

void ArraySort::RandomQuickSort(int p,int r)
{
	if(p<r){
		int i=RandomizedQuickPass(p,r);
   		RandomQuickSort(p,i-1);//对左半部分作递归处理
        RandomQuickSort(i+1,r);//对右半部分作递归处理
	}
 }


/*********************************简单选择排序******************************/
void ArraySort::SelectSort()
{
	int i,j,k;
	for (i=1;i<n;i++){
		k=i-1;
		for (j=i;j<n;j++){
			if (L[j]<L[k]) k=j;
		}
        if(k!=i-1) Swap(L[i-1],L[k]);
	}
}


/************************************堆排序************************************/
void ArraySort::HeapSort()
// sort an array of the given n
{
   int i;
   int temp;
   buildHeap();
   for (i = n-1; i >=1; i--) {
      temp = L[i];    // extract the last element from the array
      L[i] = L[0];    // move top of heap to the end of the array
      insert_special( temp,0, i-1 );      // restore heap properties
   }
}


void ArraySort::buildHeap()
// Build a heap from an array of items
// Binary tree with one node satisfies heap properties
// Therefore ignore leaves and start from the parent
// of the last item
{
   int i;
   for (i = (n - 2)/2; i >= 0; i--)     // start from parent of last item
      insert_special( L[i],i, n-1);
}


void ArraySort::insert_special( int x, int start, int end)
// insert x into the sub-heap from start to end
// location start is empty
{
   int child = 2*start + 1;        // left child of start
        
   while (child <= end) {
      if (child < end && L[child] < L[child + 1])
         child++;         // child is the larger child of start
      if (x > L[child])
         break;           // x stays in start
      else {
         L[start] = L[child];
         start = child;
         child = 2*start + 1;
      }
   }       
   L[start] = x;
}

/******************************输出********************************/
void ArraySort::Output()
{
	cout<<"duration time is"<<duration<<endl;
}

/******************************主函数********************************/
void main()
{
   int * L=new int[10000000];
	int n,i;
        cout<<"输入待排序的数据个数："<<endl;
	cin >> n ;
	RandomNumber rnd;
	for (i=0;i<n;i++)
		L[i]=rnd.Random(n);
	ArraySort p1(L,n);ArraySort p2(L,n);ArraySort p3(L,n);ArraySort p4(L,n);
	ArraySort p5(L,n);ArraySort p6(L,n);ArraySort p7(L,n);ArraySort p8(L,n);

	cout<<"When the length of Array is "<<n<<':'<<endl;
	clock_t start, finish;
	double duration;

   start = clock(); 
	p1.MyInsertSort();//插入排序
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout<<"By MyInsertSort,duration time is "<<duration<<"s."<<endl;

    start = clock(); 
	p2.BiInsertSort();//折半插入排序
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout<<"By BiInsertSort,duration time is "<<duration<<"s."<<endl;

    start = clock(); 
	p3.ShellSort();//希尔排序
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout<<"By ShellSort,duration time is "<<duration<<"s."<<endl;

   start = clock(); 
    p4.BubbleSort();//冒泡排序
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout<<"By BubbleSort,duration time is "<<duration<<"s."<<endl;

    start = clock(); 
    p5.MyQuickSort(0,n-1);//快速排序
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout<<"By MyQuickSort,duration time is "<<duration<<"s."<<endl;

    start = clock(); 
    p6.RandomQuickSort(0,n-1);//随机快速排序
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout<<"By RandomQuickSort,duration time is "<<duration<<"s."<<endl;

    start = clock(); 
    p7.SelectSort();//随机选择排序
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout<<"By SelectSort,duration time is "<<duration<<"s."<<endl;

    start = clock(); 
    p8.HeapSort();//堆排序
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout<<"By HeapSort,duration time is "<<duration<<"s."<<endl;

	delete []L;
}