黑马程序员技术交流社区
标题:
排序之快速排序
[打印本页]
作者:
刘彦麟
时间:
2015-7-25 10:00
标题:
排序之快速排序
在论坛看到很多小伙伴都讲述了排序中的很多种排序，讲的很好也很细，作为一名小菜鸟今天也为大家讲一下排序中的快速排序，大家学习学习，
首先讲一下快速排序的策略，快速排序的策略就是分治策略，也就是分而治之！那什么叫做分治策略呢？
简单的一句话就是将一个复杂的大问题分解成n个与大问题类似结构的小问题，然后解决小问题，最后在返回大问题，大家都知道的··大事化小，小事化无嘛···小问题就是很好解决的！
快速排序呢，就是把比一个数字大的数字放在这个数字的后面，把比这个数字小的数字放在前面，这个数字呢可以是第一个，也可以是最后一个，随便！
那么下面给通过实际例子给大家讲解快速排序
比如数组 10个数字· 我们取第一个数字！
5 3 8 1 4 6 7 2 9 0 我们把5大的数字放在后面，把5小的数字放在前面
3 1 4 2 0 5 9 7 6 8 大家可以看到5之前的数字都比5小，5之后的数字都比5大，那么这是怎么交换
的呢？为什么变换完了成了这个样子？在一会的代码中为大家讲解。
这个时候细心的同学就会发现，比5小的数字虽然都在前面，但是无序，比
5大虽然都在后面，但是也无序，这是为什么呢？这是因为我们只对这个大问题进行了一次分治，发现问题还不够小，所以还要分治，所以 就要用到递归
代码原理：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
下面是代码，有注释··大家看看···
void sort(int *a, int left, int right)
{
if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];
while(i < j) /*控制在当组内寻找一遍*/
{
while(i < j && key <= a[j])
/*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
{
j--;/*向前寻找*/
}
a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
a[left]，那么就是给key）*/
while(i < j && key >= a[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
至于时间复杂度不稳定，平均是log2n吧···
那么快速排序就到此为止了，代码可能会看不懂，没关系，懂了原理，自己慢慢写出来，才会真正的理解。
最后呢，在说一嘴，排序呢大家都会，可是写程序还有些排序的程序，所以很麻烦，所以教大家一个排序的简单方法
就是用到 sort（），函数。他是定义在#include<algorithm>这个头文件中哦
a[10]=10个数，随便写
sort（a）；//就已经排序成功，就这么简单
输出的话就升序，还有降序，大家有兴趣可以自己研究研究
谢谢大家···有错误欢迎指出····纯手打··谢谢大家！
作者:
刘彦麟
时间:
2015-7-25 10:18
啊···没人看· ···
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2