【排序】快排思想以及例子

思想

使用分治法来处理数据

例题

19 97 09 17 01 08
首先确定一个pivot 一般是首位，把比p小的放p的左边，比p大的放p的右边。L是左指 R是右指
首轮排序

p 19
__ 97 09 17 01 08
L R
首先应从R开始判断 08<19
08替换到p所在位置，R移动
p 19
08 97 09 17 01 __
L R
接着是L指移动，97>19,97替换到R
08 __ 09 17 01 97
L R
接着是R指移动，01<19 01替换到L
08 01 09 17 __ 97
L R
接着是L指移动，09<19 序列不变
08 01 09 17 __ 97
L R
接着是L指移动，17<19 序列不变
08 01 09 17 __ 97
L R
接着是L指移动，L指R指重合 替换p 19
08 01 09 17 19 97
R
L
首轮排序结束 此时在19的左边是小于他的序列 右边是大于他的序列，再分别对左右序列做快排
首先从R指开始判断17>08 位置不动
p 08
__ 01 09 17
L R
R指指向下一位
p 08
__ 01 09 17
L R
09>08 位置不动
R指指向下一位
__ 01 09 17
L R
01>08 替换到L
01 __ 09 17
L R
L指指向下一位
01 __ 09 17
R
L
R,L重合 放入p 08
01 08 09 17
此时序列，右序列只有一个数无序再排序
01 08 09 17 19 97 有序