最新消息:点击查看大S的省钱秘笈

快速排序(QuickSort)算法 C语言实现

编程相关 Slyar 1252浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

下午做题的时候用到了快速排序(QuickSort),只不过这次换成C语言实现。草草写了一个,感觉很乱,改。。。改完还乱。。。继续改。。。最后结果就是如下这个快速排序(QuickSort)算法的C语言实现。

void qsort(int s[], int l, int r)
{
    int i, j, x;
    if (l < r)
    {
        i = l;
        j = r;
        x = s[i];
        while (i < j)
        {
            while(i < j && s[j] > x) j--; /* 从右向左找第一个小于x的数 */
            if(i < j) s[i++] = s[j];
            while(i < j && s[i] < x) i++; /* 从左向右找第一个大于x的数 */
            if(i < j) s[j--] = s[i];
        }
        s[i] = x;
        qsort(s, l, i-1); /* 递归调用 */
        qsort(s, i+1, r);
    }
}

我的这个算法实现是每次从数组头部取数字作为基准,看起来好理解一些,呵呵~我是这么认为的。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

快速排序(QuickSort)的最坏时间复杂度应为0(n2),最好时间复杂度为O(nlgn),平均时间复杂度为O(nlgn)。快速排序(QuickSort)在系统内部需要一个栈来实现递归。若每次划分较为均匀,则其递归树的高度为O(lgn),故递归后需栈空间为O(lgn)。最坏情况下,递归树的高度为O(n),所需的栈空间为O(n)。

转载请注明:Slyar Home » 快速排序(QuickSort)算法 C语言实现

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (16)

  1. 写得真好,简单易懂,拿来做作业了
    jokul1年前 (2015-10-18)回复
  2. 实在是写的太棒了
    3年前 (2013-07-19)回复
  3. 写的很好,让人很容易理解
    Jordan4年前 (2012-10-27)回复
  4. Slyar : @cjxgm 我逗你的。。。。http://www.slyar.com/blog/stdlib-qsort.html/
    ………………………………………………
    cjxgm5年前 (2011-09-12)回复
  5. @cjxgm 我逗你的。。。。http://www.slyar.com/blog/stdlib-qsort.html/
    Slyar5年前 (2011-09-10)回复
  6. @Slyar Linux 里可以看 man qsort 不然就看这个吧: https://www.chemie.fu-berlin.de/chemnet/use/info/libc/libc_15.html
    cjxgm5年前 (2011-09-10)回复
  7. @cjxgm 哦?那是什么啊,怎么用啊?
    Slyar5年前 (2011-09-09)回复
  8. C 语言里也有一个内置的快排,叫 qsort,在 stdlib.h 里
    cjxgm5年前 (2011-09-09)回复
  9. 我觉得代码还可以写得更好些
    Max6年前 (2011-02-09)回复
  10. 谢谢slyar, 从这儿学到很多东西呢
    普兒7年前 (2009-11-16)回复
  11. 厉害,想了一下午,还没完全弄明白。。。。菜啊
    ljt7年前 (2009-11-09)回复
  12. 嗯,我只能说你写的非常好,很棒!
    闲人8年前 (2009-02-11)回复
  13. 有点意思。。。博客很有技术含量。。。支持博主
    推背图8年前 (2008-10-12)回复
  14. STL里面有一个算法叫做sort(),使用的是随机化的快速排序,不存在算法效率退化的问题。 int a[5] = {1,3,6,2,5}; sort(a, a + 5); 这时a就是升序排列的了。
    felix0218年前 (2008-10-12)回复
    • 恩,这个我有听说。
      Slyar8年前 (2008-10-12)回复