快排-归并-希尔-冒泡-插入及基数排序C++实现
#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#define MAX_ARRAY_LENGTH 100000float array[MAX_ARRAY_LENGTH + 1];int n = 0;__int64 startTime, endTime;void InitArray(float *, int);/**************************************************************快速排序相关函数/*************************************************************/void swapFloat(float &a, float &b);int Partition(float *, int, int);void QuickSort(float *array, int low, int high);void PrintArray(float *array, int n);__int64 QuickExcuteTime(int n);/*桶排序相关数据结构及函数*/#define BUCKET_LENGTH 11struct node{double data;struct node * next;};typedef struct node * BucketNode;BucketNode bucket[BUCKET_LENGTH];BucketNode InsertNode(BucketNode, float);void PrintOneBucket(BucketNode, int &);void PrintBucket();void BucketSort(int);void CleanBucket();__int64 BucketExcuteTime(int n);/*归并排序相关函数*/void MergeSort(float *array, float *tempArray, int left, int right);void Merge(float *array, int left, int right, int middle);__int64 MergeExcuteTime(int n);/*冒泡排序相关函数*/void BubbleSort(float *, int);__int64 BubbleExcuteTime(int);/*插入排序相关函数*/void InsertSort(float *array, int n);__int64 InsertExcuteTime(int);/*希尔排序相关函数*/void ShellSort(float *array, int n);__int64 ShellExcuteTime(int n);/*获取时间,单位是微秒*/__int64 GetCPUTime() {static LARGE_INTEGER li = {0};LARGE_INTEGER linow = {0};if (li.QuadPart == 0)QueryPerformanceFrequency(&li);QueryPerformanceCounter(&linow);return linow.QuadPart *100000/ li.QuadPart;}#ifdef __TURBOC__ #define get_clock_ticks(x) x = biostime(0,0L)#else #define get_clock_ticks(x) x = GetCPUTime()#endif/*****起始时间和结束时间***************************************************//*三个实验测试用例*/void ExperimentOne(int);void ExcuteWithNumber(int);void ExperimentTwo(int, int, int);void ExperimentThree(int, int, int, int);void MyExperiment(){printf("================Have a nice day=======================\n");printf("===========输入1: N=10时排序结果及运行时间============\n");printf("===========输入2: 同一排序算法不同样本测试============\n");printf("===========输入3: 每个排序不同样本多次测试求平均时间\n");printf("===========输入0: 退出实验============================\n");int cases = 0;while(scanf("%d", &cases) != EOF){if(cases == 0) break;switch(cases){case 1:{n = 10;ExperimentOne(n);break;}case 2:{ExperimentTwo(1000, 10000, 100000);break;}case 3:{ExperimentThree(1000, 10000, 100000, 5);break;}default:{printf("没有可选项");break;}}printf("================Have a nice day=======================\n"); printf("===========输入1: N=10时排序结果及运行时间============\n"); printf("===========输入2: 同一排序算法不同样本测试============\n"); printf("===========输入3: 每个排序不同样本多次测试求平均时间\n"); printf("===========输入0: 退出实验============================\n");}}int main(int args, char *argv[]){MyExperiment();return 0;}/*随机产生n个数array数组*/void InitArray(float *array, int n){srand( (unsigned)time(NULL) );for(int i=1; i<=n; i++){//scanf("%f", &array[i]);array[i] = (float)(rand()/(RAND_MAX+1.0));}}/********************************************************************桶排序接口/*******************************************************************//*head 为bucket[i],插入节点值为data*/BucketNode InsertNode(BucketNode head, float data){BucketNode newNode = (BucketNode)malloc(sizeof(struct node));newNode->data = data;newNode->next = NULL;BucketNode p = head;if(head == NULL){head = newNode;}else{while(p->next != NULL && data > p->next->data){p = p->next;}newNode->next = p->next;p->next = newNode;}return head;}/*插入n个数据的桶排序*/void BucketSort(int n){int i = 0;for(i=0; i<BUCKET_LENGTH; i++)bucket[i] = NULL;float data = 0.0;srand( (unsigned)time(NULL) );for(i=0; i<n; i++){data = (float)rand()/(RAND_MAX + 1);int key = (int)(data*10); bucket[key] = InsertNode(bucket[key], data);}}/*输出桶中一个区间的链表*/void PrintOneBucket(BucketNode head, int &count){BucketNode p = head;while(p != NULL){printf("%.8f ", p->data);if(count%7 == 0)printf("\n");count++;p = p->next;}}/*输出桶排序结果*/void PrintBucket(){int count = 1;for(int i=0; i<BUCKET_LENGTH; i++){PrintOneBucket(bucket[i], count);}printf("\n");}/*清空桶*/void CleanBucket(){for(int i=0; i<BUCKET_LENGTH; i++){BucketNode p = bucket[i];BucketNode q;while(p != NULL){q = p->next;free(p);p = q;}}}/*计算n个数据的桶排序执行时间*/__int64 BucketExcuteTime(int n){get_clock_ticks(startTime);BucketSort(n);get_clock_ticks(endTime);__int64 costTime = (endTime - startTime)*100;CleanBucket();return costTime;}/*************************************************************************************/快序排序/************************************************************************************//*交换两个浮点数*/void swapFloat(float &a, float &b){float t = a;a = b;b = t;}/**/void QuickSort(float *array, int low, int high){if(low < high){int pivotLoc = Partition(array, low, high);QuickSort(array, low, pivotLoc-1);QuickSort(array, pivotLoc, high);//low = pivotLoc + 1; }}/*找到轴心*/int Partition(float *array, int low, int high){int r = high - rand()%(high-low);swapFloat(array[high], array[r]);float x = array[high];int i = low - 1;for(int j=low; j<high; j++){if(array[j] <= x){i = i + 1;swapFloat(array[i], array[j]);}}swapFloat(array[i+1], array[high]);return (i + 1);}/*计算n个数据的快排执行时间*/__int64 QuickExcuteTime(int n){InitArray(array, n);get_clock_ticks(startTime);QuickSort(array, 1, n);get_clock_ticks(endTime);__int64 costTime = (endTime - startTime)*100;return costTime;}/*****************************************************************************************/希尔排序接口/****************************************************************************************//*希尔排序*/void ShellSort(float *array, int n){ float temp = 0.0; for(int step=n/2; step>0; step/=2){for(int i=step; i<=n; i++) { temp = array[i]; for(int j=i; j>=step; j-=step) { if(temp < array[j-step]) { array[j] = array[j - step]; } else { break; } } array[j] = temp; }}}/*n个数据的希尔排序实行时间*/__int64 ShellExcuteTime(int n){InitArray(array, n);get_clock_ticks(startTime);ShellSort(array, n);get_clock_ticks(endTime);__int64 costTime = (endTime - startTime)*100;return costTime;}/*****************************************************************/插入排序/****************************************************************//*n个数据的插入排序*/void InsertSort(float *array, int n){for(int i=1; i<=n; i++){float key = array[i];int j = i -1;while(array[j] > key && j>=1){array[j+1] = array[j];j = j -1;}array[j+1] = key;}}/*n个数据的插入排序执行时间*/__int64 InsertExcuteTime(int n){InitArray(array, n);get_clock_ticks(startTime);InsertSort(array, n);get_clock_ticks(endTime);__int64 costTime = (endTime - startTime)*100;return costTime;}/*****************************************************************/归并排序/*****************************************************************//*将两个子数组归并*/void Merge(float *array, float *tempArray, int left, int right, int middle){int leftIndex = left;int rightIndex = middle + 1;for(int i=left; (leftIndex<=middle)&&(rightIndex<=right); i++){if(array[leftIndex] < array[rightIndex])tempArray[i] = array[leftIndex++];elsetempArray[i] = array[rightIndex++];}while(leftIndex <= middle)tempArray[i++] = array[leftIndex++];while(rightIndex <= right)tempArray[i++] = array[rightIndex++];for(i=left; i<=right; i++)array[i] = tempArray[i]; }/*归并排序*/void MergeSort(float *array, float *tempArray, int left, int right){if(left < right){int middle = left + (right - left)/2; MergeSort(array, tempArray, left, middle);MergeSort(array, tempArray, middle+1, right);Merge(array, tempArray, left, right, middle);}}/*n个数据的归并排序执行时间*/__int64 MergeExcuteTime(int n){InitArray(array, n);float tempArray[100001];get_clock_ticks(startTime);MergeSort(array, tempArray, 1, n);get_clock_ticks(endTime);__int64 costTime = (endTime - startTime)*100;return costTime;}/****************************************************************************/冒泡排序/****************************************************************************/void BubbleSort(float *array, int n) { for(int i=1; i<=n; i++) { for(int j=1; j<i; j++) { if(array[j] > array[j+1]) swapFloat(array[j], array[j+1]); } }}__int64 BubbleExcuteTime(int n){InitArray(array, n);get_clock_ticks(startTime);BubbleSort(array, n);get_clock_ticks(endTime);__int64 costTime = (endTime - startTime)*100;return costTime;}void PrintArray(float *array, int n){for(int i=1; i<=n; i++){printf("%.8f ", array[i]);if(i%7 == 0) printf("\n");}if(n%7 != 0) printf("\n");}/*实验的第一个测试用例*/void ExperimentOne(int n){__int64 excuteTime = 0;InitArray(array, n);excuteTime = QuickExcuteTime(n);printf("N=%d快速排序运行时间%I64d微秒\n", n, excuteTime);PrintArray(array, n);excuteTime = BucketExcuteTime(n);printf("N=%d桶排序运行时间%I64d微秒\n", n, excuteTime);PrintArray(array, n);excuteTime = ShellExcuteTime(n);printf("N=%d希尔排序运行时间%I64d微秒\n", n, excuteTime);PrintArray(array, n);excuteTime = InsertExcuteTime(n);printf("N=%d插入排序运行时间%I64d微秒\n", n, excuteTime);PrintArray(array, n);excuteTime = MergeExcuteTime(n);printf("N=%d归并排序运行时间%I64d微秒\n", n, excuteTime);PrintArray(array, n);excuteTime = BubbleExcuteTime(n);printf("N=%d冒泡排序运行时间%I64d微秒\n", n, excuteTime);PrintArray(array, n);}/*数组个数为n,测试各个算法的运行时间*/void ExcuteWithNumber(int n){__int64 excuteTime = 0;InitArray(array, n);excuteTime = QuickExcuteTime(n);printf("快速排序运行时间%I64d微秒\n", excuteTime);excuteTime = BucketExcuteTime(n);printf("桶排序运行时间%I64d微秒\n", excuteTime);excuteTime = ShellExcuteTime(n);printf("希尔排序运行时间%I64d微秒\n", excuteTime);excuteTime = InsertExcuteTime(n);printf("插入排序运行时间%I64d微秒\n", excuteTime);excuteTime = MergeExcuteTime(n);printf("归并排序运行时间%I64d微秒\n", excuteTime);excuteTime = BubbleExcuteTime(n);printf("冒泡排序运行时间%I64d微秒\n", excuteTime);}/*实验的第二个测试用例*/void ExperimentTwo(int n1, int n2, int n3){printf("N=%d时同一样本各个算法测试\n", n1);ExcuteWithNumber(n1);printf("\nN=%d时同一样本各个算法测试\n", n2);ExcuteWithNumber(n2);printf("\nN=%d时同一样本各个算法测试\n", n3);ExcuteWithNumber(n3);}/*实验第三个测试时辅助函数*/void ExperimentThreeAtN(int arrayNum, int testTimes){int i = 0;__int64 sumTime = 0, costTime = 0;for(i=0; i<testTimes; i++){costTime = BucketExcuteTime(arrayNum);sumTime += costTime;}printf("N=%d桶排序执行%d次的平均时间为%I64d微秒\n", arrayNum, testTimes, (__int64)(sumTime/testTimes));sumTime = 0;for(i=0; i<testTimes; i++){costTime = QuickExcuteTime(arrayNum);sumTime += costTime;}printf("N=%d快速排序执行%d次的平均时间%I64d微秒\n", arrayNum, testTimes, (__int64)(sumTime/testTimes));sumTime = 0;for(i=0; i<testTimes; i++){costTime = MergeExcuteTime(arrayNum);sumTime += costTime;}printf("N=%d归并排序执行%d次的平均时间%I64d微秒\n", arrayNum, testTimes, (__int64)(sumTime/testTimes));sumTime = 0;for(i=0; i<testTimes; i++){costTime = BubbleExcuteTime(arrayNum);sumTime += costTime;}printf("N=%d冒泡排序执行%d次的平均时间%I64d微秒\n", arrayNum,testTimes, (__int64)(sumTime/testTimes));sumTime = 0;for(i=0; i<testTimes; i++){costTime = ShellExcuteTime(arrayNum);sumTime += costTime;}printf("N=%d希尔排序执行%d次的平均时间%I64d微秒\n", arrayNum, testTimes, (__int64)(sumTime/testTimes));sumTime = 0;for(i=0; i<testTimes; i++){ costTime = InsertExcuteTime(arrayNum);sumTime += costTime;}printf("N=%d插入排序执行%d次的平均时间%I64d微秒\n", arrayNum, testTimes, (__int64)(sumTime/testTimes));}/*第三个测试用例*/void ExperimentThree(int n1, int n2, int n3, int testTimes){ExperimentThreeAtN(n1, testTimes);printf("\n");ExperimentThreeAtN(n2, testTimes);printf("\n");ExperimentThreeAtN(n3, testTimes);}