参考:
快速排序
堆排序
各类排序
#include <iostream> #include <vector> #include <time.h> #include <cstdlib> //......自行添加其他必要的库 using namespace std; #define num 100 //各种排序方法的函数声明,有兴趣选做注释部分排序算法 //template<class T> //void BubbleSort(vector<T> &x);//冒泡排序 //template<class T> //void SelectSort(vector<T> &x);//选择排序 //template<class T> //void InsertSort(vector<T> &x);//插入排序 //template<class T> //void ShellSort(vector<T> &x);//希尔排序 //template<class T> //void CountedSort(vector<T> &x);//计数排序 //template<class T> //void RadixSort(vector<T> &x);//基数排序 //template<class T> //void BSTSort(vector<T> &x);//选做：二叉查找树排序 template<class T> void QuickSort(vector<T> &x, int first, int end);//快速排序 template<class T> void HeapSort(vector<T> &x);//堆排序 template<class T> void Heapfy(vector<T> &x, int first, int end); //堆调整 template<class T> void Display(vector<T> &x); template<class T> void ResetData(vector<T> &x,vector<T> &y);//使用y重置x //......自行添加其他必要的函数声明 int main() {clock_t start,finish;double totaltime;vector<int> a(num+1),b(num+1);int i;srand(time(0));//随机数种子初始化for(i=1;i<=num;i++){ a[i]=rand()%10000+1; //随机生成1-10000内的数值作为排序对象b[i]=a[i];}//排序前显示数据cout<<"排序前"<<endl;Display(a);//冒泡排序// BubbleSort(a);//cout<<"冒泡排序后"<<endl;//Display(a);//选择排序// ResetData(a,b);// SelectSort(a);// cout<<"选择排序后"<<endl;// Display(a);//插入排序// ResetData(a,b);// InsertSort(a);// cout<<"插入排序后"<<endl;// Display(a);//希尔排序// ResetData(a,b);// ShellSort(a);// cout<<"希尔排序后"<<endl;// Display(a);//计数排序// ResetData(a,b);// CountedSort(a);// cout<<"计数排序后"<<endl;// Display(a);//基数排序// ResetData(a,b);// RadixSort(a);// cout<<"基数排序后"<<endl;// Display(a);//快速排序 ResetData(a,b);start = clock();QuickSort(a,0,num);finish = clock();cout<< endl << "快速排序后"<<endl;totaltime = (double)(finish-start)/CLOCKS_PER_SEC;cout << "time: " << totaltime << "s" << endl;Display(a);//堆排序 ResetData(a,b);start = clock();HeapSort(a);finish = clock();cout<< endl << "堆排序后"<<endl;totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout << "time: " << totaltime << "s" << endl;Display(a);cout << endl; }template<class T> void Display(vector<T> &x) {for(int i=1;i<=num;i++){ cout<<x[i]<<" ";if(i%15==0) cout<<endl;} }template<class T> void ResetData(vector<T> &x,vector<T> &y)//使用y重置x {for(int i=1;i<=num;i++){x[i]=y[i];} }template<class T> void QuickSort(vector<T> &x, int first, int end){if( first<end ){int i=first;int j=end;T t=x[i];while( i<j ){while( i<j && x[j] >= t ){j--;}if( i<j ){x[i++] = x[j];}while( i<j && x[i] <= t){i++;}if( i<j ){x[j--] = x[i];}}x[i] = t;QuickSort(x, first, i-1);QuickSort(x, i+1, end);} }template<class T> void Heapfy(vector<T> &x, int p, int len){int father = p;int child = 2*father;while( child<=len ){if( child+1 <= len && x[child] < x[child+1] ){child++;}if( x[child] > x[father] ){int t=x[child];x[child] = x[father];x[father] = t;father = child;child = 2*father;}else break;} }template<class T> void HeapSort(vector<T> &x){for(int i=num/2; i>=1; i--){ //构造最大堆，但子结点左右孩子大小不分 Heapfy(x, i, num);}for(int i=num; i>1; i--){ //构造最小堆，使得最左孩子小于右孩子int t=x[1];x[1] = x[i];x[i] = t;Heapfy(x,1,i-1);} }