快速排序

一个简单易理解的快速排序实现。
//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);
}

posted on 2012-03-05 08:52 DjvuLee 阅读(142) 评论(0)  编辑 收藏 引用 所属分类: 排序


只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2013年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

统计

常用链接

留言簿

随笔分类(13)

随笔档案(19)

文章分类(2)

文章档案(1)

搜索

最新评论

评论排行榜