数据结构之快速排序（重点）

快速排序

算法所需
一个基准点
左边是比其小的数，右边是比其大的数

先使所指的元素作为基准元素low
用一个piviot存储49
然后进行比遍历操作
就是high向左移动(high–)，到第一个比piviot小的元素进行一个data[low]=data[high]
然后进行low++，找到第一个大于等于 piviot的赋值给data[high]即可

就这样循环
最后low=high时
正好把piviot存入，左边比它小右边大于等于它

接下来我们管左子表和右子表即可

右子表

这样再划分为两个子表，由于右边只有一个元素不用再次比较了
看左字表即可

然后排序完毕
就是划分呗

代码实现

递归算法比较复杂

需要使用栈（系统的），先入后出
首先第一个函数的话
是先对数组做一个整的划分（0-7）
最后pivot=3

方便划分出来左右子表
然后对左子表进行递归划分
然后还是
先对0到2
划分
最后左边一个元素右边一个元素再进行
这个两个子表已经是排好了其实，下一次还是出来左子表是吧
处理13一个元素呗，high=pivot-1=0，low=0
然后还是low做pivot呗
然后high对应的等于low
high-1不符合条件弹出栈
low还是在那个位置赋值还是那个位置呗，就是没变
右子表就是low=pivot+1=2,high=2
和上面左子表相同呗

第一个入栈（整体的左子表排序完了）
右子表和做字表类似
不说了

算法效率分析

时间复杂度主要在Partition函数呗
这个函数主要做的不就是high和low双向扫描对比
是查找n个元素

最后递归时间复杂度
还要与递归层数有关！

二叉树的层数其实就是对应的递归次数

总结