【学习笔记】算法导论第2章：算法基础

//======================================
//Ch2_1_Basic_Sort_Algorthm
//======================================
#include<iostream>
#include<vector>
#include<limits.h>	//using INT_MAX
using namespace std;
//---------------------------------------

class Sequence{
	vector<int> s;

public:
	void set(int* str,int n){
		if(n<=0){
			cerr<<"Input Parameter Error!"<<endl;
			exit(1);
		}
		s.insert(s.end(),str,str+n);
	}//-----------------------------------

	void print(){
		for(int i=0;i<s.size();i++)		cout<<s[i]<<" ";
		cout<<endl;
	}//-----------------------------------

	void print(vector<int> A){
		for(int i=0;i<A.size();i++)		cout<<A[i]<<" ";
		cout<<endl;
	}//-----------------------------------

	void insertionSort();
	void selectionSort();
	void bubbleSort();
	void merge(int p,int q,int r);
	void mergeSort(int p,int r);
	int binarySearch(int p,int r,int target);
	bool isAscend();
};//--------------------------------------

void Sequence::insertionSort(){
	if(s.size()>=2){
		for(int j=1;j<s.size();j++){
//			cout<<s[j]<<endl;
			int key = s[j];
			int i   = j-1;
//			while(key>s[i] && i>=0){	//	descend
			while(key<s[i] && i>=0){	//	ascend
				s[i+1] = s[i];
				i--;
			}
			s[i+1] = key;
//			print();
		}
	}
}//-----------------------------------

void Sequence::selectionSort(){
	for(int i=0;i<s.size()-1;i++){
//		cout<<i+1<<endl;
		int key  	 =  s[i];
		int min		 =  s[s.size()-1];;
		int minIndex =  s.size()-1;
		for(int j=i;j<s.size();j++){
			if(s[j]<min){
				min		 =	s[j];
				minIndex =  j;
			}
		}
		s[i]		=	min;
		s[minIndex] =   key;
//		print();
	}
}//------------------------------------

void Sequence::bubbleSort(){
	for(int i=0;i<s.size()-1;i++){
		for(int j=s.size()-1;j>i;j--){
			if(s[j]<s[j-1]){
				int temp   = s[j];
					s[j]   = s[j-1];
					s[j-1] = temp;
			}
		}
	}
}//------------------------------------

void Sequence::merge(int p,int q,int r){
	int n1 = q - p + 1;
	int n2 = r - q;
	vector<int> L,R;
	L.assign(s.begin()+p,s.begin()+p+n1);
	R.assign(s.begin()+q+1,s.begin()+q+1+n2);
//	print(L);	print(R);
	L.push_back(INT_MAX);
	R.push_back(INT_MAX);
	int i=0,j=0;
	for(int k=p;k<=r;k++){
		if(L[i]<=R[j])			s[k]=L[i++];
		else					s[k]=R[j++];
	}
}//-----------------------------------

void Sequence::mergeSort(int p,int r){
	if(p<r){
		int q=(p+r)/2;
		mergeSort(p,q);
		mergeSort(q+1,r);
		merge(p,q,r);
	}
}//-----------------------------------

bool Sequence::isAscend(){
	if(1==s.size())				return true;
	else{
		for(int i=1;i<s.size();i++){
			if(s[i]<s[i-1])		return false;
		}
		return	true;
	}
}//-----------------------------------

int Sequence::binarySearch(int p,int r,int target){
	if(!isAscend()){
			cerr<<"Input Sequence is not ascend!"<<endl;
			exit(1);
		}
	if(p>r)			return -1;
	else{
		int q=(p+r)/2;
		if(s[q]==target)		return q;
		else if(s[q]<target)	return binarySearch(q+1,r,target);
		else					return binarySearch(p,q,target);
	}
}//-----------------------------------

int main(){
	Sequence Obj;
	int str[]={5,2,4,7,1,3,2,6};
//	int str[]={1};	//Test example
	Obj.set(str,sizeof(str)/sizeof(str[0]));
//	Obj.insertionSort();
//	Obj.selectionSort();
//	Obj.bubbleSort();
//	Obj.merge(0,(sizeof(str)/sizeof(str[0])-1)/2,sizeof(str)/sizeof(str[0])-1);
	Obj.mergeSort(0,sizeof(str)/sizeof(str[0])-1);
	Obj.print();
//	cout<<Obj.isAscend()<<endl;
	cout<<Obj.binarySearch(0,sizeof(str)/sizeof(str[0])-1,3)<<endl;
	return 0;
}//=======================================