快速排序算法的c++实现
很早以前看过快排算法觉得自己掌握了,,课今天用的时候发现老出错,认真想想发现自己一直搞错了。。。
下面先说一下我的想法:
首先,快排的思想就是
- 从数列中挑出一个元素,称为 "基准"(pivot),
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
那么这里需要考虑的就是如何进行分区,这个是最重要的,先来看看我的分区的实现:(这里的provit我就不用随机数来实现了,直接选第一个)
int partition(int array[], int begin, int end) {
int index = begin;
int proviet = array[begin];
swap(array[index], array[end]);//将provit换到最后
for(int i = begin; i != end; i++) {//将小于provit的元素放到左边,大的放到右边
if (array[i] < proviet)
swap(array[index++], array[i]);
}
swap(array[index], array[end]); return index;
}
首先,将provit移到数组的最后一位,这样在数组分区的时候就不会影响到provit,也就是这句
swap(array[index], array[end]);
假设我们要分区的数组是6 7 4 3 56 5, 那么到现在数组应该变成这样了
然后,就要将除 provit 意外的全部元素进行遍历,此时 index 是 0,i 也从 0 开始。那么因为第一个 5 < 6,所以变成这样,
到第三步,因为7>6, 所以 index 没变,而 i 自增,即这样,那么此时因为 4 < 6, 所以将 4 和 7 交换,变成这样。
下面的一招这个原理即可。那么,到 for 循环完成后,数组变成如下:,这时,因为 index 位的数大于等于 privot, 所以将他们交换,最后达到的效果就是大的全在右边,小的全在左边。
然后是 quickSort()的内容:
void quickSort(int array[], int begin, int end) {
if (begin >= end)
return;
int position = partition(array, begin, end);
quickSort(array, begin, position - 1);
quickSort(array, position + 1, end);
}
这里就是用递归的方法将数列分段进行大小分区,这个应该不难理解。因为每一段内部的元素的都比他后面段的所有元素都小,那么排出来的就应该是一个有序列了。
对于provit的选择,其实没有太多的要求,只是说你用随机数来产生的话更可能得到一个好的 provit 使得分区更好得到更好的速度。因为使用随机数法使得输入数据的次序对算法不产生影响。只有在随机数产生器给出了一个很不巧的排列时,随机化算法的最坏情况性态才会出现。事实上可以证明几乎所有的排列都可使快速排序接近平均情况性态,只有非常少的几个排列才会导致算法的近最坏情况性态。所以一般情况下采用随机数法。
如果你想用随机数来实现,可以看看这个http://code.wikia.com/wiki/Random_number
最新文章
- MVC中的默认Model绑定者DefaultModelBinder
- ios蓝牙开发(三)ios连接外设的代码实现:手机app去读写蓝牙设备。
- asp.net json 与xml 的基础事例
- redis async client 与自有框架集成
- easyui datagrid 编辑器绑定事件
- C#--判断当前是否是移动设备和设备的型号
- 如何设置 Windows 开机启动项
- 【LeetCode 99】Recover Binary Search Tree
- Visual Studio 2012中使用Zen Coding,写html的神器!
- js原型对象,每个new出来的新对象都有独立的原型对象__proto__
- 使用JavaScript制作页面效果3
- 日志组件slf4j介绍及配置详解
- ios 汽车品牌展示案例
- 【BZOJ3514】 Codechef MARCH14 GERALD07加强版
- python简单实现目录对比
- HihoCoder - 1051:补提交卡
- Microsoft Dynamics CRM 2011 安装完全教程
- 132.1.001 Union-Find | 并查集
- [Java] Design Pattern:Code Shape - manage your code shape
- Centos6.7在VMware7.0上的hgfs文件共享
热门文章
- 【poj2096】Collecting Bugs 期望dp
- 【bzoj3297】[USACO2011 Open]forgot STL+dp
- hdu 1281 棋盘游戏 (二分匹配)
- JS变量对象详解
- 2017中国大学生程序设计竞赛-哈尔滨站 A - Palindrome
- [BZOJ5303] [HAOI2018] 反色游戏
- 剑桥offer系列(1~10)
- STL之五:set/multiset用法详解
- Codeforces Round #329 (Div. 2)A 字符串处理
- [POI2007] ZAP-Queries (莫比乌斯反演)