数据结构--快速排序

 目录

快速排序的定义

演示快速排序过程

快速排序的算法：（重点！！！）

算法效率分析

比较好的情况

最坏情况

回顾本节内容

---

 快速排序的定义

 

选取基准后，分成右边是大于基准的元素，左边是小于基准的 ，移动low和high指针

默认情况是第一个元素为基准

演示快速排序过程

1）选取49为基准，暂时存放到一边，使用low和high指针，让high右边全部大于等于49，low左边小于49，

 

2) low指向空，所以从high开始左移，遇到27小于49，所以把27放到0号位置

 3)low指针右移，指向的元素和49基准对比，遇到65大于49，放到6号空缺位置

 4）low指向空，high左移，对比元素，65大于49，不用动65，左移遇到13，13小于49，所以13放到左边的2号空缺位置

 5）low指向13小于49，不同动，low右移，遇到97，97大于49，所以97放到右边，5号空缺位置

 

 6）high指向97，97大于49，不用移动high指针左移，遇到76，76大于49，不用动，high继续左移，遇到low，此时low=high，基准位置可以确定了，基准49放到low=high指向的3号位置，完成一轮

 7）完成了一轮

 

接下来的排序只看基准划分好的左边和右边

左边的：

 

同理右边也是一样的步骤。

快速排序的算法：（重点！！！）

快速排序需要一个递归工作栈

 

算法效率分析

 

 

 

 

 

 比较好的情况

找到基准后可以将待排序的序列划分为均匀的两个部分，递归深度最小，算法效率最高

最坏情况

以基准为轴，待排序被划分的不均匀的两部分，如果初始序列为顺序或者逆序，快速排序性能最差

快速排序是所有内部排序算法中平均性能最优的排序算法

 

回顾本节内容