qinck_sort_classic.cpp

算法导论上的快速排序经典算法实现。用动态数组vector实现

// Qinck_Sort_Classic.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <iostream>
#include <vector>
using namespace::std;
using std::vector;


void Print_v(vector<int> &v)
{
	vector<int>::iterator it;
    for (it=v.begin();it!=v.end();it++)
	{
		cout<<*it;
		cout<<"   ";
	}

    cout<<endl;

	return;
}

int Partition(vector<int> &v,int p,int r)
{
	int i;
	int j;
	int x;
	int temp;
	x=v[r];
	i=p-1;
    for (j=p;j<r;j++)
	{
		if (v[j]<=x)
		{
			i++;
			temp=v[i];
			v[i]=v[j];
			v[j]=temp;

		}
	}
	temp=v[i+1];
	v[i+1]=v[r];
	v[r]=temp;

	return i+1;
}
void Quick_Sort(vector<int> &v,int p,int r)
{
	int q;
	if(p<r){
		q=Partition(v,p,r);

		Quick_Sort(v,p,q-1);
		
		Quick_Sort(v,q+1,r);

	}

}


int _tmain(int argc, _TCHAR* argv[])
{
	clock_t start_;
	clock_t finish_;
	vector<int> v;
	int one;
	int i;
	int j;
	for (i=0;i<=1000;i++)
		for (j=0;j<=100;j++)
		{
			one=rand();
			v.push_back(one);
			cout<<one<<endl;  // 如果需要看具体数值，可以解除屏蔽
		}
             
	
	int len;
	int r;
	int p;
	double  duration;

	len=v.size();
    r=len-1;
	p=0;
    
	start_ = clock();
	Quick_Sort(v,p,r);
	
	Print_v(v);  // 如果需要看具体数值，可以解除屏蔽
	
	finish_=clock();
	duration = (double)(finish_-start_)/CLOCKS_PER_SEC;
    cout<<"The running time is "<<duration;


	system("pause");
	
	
	
	return 0;
}