设为首页 加入收藏

TOP

问题解决最佳方法:排序(二)
2013-05-14 09:26:01 来源: 作者: 【 】 浏览:637
Tags:问题 解决 最佳 方法 排序


    结果如下:
    第五次
    0 1 2 3 4 5 6
    3 4 5 9 2 1 7继续使用 pivot = 5 与 a[high] 进行对比
    同样进行交换,结果如下:
    第六次
    0 1 2 3 4 5 6
    3 4 1 9 2 5 7继续使用 pivot = 5 与 a[low] 进行对比
    结果如下:(low++)
    第七次
    0 1 2 3 4 5 6
    3 4 1 9 2 5 7继续使用 pivot = 5 与 a[low] 进行对比
    结果如下:
    第八次
    0 1 2 3 4 5 6
    3 4 1 5 2 9 7继续使用 pivot = 5 与 a[high] 进行对比
    结果如下:(high--)
    第九次
    0 1 2 3 4 5 6
    3 4 1 5 2 9 7继续使用 pivot = 5 与 a[high] 进行对比
    结果如下:(最终结果low == high,橙色表示)
    第九次
    0 1 2 3 4 5 6
    3 4 1 2 5 9 7最后由于 low++  所以 low == high
    到这里,已经利用 基准数pivot = 5 把这个数列分为了两部分(5 的左边都是小于它的,右边都是大于它的)
    然后递归。用同样的方法,对分割出来的两部分用"基准数"继续进行分割
    快排函数代码:
    [cpp]
    //快排函数
    void sort(int *s, int low, int high)
    {
    int    pivot;
    //if语句的判断是结束递归的简单情景,不能缺
    if (low < high)
    {
    // partition 函数就是利用基准数进行分割的功能函数,这个函数是重点
    pivot = partition(s, low, high);
    sort(s, pivot + 1, high);
    sort(s, low, pivot - 1);
    }
    }
    什么是递归的简单情景?可以看看这里
    partition 函数代码:
    [cpp]
    //这个函数就是上面演示的代码实现
    int partition(int *s, int low, int high)
    {
    int    pivot;
    pivot = s[low];
    while (low < high)
    {
    while (low < high && pivot <= s[high])
    {
    high--;
    } 
    swap(&s[low], &s[high]);
    while (low < high && pivot >= s[low])
    {
    low++;
    }
    swap(&s[high], &s[low]);
    }
    return  low;
    }

      

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇插入排序的主要思想 下一篇认识指针保存变量地址

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: