#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<<"冒泡排序关键字的比较次数为："<<l<<endl;
	cout<<"冒泡排序关键字的移动次数为："<<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<<"直接插入排序关键字的比较次数为："<<l<<endl;
	cout<<"直接插入排序关键字的移动次数为："<<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<<"直接选择排序关键字的比较次数为："<<l<<endl;
	cout<<"直接选择排序关键字的移动次数为："<<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<<"快速排序关键字的比较次数为："<<l<<endl;
	cout<<"快速排序关键字的移动次数为："<<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<<"希尔排序关键字的比较次数为："<<l<<endl;
	cout<<"希尔排序关键字的移动次数为："<<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<<"堆排序关键字的比较次数为："<<l<<endl;
	cout<<"堆排序关键字的移动次数为："<<k<<endl;
}

int main(){
	//关键字：一个数据元素可由多个数据项组成，
	//以数据元素某个数据项作为比较和排序依据，则该数据项称为排序关键字。 
	for(int i=0;i<5;i++){
		cout<<"第"<<i+1<<"次待排序的100个数为："<<endl; 
		sqlist L,L1,L2,L3,L4,L5,L6;
		L.size=100;
		for(int j=1;j<=100;j++){
			int t;
			t=rand()%100;
			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]<<" ";
	} 
}