学步园

#include<iostream>
#include<time.h>
#include<vector>
using namespace std;
//template<typename T>
template<typename T>
int partition(vector<T> &vec,int left,int right);
template<typename T>
void quicksort(vector<T> &vec,int left,int right);
int main()
{
 int num;
 clock_t start,finish;double duration;
 cout<<"please input the number of vector:";
 cin>>num;
 vector<int> vec(num);
 srand(time(0));
 for(vector<int>::size_type x=0;x!=vec.size();x++) 
  vec[x]=rand()%100;
 cout<<"the vector is:";
 for(vector<int>::size_type x=0;x!=vec.size();x++)
  cout<<vec[x]<<" ";cout<<endl;

 start=clock();
 quicksort(vec,0,vec.size()-1);
 finish = clock();
    //duration = (double)(finish - start) / CLOCKS_PER_SEC;
 duration = finish-start;
 cout<<"Time to do quicksort of"<<num<<" numbers is "<<duration<<" milliseconds."<<endl;

 cout<<"after quicksort,the vector is:"; 
 for(vector<int>::size_type x=0;x!=vec.size();x++)
  cout<<vec[x]<<" ";cout<<endl;
 return 0;
}
template<typename T>
int partition(vector<T> &vec,int left,int right)
{
 T pivotkey=vec[left];
 while(left<right){
  while(left<right&&vec[right]>=pivotkey) right--;
  vec[left]=vec[right];
  while(left<right&&vec[left]<=pivotkey) left++;
  vec[right]=vec[left];
 }
 vec[left]=pivotkey;
 return left;
}
template<typename T>
void quicksort(vector<T> &vec,int left,int right)
{
 if(left<right){
  int pivotloc=partition(vec,left,right);
  quicksort(vec,left,pivotloc-1);
  quicksort(vec,pivotloc+1,right);
 }
}

一写才发现自己又是好多地方忘记了，就一个检验时间花费的东西原来都多次用到的，但真写的时候就给忘了，还得搬出msdn copy。

partition上课讲的比较多，写着比较顺当，vector还是搬出primer才用上的，更别提vector的高级用法了