#include <iostream>
#include"time.h"
using namespace std;
typedef int KeyType;
struct LElemType                 //顺序表元素
{
	KeyType key;
};
struct SList
{
    LElemType *r;
	int length;
};
bool ListCreate(SList &L,int n,KeyType  a[]);//创建顺序表
void Listshow(SList &L);//显示表
void InsertSort(SList L,int &fz,int &bj);//直接插入排序法
void SelectSort(SList L, int &fz, int &bj);//简单选择排序
int Partition(SList &L, int a, int b, int &fz, int &bj);
void QuickSort(SList L, int &fz, int &bj); //快速排序
void QSort(SList &L, int a, int b, int &fz, int &bj);
void HeapSort(SList H,int &fz,int &bj);  //堆排序
void HeapSort(SList H,int &fz,int &bj);
void Merge(SList &L, int a, int m, int b,int &fz,int &bj);
void MergeSort(SList L,int &fz,int &bj); //归并排序
int main()
{
	SList L; const int n = 1000; int fz, bj;
	KeyType *a = new KeyType[n+1]; srand((unsigned)time(NULL));
	for (int i = 1; i <= n; i++) {
		a[i] = rand()%n;
	}
	ListCreate(L, n, a);
	InsertSort(L, fz, bj);
	cout << "直接插入排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
	ListCreate(L, n, a);
	SelectSort(L, fz, bj); 
	cout << "简单选择排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
	ListCreate(L, n, a);
	QuickSort(L, fz, bj); 
	cout << "快速排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
	ListCreate(L, n, a);
	HeapSort(L, fz, bj);
	cout << "堆排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
	ListCreate(L, n, a);
	MergeSort(L, fz, bj);
	cout << "归并排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
	return 0;
}
bool ListCreate(SList &L,int n,KeyType a[])
{
	L.r = new LElemType[n+1];    
	if (!L.r) {
		return false;                        
	}
	L.length = n;
	for (int i = 1; i <= n; i++) {
		L.r[i].key = a[i];
	}
	return true;
}
void Listshow(SList &L)
{
	int i=L.length;
	for(int j=1;j<=i;j++)
	{
		cout<<L.r[j].key<<"  ";
	}
}
void InsertSort(SList L,int &fz,int &bj) {           
	fz = 0; bj = 0;
	int i, j; LElemType x;
	for (i = 2; i <= L.length; i++) {
		for (fz++,x = L.r[i], j = i - 1; j >= 1 && (bj++, x.key < L.r[j].key); j--) {
			L.r[j + 1] = L.r[j]; fz++;
		}
		L.r[j + 1] = x; fz++;
	}
}

void SelectSort(SList L, int &fz, int &bj) {            
	fz = 0; bj = 0;
	int i, j, k; LElemType x;
	for (i = 1; i <= L.length-1; i++) {
		k = i;
		for (j = i + 1; j <= L.length; j++) {
			if (bj++,L.r[j].key < L.r[k].key) k = j;
		}
		if (k > i) {
			x = L.r[i]; fz++;
			L.r[i] = L.r[k]; fz++;
			L.r[k] = x; fz++;
		}
	}
}

int Partition(SList &L, int a, int b, int &fz, int &bj) {
	LElemType x = L.r[a]; fz++;
	while (a < b) {
		while (a < b && (bj++,L.r[b].key >= x.key)) {
			b--;
		}
		L.r[a] = L.r[b]; fz++;
		while (a < b && (bj++,L.r[a].key <= x.key)) {
			a++;
		}
		L.r[b] = L.r[a]; fz++;
	}
	L.r[a] = x; fz++; return a;
}
void QSort(SList &L, int a, int b, int &fz, int &bj) {
	int p;
	if (a >= b)return;
	p = Partition(L, a, b,fz,bj); 
	QSort(L, a, p - 1,fz,bj); QSort(L, p + 1, b,fz,bj);
}
void QuickSort(SList L, int &fz, int &bj) {                  
	fz = 0; bj = 0;
	QSort(L, 1, L.length, fz, bj);
}

void HeapAdjust(SList &H, int s, int m,int &fz,int &bj) {
	//设L.r[s+1:m]满足堆的条件，本算法调整H使H.r[s:m]为堆
	int j; LElemType x;
	x = H.r[s]; fz++; j = 2 * s;
	while (j <= m) {
		if (j < m && (bj++,H.r[j].key < H.r[j + 1].key)) j++;
		if (bj++,x.key >= H.r[j].key) break;
		H.r[s] = H.r[j]; fz++; s = j; j = 2 * j;
	}
	H.r[s] = x; fz++;
}
void HeapSort(SList H,int &fz,int &bj) {                       
	fz = 0; bj = 0;
	int i; LElemType x;
	for (i = H.length / 2; i >= 1; i--) HeapAdjust(H, i, H.length,fz,bj);
	//将H.r[1:H.length]建成堆
	for (i = H.length; i >= 2; i--) {
		x = H.r[1]; H.r[1] = H.r[i]; H.r[i] = x; fz += 3;
		HeapAdjust(H, 1, i - 1,fz,bj);
	}
}

void Merge(SList &L, int a, int m, int b,int &fz,int &bj) {
	int i, j, k, s; LElemType *t;
	t = new LElemType[m - a + 1]; i = 0; j = m + 1; k = a - 1;
	for (s = a; s <= m; s++) { t[s - a] = L.r[s]; fz++; }
	while (i <= m - a&&j <= b) {
		k++;
		if (bj++, t[i].key <= L.r[j].key) { L.r[k] = t[i]; fz++; i++; }
		else { L.r[k] = L.r[j]; fz++; j++; }
	}
	while (i <= m - a) { k++; L.r[k] = t[i]; fz++; i++; }
	delete[]t;
}
void MergeSort(SList L,int &fz,int &bj) {             
	fz = 0; bj = 0;
	int a, b, m, h;
	for (h = 1; h < L.length; h *= 2) {
		for (a = 1;; a += 2 * h) {
			m = a + h - 1; if (m >= L.length)break;
			b = m + h; if (b > L.length) b = L.length;
			Merge(L, a, m, b, fz, bj);
		}
	}
}