一时兴起

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstring>
using namespace std;
#define SIZE 10
void heapSort(int size, int data[]) {
	int cur = (size - 2) / 2;
	int tmp;
	//构建最大堆
	while(cur >= 0) {
		int j = 2 * cur + 1;
		int i = cur;
		tmp = data[cur];
		while(j < size) {
			if(j < size - 1 && data[j] < data[j + 1]) j++;
			if(data[j] <= tmp) break;
			data[i] = data[j];
			i = j;
			j = 2 * j + 1;
		}
		data[i] = tmp;
		cur--;
	}
	//开始排序
	cur = size - 1;
	while(cur > 0) {
		tmp = data[cur];
		data[cur] = data[0];
		data[0] = tmp;
		//调整堆
		int j = 1;
		int i = 0;
		tmp = data[0];
		while(j < cur) {
			if(j < cur - 1 && data[j] < data[j + 1]) j++;
			if(data[j] <= tmp) break;
			data[i] = data[j];
			i = j;
			j = 2 * j + 1;
		}
		data[i] = tmp;
		cur--;
	}
}
void quickSort(int beg, int end,int data[]) {
	int x = beg, y = end;
	int tmp;
	while(x < y) {
		while(x < y && data[x] <= data[y]) y--;
		if(x < y) {
			tmp = data[x];
			data[x] = data[y];
			data[y] = tmp;
			x++;
		}
		while(x < y && data[x] <= data[y]) x++;
		if(x < y) {
			tmp = data[x];
			data[x] = data[y];
			data[y] = tmp;
			y--;
		}
	}
	if(beg < x - 1) quickSort(beg, x - 1, data);
	if(y + 1 < end) quickSort(y + 1, end, data);
}
void shellSort(int size, int data[]) {
	int increment = size / 2;
	int tmp;
	while(increment >= 1) {
		for(int i = 0; i < increment; i++) {
			for(int j = i; j < size; j += increment) {
				for(int k = j + increment; k < size; k += increment) {
					if(data[k] < data[k - increment]) {
						tmp = data[k];
						data[k] = data[k - increment];
						data[k - increment] = tmp;
					}
				}
			}
		}
		increment /= 2;
	}
}
void mergeSort(int beg, int end, int data[]) {
	if(beg >= end) return;
	int mid = (beg + end) / 2;
	mergeSort(beg, mid, data);
	mergeSort(mid + 1, end, data);
	
	int leftLength = mid - beg + 1;
	int rightLength = end - mid;
	int *leftHalf = new int[leftLength];
	int *rightHalf = new int[rightLength];
	memcpy(leftHalf, &data[beg], sizeof(int) * leftLength);
	memcpy(rightHalf, &data[mid + 1], sizeof(int) * rightLength);
	int i = 0, j = 0;
	int cur = beg;
	while(i < leftLength && j < rightLength) {
		if(leftHalf[i] < rightHalf[j]) {
			data[cur++] = leftHalf[i];
			i++;
		}else {
			data[cur++] = rightHalf[j];
			j++;
		}
	}
	if(i == leftLength) {
		for(int k = j; k < rightLength; k++) {
			data[cur++] = rightHalf[k];
		}
	}else {
		for(int k = i; k < leftLength; k++) {
			data[cur++] = leftHalf[k];
		}
	}
}
int main() {
	srand(time(NULL));
	int a[SIZE];
	cout << "heap sort..." << endl;
	for(int i = 0; i < SIZE; i++) {
		a[i] = rand() % 100;
	}
	for(int i = 0; i < SIZE; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	heapSort(SIZE, a);
	for(int i = 0; i < SIZE; i++) {
		cout << a[i] << " ";
	}
	cout << endl << endl;
	cout << "quick sort..." << endl;
	for(int i = 0; i < SIZE; i++) {
		a[i] = rand() % 100;
	}
	for(int i = 0; i < SIZE; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	quickSort(0, SIZE - 1, a);
	for(int i = 0; i < SIZE; i++) {
		cout << a[i] << " ";
	}
	cout << endl << endl;

	cout << "shell sort..." << endl;
	for(int i = 0; i < SIZE; i++) {
		a[i] = rand() % 100;
	}
	for(int i = 0; i < SIZE; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	shellSort(SIZE, a);
	for(int i = 0; i < SIZE; i++) {
		cout << a[i] << " ";
	}
	cout << endl << endl;

	cout << "merge sort..." << endl;
	for(int i = 0; i < SIZE; i++) {
		a[i] = rand() % 100;
	}
	for(int i = 0; i < SIZE; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	mergeSort(0, SIZE - 1, a);
	for(int i = 0; i < SIZE; i++) {
		cout << a[i] << " ";
	}
	cout << endl << endl;
	return 0;
}