#include<iostream>
#include<cstdlib>
using namespace std;
const int maxsize=105;
struct sqlist{
	int size;
	int sq[maxsize];
};

void swap(sqlist *L,int i,int j){
	int temp = L->sq[i];
	L->sq[i] = L->sq[j];
	L->sq[j] = temp;
}

void bubble_sort(sqlist *L){
	cout<<"··冒泡排序··"<<endl;
	int l=0,k=0; 
	for(int i=1;i<L->size;i  )
		for(int j=1;j<=L->size-i;j  ){
			l  ;
			if(L->sq[j]>L->sq[j 1]){
				swap(L,j,j 1);
				k =3;
			}			
		}
	cout<<"冒泡排序關(guān)鍵字的比較次數(shù)為："<<l<<endl;
	cout<<"冒泡排序關(guān)鍵字的移動(dòng)次數(shù)為："<<k<<endl; 
}

void insertion_sort(sqlist *L){
	cout<<"··直接插入排序··"<<endl;
	int l=0,k=0;
	for(int i=2;i<=L->size;i  ){
		l  ;
		int temp=L->sq[i];
		int j=i-1; 
		while(temp<L->sq[j]&&j>0){
			l  ;
			L->sq[j 1]=L->sq[j];
			k  ;
			j--;
		}
		l  ;
		L->sq[j 1]=temp;
		k  ;
	}
	cout<<"直接插入排序關(guān)鍵字的比較次數(shù)為："<<l<<endl;
	cout<<"直接插入排序關(guān)鍵字的移動(dòng)次數(shù)為："<<k<<endl;
}

void selection_sort(sqlist *L){
	cout<<"··直接選擇排序··"<<endl;
	int l=0,k=0;
	for(int i=1;i<L->size;i  ){
		int t;
		t=i;
		for(int j=i 1;j<=L->size;j  ){
			l  ;
			if(L->sq[t]>L->sq[j])
				t=j;
		}
		if(t!=i){
			swap(L,t,i);
			k =3;
		}	
	}
	cout<<"直接選擇排序關(guān)鍵字的比較次數(shù)為："<<l<<endl;
	cout<<"直接選擇排序關(guān)鍵字的移動(dòng)次數(shù)為："<<k<<endl;
}

int Partition(sqlist *L,int low,int high,int &l,int &k){
    int pivotkey;
    pivotkey = L->sq[low];
    while(low<high)
    {
        while(L->sq[high] >= pivotkey && low<high ){
            l  ;
            high--;
        }
        l  ;
        swap(L,low,high);
        k =3;
        while(L->sq[low] <= pivotkey && low<high ){
            l  ;
            low  ;
        }
        l  ;
        swap(L,low,high);
        k =3;
    }
    return low;
}

void QSort(sqlist *L,int low,int high,int &l,int &k){
    int pivot;
    if(low<high){
        pivot = Partition(L,low,high,l,k);
        QSort(L,low,pivot-1,l,k);
        QSort(L,pivot 1,high,l,k);
    }
}

void quick_sort(sqlist *L){
	cout<<"··快速排序··"<<endl;
	int l=0,k=0;
	QSort(L,1,L->size,l,k);
	cout<<"快速排序關(guān)鍵字的比較次數(shù)為："<<l<<endl;
	cout<<"快速排序關(guān)鍵字的移動(dòng)次數(shù)為："<<k<<endl;
}

void shell_sort(sqlist *L){
	cout<<"··希爾排序··"<<endl;
	int l=0,k=0;
	int d;
	d=L->size/2;
	while(d>0){
		for(int i=d 1;i<=L->size;i  ){
			l  ;
			int temp=L->sq[i];
			int j=i-d; 
			while(temp<L->sq[j]&&j>0){
				l  ;
				L->sq[j d]=L->sq[j];
				k  ;
				j-=d;
		}
		l  ;
		L->sq[j d]=temp;
		k  ;
		}
		d/=2;
	} 
	cout<<"希爾排序關(guān)鍵字的比較次數(shù)為："<<l<<endl;
	cout<<"希爾排序關(guān)鍵字的移動(dòng)次數(shù)為："<<k<<endl;
}

void sift(sqlist *L,int low,int high,int &l,int &k){
	int i=low,j=2*i;
	int temp=L->sq[i];
	while(j<=high){
		l  ;
		if(j<high&&L->sq[j]<L->sq[j 1])
			j  ;
		l  ;	
		if(temp<L->sq[j]){
			L->sq[i]=L->sq[j];
			k  ;
			i=j;
			j=2*i;
		}
		else break;
	}
	L->sq[i]=temp;
	k  ;
}

void heap_sort(sqlist *L){
	cout<<"··堆排序··"<<endl;
	int l=0,k=0;
	for(int i=L->size/2;i>0;i--)
		sift(L,i,L->size,l,k);
	for(int i=L->size;i>=2;i--){
		swap(L,1,i);
		k =3;
		sift(L,1,i-1,l,k);
	}
	cout<<"堆排序關(guān)鍵字的比較次數(shù)為："<<l<<endl;
	cout<<"堆排序關(guān)鍵字的移動(dòng)次數(shù)為："<<k<<endl;
}

int main(){
	//關(guān)鍵字：一個(gè)數(shù)據(jù)元素可由多個(gè)數(shù)據(jù)項(xiàng)組成，
	//以數(shù)據(jù)元素某個(gè)數(shù)據(jù)項(xiàng)作為比較和排序依據(jù)，則該數(shù)據(jù)項(xiàng)稱為排序關(guān)鍵字。 
	for(int i=0;i<5;i  ){
		cout<<"第"<<i 1<<"次待排序的100個(gè)數(shù)為："<<endl; 
		sqlist L,L1,L2,L3,L4,L5,L6;
		L.size=100;
		for(int j=1;j<=100;j  ){
			int t;
			t=rand()0;
			L.sq[j]=t;
			cout<<L.sq[j]<<" ";
		}
		cout<<endl;
		L1=L2=L3=L4=L5=L6=L;
		bubble_sort(&L1);
	//	for(int i=1;i<=100;i  )
	//		cout<<L1.sq[i]<<" ";
		insertion_sort(&L2); 
	//	for(int i=1;i<=100;i  )
	//		cout<<L2.sq[i]<<" ";
		selection_sort(&L3); 
	//	for(int i=1;i<=100;i  )
	//		cout<<L3.sq[i]<<" ";
		quick_sort(&L4); 
	//	for(int i=1;i<=100;i  )
	//		cout<<L4.sq[i]<<" ";
		shell_sort(&L5);
	//	for(int i=1;i<=100;i  )
	//			cout<<L5.sq[i]<<" ";
		heap_sort(&L6);
	//	for(int i=1;i<=100;i  )
	//		cout<<L6.sq[i]<<" ";
	} 
}