对比归并排序和快速排序的性能实验数据：
{99,95,90,88,85,83,80,75,70,65,60,55,50}
伪代码表示：
核心代码：
实现代码：#include<iostream>using namespace std;/************声明归并排序函数*****************/void Merge(int r[],int r1[],int s,int m,int t);void MergeSort(int r[],int s,int t);/************声明归并排序函数*****************/int Partition(int r[],int first,int end);void QuickSort(int r[],int first,int end);static int compareCount[2] = {0};//用来统计比较次数,compareCount[0]统计归并排序产生比较次数,compareCount[1]统计快速排序产生比较次数.static int moveCount[2] = {0};//用来统计移动次数,moveCount[0]统计归并排序产生移动次数,moveCount[1]统计快速排序产生移动次数.static int tempCompareCount = 0;//用来辅助归并排序，统计每次合并产生的比较次数，辅助快速排序每次划分产生的比较次数static int tempMoveCount = 0;//用来辅助归并排序，统计每次合并产生的移动次数，辅助快速排序每次划分产生的移动次数/************统计归并排序每次合并产生的比较次数与移动次数*****************/static int mergeSortCompareCount[4] = {0};//用来统计归并排序4次合并过程，每次合并产生的比较次数static int mergeSortMoveCount[4] = {0};//用来统计归并排序4次合并过程，每次合并产生的移动次数/************统计快速排序每次合并产生的比较次数与移动次数*****************/static int index = 0;//用于辅助划分计数int quickSortCompareCount[12] = {0};//用来统计快速排序12次划分过程，每次划分产生的比较次数int quickSortMoveCount[12] = {0};//用来统计快速排序12次划分过程，每次划分产生的移动次数int main(){int rm[] = {99,95,90,88,85,83,80,75,70,65,60,55,50};int rq[] = {99,95,90,88,85,83,80,75,70,65,60,55,50};int length = sizeof(rm)/sizeof(int);int i;cout<<"归并排序：\n原序列：";for(i = 0 ;i <length;i++)cout<<rm[i]<<" ";MergeSort(rm,0,length-1);cout<<"\n排序后序列：";for(i = 0 ;i <length;i++)cout<<rm[i]<<" ";for(i = 0 ; i < 4; i++)cout<<"\n第"<<i+1<<"次归并,比较次数："<<mergeSortCompareCount[i]<<"次，移动次数："<<mergeSortMoveCount[i]<<"次";cout<<"\n利用归并排序比较："<<compareCount[0]<<"次,移动："<<moveCount[0]<<"次"<<endl;cout<<"*****************************************************"<<endl;cout<<"快速排序：\n原序列：";for(i = 0 ;i <length;i++)cout<<rq[i]<<" ";QuickSort(rq,0,length-1);cout<<"\n排序后序列：";for(i = 0 ;i <length;i++)cout<<rq[i]<<" ";for(i = 0 ; i < 12; i++)cout<<"\n第"<<i+1<<"次划分,比较次数："<<quickSortCompareCount[i]<<"次，移动次数："<<quickSortMoveCount[i]<<"次";cout<<"\n利用快速排序比较："<<compareCount[1]<<"次,移动："<<moveCount[1]<<"次"<<endl;return 0;}void MergeSort(int r[],int s,int t){if(s==t)return;else{int m,r1[1000];m = (s+t)/2;MergeSort(r,s,m);MergeSort(r,m+1,t);/***********将用于统计每次合并产生比较次数与移动次数的临时变量置为0*************/tempCompareCount = 0;tempMoveCount = 0;Merge(r,r1,s,m,t);//将r1中归并好的数据移动到r中，产生移动次数为t – s + 1。for(int i = s; i <= t;i++)r[i] = r1[i];moveCount[0] += t – s + 1;tempMoveCount += t – s + 1;/**********统计第一次合并产生的比较次数与移动次数********************/if(t-s==1){mergeSortCompareCount[0] += tempCompareCount;mergeSortMoveCount[0] += tempMoveCount;}/**********统计第二次合并产生的比较次数与移动次数********************/if(t-s==2||t-s==3){mergeSortCompareCount[1] += tempCompareCount;mergeSortMoveCount[1] += tempMoveCount;}/**********统计第三次合并产生的比较次数与移动次数********************/if(t-s==5||t-s==6){mergeSortCompareCount[2] += tempCompareCount;mergeSortMoveCount[2] += tempMoveCount;}/**********统计第四次合并产生的比较次数与移动次数********************/if(t-s==12){mergeSortCompareCount[3] += tempCompareCount;mergeSortMoveCount[3] += tempMoveCount;}}}void Merge(int r[],int r1[],int s,int m,int t){int i = s,j = m+1,k = s;while(i<=m&&j<=t){//产生比较,比较计数器加1compareCount[0]++;tempCompareCount++;if(r[i]<=r[j])r1[k++] = r[i++];elser1[k++] = r[j++];}while(i<=m)r1[k++] = r[i++];while(j<=t)r1[k++] = r[j++];//将r分割的数合并的数移动到r1中，参数移动次数为t – s + 1，记录下moveCount[0] += t – s + 1;tempMoveCount += t – s + 1;}void QuickSort(int r[],int first,int end){int pivot;if(first<end){pivot = Partition(r,first,end);QuickSort(r,first,pivot-1);QuickSort(r,pivot+1,end);}}int Partition(int r[],int first,int end){int i = first,j = end;tempCompareCount = 0;tempMoveCount = 0;while(i<j){while(i < j &&r[i]<=r[j]){j–;//快速排序产生比较，比较次数+1compareCount[1]++;tempCompareCount++;}if(i<j){//快速排序产生比较，，比较次数+1，并且产生交换，移动次数+3compareCount[1]++;tempCompareCount++;tempMoveCount+=3;moveCount[1]+=3;int temp = r[i];r[i] = r[j];r[j] = temp;i++;}while(i < j &&r[i]<=r[j]){//快速排序产生比较，比较次数+1compareCount[1]++;tempCompareCount++;i++;}if(i<j){//快速排序产生比较，比较次数+1，并且产生交换，移动次数+3compareCount[1]++;tempCompareCount++;tempMoveCount+=3;moveCount[1]+=3;int temp = r[i];r[i] = r[j];r[j] = temp;j–;}}//cout<<"\n["<<index<<"] = "<<tempCompareCount<<"—-"<<tempMoveCount;quickSortCompareCount[index] = tempCompareCount;quickSortMoveCount[index] = tempMoveCount;index++;return i;}实验结果：天不负;卧薪尝胆，三千越甲可吞吴。
