马赛克007欢迎你

htt://shexinwei.blogbus.com

http://www.cppblog.com/shexinwei

感谢大家的支持

快速排序(C++)

  1 //版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
  2 //http://shexinwei.blogbus.com/logs/74827291.html
  3 
  4 
  5 /*
  6 
  7 Subject:      Quick sort
  8 
  9 Author:       shexinwei
 10 
 11 School:       xidian university
 12 
 13 Date:         2010-09-12
 14 
 15 Laguage:      C++
 16 
 17 IDE | Tool:   GCC
 18 
 19 Version:      1.0
 20 
 21 Modify Time:  2010-09-12
 22 
 23 */    
 24 
 25 #include <iostream>
 26 
 27 using namespace std;
 28 
 29 int sort(int begin,int end,int data[],int n);
 30 
 31 int recurs(int begin,int end,int data[],int n);
 32 
 33 int print(int data[],int n);
 34 
 35 int main()
 36 
 37 {
 38 
 39     int data[] = {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
 40 
 41     //打印初始序列
 42 
 43     print(data,20);
 44 
 45     //递归排序
 46 
 47     recurs(0,19,data,20);
 48 
 49     //打印最终序列    
 50 
 51     print(data,20);
 52 
 53     cout<<endl;
 54 
 55         return 1;
 56 
 57 }
 58 
 59  
 60 
 61 //打印序列
 62 
 63 int print(int data[],int n)
 64 
 65 {
 66 
 67     for(int i = 0;i<n;i++)
 68 
 69         cout<<data[i]<<" ";
 70 
 71     cout<<endl;
 72 
 73     return 1;
 74 
 75 }
 76 
 77  
 78 
 79  
 80 
 81 int sort(int begin,int end,int data[],int n)
 82 
 83 {
 84 
 85     //选择最后一位做初始的中枢
 86 
 87     int pos = end;
 88 
 89     int key  = data[end];
 90 
 91     //索引初始化
 92 
 93     int front = begin;
 94 
 95     int last = end;
 96 
 97     for(;front != last;front++)
 98 
 99     { //向后查找
100 
101  
102 
103         if((data[front] < key) || (data[front] == key)) continue;
104 
105         else
106 
107         { //遇到比中枢值大的元素,交换位置,修改pos的值,并开始从后向前找
108 
109             data[pos] = data[front];
110 
111             pos = front;
112 
113             //以下一句可注释,只需要保存中枢的位置,可以不修改值,因中枢值在key中保存,最后找到最终位置后再赋值即可
114 
115             data[pos] = key;     
116 
117             //输出改变一次后的序列
118 
119             print(data,n);
120 
121             for(;front != last;last--)
122 
123             {//从后向前查找
124 
125                 if((data[last] > key)||(data[last] == key)) continue;
126 
127                 else
128 
129                 { //遇到比中枢值小的元素,交换位置,修改pos值,并重新开始从前向后查找
130 
131                    data[pos] = data[last];
132 
133                    pos = last;
134 
135                  //以下一句可注释,只需要保存中枢的位置,可以不修改值,因中枢值在key中保存,最后找到最终位置后再赋值即可
136 
137                        data[pos] = key;
138 
139                  //打印修改以后的序列
140 
141                    print(data,n); 
142 
143                  //重新开始从前向后查找
144 
145                    break;
146 
147                 }
148 
149             }
150 
151             
152 
153         }
154 
155         //如果从后向前已经使得front==last,那么一趟分割完毕
156 
157         if(front == last) break;
158 
159     }
160 
161     data[pos] = key;
162 
163     return pos;
164 
165 }
166 
167 int recurs(int begin,int end,int data[],int n)
168 
169 {
170 
171     //递归出口
172 
173     if((begin == end) || (begin > end)) return 1;
174 
175     else
176 
177     {
178 
179     //做分割
180 
181     int index = sort(begin,end,data,n);
182 
183     //前一部分递归
184 
185     recurs(begin,index-1,data,n);
186 
187     //后一部分递归
188 
189     recurs(index+1,end,data,n);
190 
191     }
192 
193 }

posted on 2010-09-12 17:02 马赛克007 阅读(4366) 评论(1)  编辑 收藏 引用

评论

# re: 快速排序(C++)[未登录] 2010-09-14 08:52 111

快速排序!!!???@_@, 好笑  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

公告

QQ:306334649 本博客所发代码皆为作者原创,大家可以随便使用。

常用链接

留言簿(1)

随笔档案

文章分类

我的博客

搜索

最新评论

阅读排行榜

评论排行榜