liyuxia713

蹒跚前行者

常用链接

统计

Algorithms

C++

最新评论

基本排序算法及分析（四）：快速排序

快速排序:
 1/*----------------------------------------------------------------------------------------------
 2Quick_sort.h
 3快速排序:确定一个枢纽元，一次遍历后将数组划分成两个部分，第一部分均比枢纽元小
 4         第二部分都比枢纽元大，然后对这两个数组进行快速排序，是一种递归的方法
 5平均运行时间O(Nlog(N)),最坏运行时间O(N^2)
 6最坏情形：对于预排序的序列。
 7对与枢纽元相等的元素处理：
 8    i,j都停止：会比较相等元素，但是可以划分成长度相当的两个子数组
 9    i,j都不停止，不会比较相等元素，但是可能产生长度不平衡的两个子数组(与枢纽元相等的元素较多时)
10枢纽元的选取：
111. 选取第一个元素做枢纽元：对于（部分）预排序的序列运行时间O(N^2)
122. 随机生成枢纽元：能避免上述问题，但是产生枢纽元的代价高
133. 三数中值分割法：选取左端，右端，中间位置三个元素的中值
14----------------------------------------------------------------------------------------------*/
15#ifndef QUICK_SORT_H
16#define QUICK_SORT_H
17
18#include "typedef.h" /* typedef int T 待排序的元素类型只要在这个文件中控制即可. */
19#include "swap.h" /*交换两个元素值*/
20
21/* 选取第一个元素做枢纽元的情形----返回枢纽元位置*/
22int Quick_sort_divide(T*a, int begin, int end)
23{
24    T key = a[begin];
25
26    while(begin < end)
27    {
28        while(begin < end && a[end] >= key) --end;
29            a[begin] = a[end]; //不能--end，下面循环还要给现在的end位置赋值呢！         
30            //swap(a[begin],a[end]);
31        while(begin < end && a[begin] <= key) ++begin;
32            a[end] = a[begin];
33            //swap(a[begin],a[end]);
34    }
35    a[begin] = key;
36    
37    return begin;
38}
39
40/*三数中值割分法----选取枢纽元*/
41const int& median3(T*a, int begin, int end)
42{
43    int mid = (begin + end)/2;
44    //将三个位置的元素，按顺序摆好，一会儿begin，end位置的元素就无需参加比较
45    if(a[mid] < a[begin]) swap(a[mid],a[begin]);
46    if(a[end] < a[begin]) swap(a[end],a[begin]);
47    if(a[mid] > a[end]) swap(a[mid],a[end]);
48    
49    swap(a[mid],a[end-1]); //将枢纽元放到倒数第二个位置
50    return a[end-1];
51}
52
53
54/*三数中值分割法----分割:返回枢纽元位置*/
55int Quick_sort_divide_3v(T*a, int begin,int end)
56{
57    T key = median3(a,begin,end);
58    int tag = end - 1;
59    begin = begin + 1; //选取枢纽元时原begin位置的元素已设置成小于key的
60    end = end - 2; //原end位置值已设置成大于key的，end-1位置为key，都不用考虑
61    while(begin < end)
62    {
63        while(a[begin] < key) ++begin;
64        while(a[end] > key) --end;
65        if(begin < end) swap(a[begin],a[end]);
66    }
67    swap(a[begin],a[tag]);
68    return begin;
69}
70
71/*一次分割*/
72void Quick_sort_step(T*a, int begin, int end)
73{    
74    if(begin < end)
75    {
76        int k = Quick_sort_divide_3v(a,begin,end); //三数中值割分法
77        //int k = Quick_sort_divide(a,begin,end); //选第一个元素做枢纽元
78        Quick_sort_step(a,begin,k-1);
79        Quick_sort_step(a,k+1,end);
80    }
81}
82/*快速排序*/
83void Quick_sort(T* a, int n)
84{
85    //if(n > 10) 当元素个数少时不必用快速插入法    
86        Quick_sort_step(a,0,n-1);
87    //else Insertion_sort(a,n);
88}
89
90#endif

 
  

posted on 2009-04-22 16:56 幸运草 阅读(2818) 评论(8)  编辑 收藏 引用 所属分类: Algorithms

评论

# re: 基本排序算法及分析（四）：快速排序 2009-04-28 21:27 shongbee2

哈哈，终于弄清楚了。谢谢您。。以后多交流哈。呵呵  回复  更多评论   

# re: 基本排序算法及分析（四）：快速排序 2009-10-10 15:30 Linsea

我想问下那个logN对数都没有底数,那个底数是多少?2吗?
我看严蔚敏的书上有的地方有底数2,有的地方没有,是怎么回事,这个问题困扰我好久了,望博主对回答,谢谢!  回复  更多评论   

# re: 基本排序算法及分析（四）：快速排序 2009-10-17 10:19 幸运草

@Linsea
是以2为底的logN，我想有的时候没写是默认是2吧，因为二叉树一般涉及的都是以2为底的指数函数，反过来也是以2为底的对数函数。

具体的解释我放在原日志最下端了，因为我只能以图片的格式插入数学公式，所以就没有办法放在回复里了，你看一下，有问题再联系我  回复  更多评论   

# re: 基本排序算法及分析（四）：快速排序 2012-06-28 00:58 我是大熊

最近也在看快排，希望一起讨论
http://php.oil58.com/  回复  更多评论   

# re: 基本排序算法及分析（四）：快速排序 2012-06-28 11:31 liyuxia713

@我是大熊

去贵页面浏览了下，文笔风格比较吸引人，但页面排版看着有些乱  回复  更多评论   

# re: 基本排序算法及分析（四）：快速排序 2012-07-04 03:15 我是大熊

@liyuxia713
谢谢！！可能是浏览器兼容性的关系！不过在改进了!
  回复  更多评论   

# re: 基本排序算法及分析（四）：快速排序 2012-07-04 03:39 我是大熊

我写的快排，简单的理解，没你的这么深。可以的话，帮我看看！
http://php.oil58.com/?p=206  回复  更多评论   

# re: 基本排序算法及分析（四）：快速排序 2012-07-04 03:41 我是大熊

不支持这个链接，不好意思
http://php.oil58.com/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-c/  回复  更多评论   


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