// SortTest.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include 
     
      using namespace std;void swap(int& a, int& b) {	int c = a;	a = b;	b = c;}void BubbleSort(int arr[],int length) {	for (int i = 0; i < length-1; i++) {		for (int j = 0; j < length - i-1; j++) {			if (arr[j] > arr[j + 1]) {				swap(arr[j], arr[j+ 1]);				//此处可增加是否跳出标记 标记为真			}		}		//此处检测跳出标记 若标记为假 则说明此次循环数据已无变动 		//排序结束 可跳出循环	}}void PrintArray(int arr[], int length) {	for (int i = 0; i < length; i++) {		std::cout << arr[i] << " ";	}	std::cout << std::endl;}void TestBubbleSort() {	int testArr1[] = { 12,76,12,18,99,12,12,35,12,12 };	int testArr2[] = { 1,2,3,8,7,4,5,6,7,8,9,0 };	int testArr3[] = { 0,9,3,4,8,7,99,6,7,88,5,33,66,4,3,2,1 };#define TESTARR(ARR)								\do{													\	BubbleSort(ARR, sizeof(ARR) / sizeof(ARR[0]));	\	PrintArray(ARR, sizeof(ARR) / sizeof(ARR[0]));	\}while(0)	TESTARR(testArr1);	TESTARR(testArr2);	TESTARR(testArr3);	std::cout << std::endl;}//=============================================================void QuickSort(int arr[], int left, int right) {	int i = left;	int j = right;	if (left >= right)		return;	int temp = arr[left];	while (i != j) {		while (j != i && arr[j] >=  temp)			j--;		while (j != i && arr[i] <=  temp)			i++;		if (i < j) {			swap(arr[i],arr[j]);		}	}	arr[left] = arr[i];	arr[i] = temp;	QuickSort(arr,left,i-1);	QuickSort(arr, i+1,right);}void TestQuickSort() {	int testArr1[] = { 12,76,12,18,99,12,12,35,12,12 };	int testArr2[] = { 1,2,3,8,7,4,5,6,7,8,9,0 };	int testArr3[] = { 0,9,3,4,8,7,99,6,7,88,5,33,66,4,3,2,1 };#define TESTQUICKARR(ARR)								\do{													\	QuickSort(ARR, 0,sizeof(ARR) / sizeof(ARR[0])-1);	\	PrintArray(ARR, sizeof(ARR) / sizeof(ARR[0]));	\}while(0)	TESTQUICKARR(testArr1);	TESTQUICKARR(testArr2);	TESTQUICKARR(testArr3);	std::cout << std::endl;}//=======================================struct HeapArray {	int heapArr[100];	int heapSize;	HeapArray() {		heapSize = 0;		for (int i = 0; i < 100; i++) {			heapArr[i] = -1;		}	}};HeapArray heapA;void HeadpAdjustTopDown(int index) {	while(index*2+1 <= heapA.heapSize-1){		if (index * 2 + 2 <= heapA.heapSize - 1) {			if (heapA.heapArr[index] > heapA.heapArr[index * 2 + 1] &&				heapA.heapArr[index * 2 + 1] <= heapA.heapArr[index * 2 + 2]) {				swap(heapA.heapArr[index], heapA.heapArr[index * 2 + 1]);				index = index * 2 + 1;				continue;			}			else if (heapA.heapArr[index] > heapA.heapArr[index * 2 + 2] &&				heapA.heapArr[index * 2 + 2] <= heapA.heapArr[index * 2 + 1]) {				swap(heapA.heapArr[index], heapA.heapArr[index * 2 + 2]);				index = index * 2 + 2;				continue;			}		}		else { // 仅有左儿子情况			if (heapA.heapArr[index] > heapA.heapArr[index * 2 + 1]) {				swap(heapA.heapArr[index], heapA.heapArr[index * 2 + 1]);				index = index * 2 + 1;				continue;			}		}		break;	}}void HeadpAdjustDownTop(int index) {	int i = index;	while (i != 0) {		if (heapA.heapArr[i] < heapA.heapArr[(i - 1) / 2]) {			swap(heapA.heapArr[i], heapA.heapArr[(i - 1) / 2]);			i = (i-1) / 2;		}		else {			break;		}	}}void HeapInsert(int in) {	heapA.heapArr[heapA.heapSize] = in;	HeadpAdjustDownTop(heapA.heapSize);	heapA.heapSize++;}void HeapSort(int arr[],int length) {	heapA.heapSize = 0;	for (int i = 0; i < 100; i++) {		heapA.heapArr[i] = -1;	}	for (int i = 0; i < length; i++) {		HeapInsert(arr[i]);	}}void PrintHeap() {	int j = heapA.heapSize;	for (int i = 0; i < j; i++) {		std::cout << heapA.heapArr[0] << " ";		heapA.heapArr[0] = heapA.heapArr[heapA.heapSize - 1];		heapA.heapSize--;		HeadpAdjustTopDown(0);	}	std::cout << std::endl;}void TestHeapSort() {	int testArr1[] = { 12,76,12,18,99,12,12,35,12,12 };	int testArr2[] = { 1,2,3,8,7,4,5,6,7,8,9,0 };	int testArr3[] = { 0,9,3,4,8,7,99,6,7,88,5,33,66,4,3,2,1 };#define TESTHEAPARR(ARR)								\do{													\	HeapSort(ARR, sizeof(ARR) / sizeof(ARR[0]));	\	PrintHeap();	\}while(0)	TESTHEAPARR(testArr1);	TESTHEAPARR(testArr2);	TESTHEAPARR(testArr3);	std::cout << std::endl;}//=================================================void MergeArr(int arr[], int lbegin, int lend, int rbegin, int rend, int tmp[]) {	int i = lbegin,j = lend,m = rbegin, n = rend,k = 0;	while (i <= j && m <= n) {		if (arr[i] <= arr[m]) {			tmp[k++] = arr[i++];		}		else {			tmp[k++] = arr[m++];		}	}	while (i <= j)		tmp[k++] = arr[i++];	while (m <= n) 		tmp[k++] = arr[m++];	for (int i = 0; i < k; i++) {		arr[lbegin + i] = tmp[i];	}}void MergeSort(int a[], int first, int last, int temp[]) {	if (first < last) {		int mid = (first + last) / 2;		MergeSort(a, first, mid, temp);    		MergeSort(a, mid + 1, last, temp); 		MergeArr(a,first,mid, mid + 1,last,temp);	}}bool MergeSort(int arr[], int n){	int *tmp = new int[n];	MergeSort(arr, 0, n - 1, tmp);	delete[] tmp;	return true;}void TestMergeSort() {	int testArr1[] = { 12,76,12,18,99,12,12,35,12,12 };	int testArr2[] = { 1,2,3,8,7,4,5,6,7,8,9,0 };	int testArr3[] = { 0,9,3,4,8,7,99,6,7,88,5,33,66,4,3,2,1 };#define TESTMERGEARR(ARR)								\do{													\	MergeSort(ARR, sizeof(ARR) / sizeof(ARR[0]));	\	PrintArray(ARR, sizeof(ARR) / sizeof(ARR[0]));	\}while(0)	TESTMERGEARR(testArr1);	TESTMERGEARR(testArr2);	TESTMERGEARR(testArr3);	std::cout << std::endl;}//=============================================int main(){	TestQuickSort();	TestBubbleSort();	TestHeapSort();	TestMergeSort();    return 0;}