一个简单易理解的快速排序实现。
//By:DjvuLee@2012--3-04
//快速排序,递归形式
//时间复杂度:O(nlgn);空间复杂度O(lgn)
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;
#define N 100
void qsort(int *a, int low, int high);
int main()
{
ifstream fin("input.txt");
int n;
int a[N];
fin>>n;
for(int i=0;i<n;i++)
fin>>a[i];
qsort(a,0,n-1);
//output
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
void qsort(int *a, int low, int high)
{
if(low>=high)
return ;
int i=low,j=high,type=1;
int key=a[i];
while(i<j){
if(type==1)//自高位向低位
if(a[j]<key)
{
swap(a[i],a[j]);
type=2;
}
else
j--;
else//自低位向高位
if(a[i]>key)
{
swap(a[i], a[j]);
type=1;
}
else
i++;
}//end while
qsort(a,low,j-1);
qsort(a,i+1,high);
}