快速排序:
首先,应理解迭代的思想,明白什么是基准?例如数学中的F(X) = F(X-1) + 2X,对于该式求解,须知道X的取值范围,以及另一个已知的F(a)(a为常数的值),由此可以解出所有的F(X),体现了迭代的思想。而这个F(a),也就是基准。
回归快排,对于数组a[],选取任一项为基准,进行大小比较。
具体步骤:
1. 定义变量 i = 0,j = N-1
2. 令a[0] = base(基准),基准在每轮排序的时候当然是不能改的。
3. 对所有数据,由两端到中间的比较顺序,依与基准大小关系,分放于右左两侧,右端a[j--]操作,直到a[j] < base,此时进行
a[i]覆盖,即a[i]=a[j],此时该值虽然两份保存,但a[j]之后会被覆盖,而数组貌似缺少的一个数据,即为基准base。
4. 经第3步后,此时a[i] < base,进行左端a[++i]操作,直到a[i] > base,此时进行a[j]覆盖,即a[j] = a[i],同理此时a[i]两份
保存,等着下一次的覆盖,这也就是为什么一会从左端一会儿从右端开始的原因,因为要覆盖多的保存。
5. 以上过程只完成了一趟排序,重复3,4步,直到i = j,快排才结束。
源代码:
阅读(1176) | 评论(0) | 转发(0) |