dichotomysort.h

来自「各种排序算法BubbleSort、DichotomySort、HeapSort、」· C头文件 代码 · 共 53 行

#ifndef DICHOTOMYSORT_H
#define DICHOTOMYSORT_H
#include<iostream.h>

template<class Elem>
class DichotomySort:public sort<Elem>
{
	public:
		DichotomySort(){compareNum = 0 ; moveNum = 0 ;};
		virtual void Sorts(Elem Array[], int n);////
		void print_d(Elem Array[], int n);
	private:
		int compareNum;/////比较次数
		int moveNum;/////移动次数
};
template<class Elem>
void DichotomySort<Elem>::Sorts(Elem Array[], int n)
{
	Elem temp;
	int left,right,middle;
	for(int i = 1 ; i < n ; i++)///int i = 0 ; i < n ; i++
	{
		temp = Array[i];
		left = 0;
		right = i - 1;
		while(left <= right)
		{
			middle = (left + right) / 2;
			if( compare(temp,Array[middle]) == -1 )
				right = middle - 1;
			else
				left = middle + 1;
			compareNum++;
		}
		for(int j = i - 1 ; j >= left ; j--)///for(int j = i - 1 ; j >= left ; j--)
		{
			Array[j+1] = Array[j];
			moveNum++;
		}
		Array[left] = temp;
		moveNum++;
	}
}
template<class Elem>
void DichotomySort<Elem>::print_d(Elem Array[], int n)
{
	cout<<"        二分法插入排序法         "<<endl;
	cout<<"+++++++++++++++++++++++++++++++++"<<endl;
	cout<<"比较次数："<<compareNum<<endl;
	cout<<"移动次数："<<moveNum<<endl;
	//print(Array , n);
}
#endif