啊哈磊_编程从这里起步

标题: 如果你实在看不懂快速排序 [打印本页]

---

作者: rosynirvana    时间: 2014-10-11 02:46
标题: 如果你实在看不懂快速排序

1. #include <stdio.h>
   
2. 
   
3. int ary[10], temp_ary[10];
   
4. 
   
5. void easy_qsort(int, int);
   
6. 
   
7. int main()
   
8. {
   
9.         int i;
   
10.         for(i=0; i!=10; ++i)
    
11.                 scanf("%d", &ary[i]);
    
12. 
    
13.         easy_qsort(0, 10);
    
14.         for(i=0; i!=10; ++i)
    
15.                 printf("%d ", ary[i]);
    
16. 
    
17.         return 0;
    
18. }
    
19. 
    
20. void easy_qsort(int begin, int end)
    
21. {
    
22.         int front, back;
    
23.         int pivot;
    
24.         int i;
    
25.         if(begin + 1 >= end)
    
26.                 return;
    
27. 
    
28.         pivot = ary[begin];
    
29. 
    
30.         front = begin;
    
31.         back = end - 1;
    
32. 
    
33.         for(i=begin+1; i!=end; ++i)
    
34.                 if(ary[i] <= pivot)
    
35.                         temp_ary[front++] = ary[i];
    
36.                 else
    
37.                         temp_ary[back--] = ary[i];
    
38.         temp_ary[front] = pivot;
    
39. 
    
40.         for(i=begin; i!=end; ++i)
    
41.                 ary[i] = temp_ary[i];
    
42.         easy_qsort(begin, front);
    
43.         easy_qsort(front+1, end);                 
    
44. }

复制代码

快速排序的流程是
如果待排序的数组长度小于等于1，返回
选择轴点，然后把小于轴点的放在轴点左边，大于轴点的放在轴点右边
对轴点两边的数据进行排序

其中难写的部分在于第二部分，如果是其他部分有问题就回头多看几遍书

用一个辅助数组很容易做到第二部分，例如数据
2 7 3 9 5
选择中间点3作为轴点，那么扫描一遍待排序的数据
2比3小，放在辅助数组的最左边；
7比3大，放在辅助数组的最右边；
……

然后再把数据拷贝回来

这样的快速排序叫做非原位快速排序，需要原始数据2倍的内存空间，另外又要多拷贝一次，但是时间复杂度是不变的

真正想把快速排序实现好其实是非常困难的事情，一般可以考虑用标准库中的qsort

---

作者: kuaile1210    时间: 2014-10-12 10:59
{:soso_e121:}谢谢大神！

---

作者: 超神级    时间: 2015-11-20 19:42
有时候快排只讲一个思想，有时候懂就是懂了，不懂的说了也是不是很懂

---

作者: 超神级    时间: 2015-11-20 20:01
我建议想看明白这个先把二叉树学熟悉，

---

作者: 超神级    时间: 2015-11-20 20:02
至少得写的出先中后三种遍历，因为可以稍微明白啥是递归

---

欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)

Powered by Discuz! X3.2