首页 / 算法 / 经典算法系列一-快速排序

经典算法系列一-快速排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了经典算法系列一-快速排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1134字，纯文字阅读大概需要2分钟。

内容图文

写一个系列的经典算法，共同学习！

1.快速排序

基本思想：

1.先从数列中取出一个数作为基准数。

2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步，直到各区间只有一个数。

在网上看到一篇博客，把快速排序命名为 挖坑填数+分治法，感觉很有道理，所以等会程序就按这两部来写。

先说说挖坑填数的思想：

1.i=L;j=R; 将基数挖出形成第一个坑a[i].

2.j--由后向前找出比它的小的数，找到后挖出此数填前一个坑a[i].

3.i++由前向后找出比它大的数，找到后挖出此数填前一个坑a[j].

4.重复2，3步骤直到i==j,将基数填入a[i]中。

代码实现

 int Adjust(int a[],int i,int j)

{
    int x = a[i];
    while(i<j)
    {
        while(i<j && x <= a[j])
        j--;
        if(i<j)
        {
               a[i] = a[j];
               i++;
        }          
        while(i<j && x >= a[i])
        i++;
        if(i<j)
        {
               a[j] = a[i];
               j--;       
        }    
    }
    a[i] = x;
    return i;
}

 分治：

 int quick_sort(int a[],int l,int r)

{
    int i;
    if(l < r)
    {
        i = Adjust(a,l,r);
        quick_sort(a,l,i-1);
        quick_sort(a,i+1,r);
    }
}

 这样分两步就把快速排序解决了，挺简单的。当然这样写有点麻烦，可以简单一些：

 int quick(int a[],int l,int r)

{
    int i = l;
    int j = r;
    if(l < r)
    {
        int x = a[i];
        while(i<j)
        {
            while(i<j && x <= a[j])
            j--;
            if(i<j)
            {
                   a[i] = a[j];
                   i++;
            }          
            while(i<j && x >= a[i])
            i++;
            if(i<j)
            {
                   a[j] = a[i];
                   j--;       
            }    
        }
        a[i] = x;
        quick(a,l,i-1);
        quick(a,i+1,r);
    }
}

 

 http://www.cnblogs.com/my-life/category/425361.html

 

原文：http://www.cnblogs.com/liuchengchuxiao/p/4248831.html

内容总结

以上是互联网集市为您收集整理的经典算法系列一-快速排序全部内容，希望文章能够帮你解决经典算法系列一-快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1333110.html

来源：【匿名】