#include<iostream>
using namespace std;

void swap(int * t, int i, int j){
	int temp = t[i];
	t[i] = t[j];
	t[j] = temp;
}
//归并排序：

void Merge(int*a, int*temp,int low, int mid, int high){
	int i, lEnd, NumElements, tempos;
	lEnd = mid - 1;
	tempos = low;
	NumElements = high - low + 1;
	while (low < lEnd && mid <= high){
		if (a[low] <= a[mid]){
			temp[tempos++] = a[low++];
		}
		else{
			temp[tempos++] = a[mid++];
		}
	}
	while (low <= lEnd){
		temp[tempos++] = a[low++];
	}
	while (mid <= high){
		temp[tempos++] = a[mid++];
	}
	for (i = 0; i < NumElements; i++, high--){
		a[high] = temp[high];
	}
}

void msort(int *a, int *temp, int low, int high){
	if (low >= high)return;
	int middle = (low + high) / 2;
	msort(a, temp, low, middle);// 对[low,mid]递归做归并排序
	msort(a, temp, middle + 1, high);//对[mid+1,high]递归做归并排序
	Merge(a, temp, low, middle + 1, high);//组合，把两个有序区合并为一个有序区
}



void merge_sort(int*a, int len){
	int *temp = NULL;
	temp = new int[len];
	if (temp != NULL){
		msort(a, temp, 0, len - 1);
		delete []temp;
	}
}

// 堆排序：
int heapsize = 0;
//返回左节点的索引
int Left(int index){ return ((index << 1) + 1); 
}
int Right(int index){
	return ((index << 1) + 2);
} 

void maxHeapify(int *a, int index){
	int largest = 0;
	int left = Left(index);
	int right = Right(index);
	if ((left <= heapsize) && (a[left] > a[index]))
		largest = left;
	else
		largest = index;
	if ((right <= heapsize) && (a[right] > a[largest]))
		largest = right;
	if (largest != index){
		swap(a, index, largest);
		maxHeapify(a, largest);
	}
}

void buildMaxheap(int array[], int length){
	int i;
	heapsize = length;
	for (i = length >> 1; i >= 0; i--)
	{
		maxHeapify(array, i);
	}
}

void heap_sort(int *a, int leng){
	buildMaxheap(a, leng-1);//建立大堆
	for (int i = (leng - 1); i >= 1; i--){
		swap(a, i, 0);
		heapsize--;
		maxHeapify(a, 0);
	}
}


// 选择排序：

void choice(int *a, int len){
	int i, j, x, l;
	for (int i = 0; i < len - 1; i++){
		x = a[i];
		l = i;
		for (j = i; j < len; j++){
			if (a[j] < x){
				x = a[j];
				l = j;
			}
		}
		a[l] = a[i];
		a[i] = x;
	}
}

//冒泡排序：
void maopao(int *a, int len){
	int flag = 0;
	for (int i = 0; i <len-1; i++){
		for (int j = len-1; j > i; j--){
			if (a[j] < a[j - 1])
				swap(a, j, j - 1);
			    flag = 1;
		}
		if (flag != 1){
			break;
		}
	}
}

//快速排序：

int fastpaixu(int a[], int low, int high){


	int pivot = a[low];
	while (low < high){
		while (low < high&& a[high] >= pivot){
			high = high - 1;
		}
		swap(a, low, high);
		while (low < high&& a[low] < pivot){
			low = low + 1;
		}
		swap(a, low, high);
	}
	return low;
}

void fast(int a[], int low, int high){
	int pirot;
	if (low < high){
		pirot = fastpaixu(a, low, high);
		fast(a, low, pirot - 1);
		fast(a, low+1, high);
	}
}



//希尔排序：

void shell_sort(int *a, int len){
	int h, i,j, temp;
	for (h = len / 2; h > 0; h=h/2){
		for (i = h; i < len; i++){
			temp = a[i];
			for (j = i - h; (j >= 0 && temp < a[j]); j -= h){
				a[j + h] = a[j];
			}
			a[j + h] = temp;
		}
	}
}
int main(void){
	int data[9] = { 54, 38, 96, 23, 15, 72, 60, 45, 83 };
	//fast(data, 0, 8);   //快速排序
	//maopao(data, 9);//冒泡排序
	//choice(data, 9);//选择排序
	//heap_sort(data, 9);//堆排序
	//merge_sort(data, 9);
	shell_sort(data, 9);
	for (int i = 0; i < 8; i++)
	{
		cout << data[i] <<" ";
	}
	return 0;
}