算法思想
代码归档地址:https://github.com/taoweidong/Java-Learning
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
思路分析:快速排序采用双向查找的策略,每一趟选择当前所有子序列中的一个关键字作为枢纽轴,将子序列中比枢纽轴小的前移,比枢纽轴大的后移,当本趟所有子序列都被枢轴按上述规则划分完毕后将会得到新的一组更短的子序列,他们将成为下趟划分的初始序列集。对于每一个子序列的划分采用的迭代的方式,因此在结束条件上一定要注意,否则很容易造成堆栈溢出的问题
时间复杂度:最好情况(待排序列接近无序)时间复杂度为O(nlog2n),最坏情况(待排序列接近有序)时间复杂度为O(n2),平均时间复杂度为O(nlog2n)。
代码实现
1 | package com.data.structure; |
结果:
参考
- 本文作者: 半度微凉
- 本文链接: http://www.taoweidong.com/2020/03/21/Java数据结构和算法-快速排序算法/
- 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!