//Quick Sort program in C++//用类实现快速排序。#include <iostream>using namespace std;//比较类。class intCompare{public: static bool it(int x,int y) {  return x<y; } static bool eq(int x,int y) {  return x==y; } static bool gt(int x,int y) {  return x>y; }}; template<class Record,class Compare>class Sorter{protected: static void swap(Record Array[],int i,int j);public: void printArray(Record Array[],int n);}; template<class Record,class Compare> void Sorter<Record,Compare>::swap(Record Array[],int i,int j){ Record temp=Array[i]; Array[i]=Array[j]; Array[j]=temp;} template <class Record,class Compare>void Sorter<Record,Compare>::printArray(Record Array[],int n){ cout<<"Print all element!"; for(int i=0;i<n;i++)  cout<<Array[i]<<"  "; cout<<endl;} template<class Record,class Compare>class QuickSort:public Sorter<Record,Compare>{private: int selectPivot(int left,int right); int partition(Record Array[],int left,int right,Record &item);public: void Sort(Record Array[],int left,int right);};//选择轴值。template<class Record,class Compare>int QuickSort<Record,Compare>::selectPivot(int left,int right){ return (left+right)/2;}//分割函数。template<class Record,class Compare>int QuickSort<Record,Compare>::partition(Record Array[],int left,int right,Record &item){ do{                     //一直移动标记知道相等或反过。  while(Compare::it(Array[++left],item));        while((right!=0)&&Compare::gt(Array[--right],item));  swap(Array,left,right);        //大于轴值在右小于轴值在左。 }while(left<right); swap(Array,left,right);   //记得最后反转换。 return left;}//快速排序的实现template<class Record,class Compare>void QuickSort<Record,Compare>::Sort(Record Array[],int left,int right){ if(left>=right)  return; int pivotIndex=selectPivot(left,right); swap(Array,pivotIndex,right); int k=partition(Array,left-1,right,Array[right]); swap(Array,k,right); Sort(Array,left,k-1);        //用递归实现。 Sort(Array,k+1,right);} int main(){ int n; QuickSort<int,intCompare> A; cout<<"Enter sum of sorted number: "; cin>>n; int *Array=new int[n]; cout<<"Enter the number: "<<endl; for(int i=0;i<n;i++)  cin>>Array[i]; A.Sort(Array,0,n-1); A.printArray(Array,n); return 0;} 这个是我用字典形式的实现了快速排序算法。在这个字典序中加进一些东西。就可以变成一些复杂的排序。像图书管图书排序或其他的。这里我只写了写简单的形式。如果同学要做什么字典课程设计就加一个数据类，比较类也还要更描述的更仔细。

评论