图解Java经典算法快速排序的原理与实现
快速排序
通过一趟排序将待排元素分成独立的两部分,其中一部分为比基准数小的元素,另一部分则是比基准数大的元素。然后对这两部分元素再按照前面的算法进行排序,直到每一部分的元素都只剩下一个。
本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。
算法原理
- 从数列中挑出一个元素作为基准点
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面
- 然后基准值左右两边,重复上述步骤
- 通过递归把基准值元素左右两侧的数组排序,排完之后,整个数组就排序完成了
图解
问题描述:
给定一个无序排列的数组 nums,使其能够按照有序输出
示例:
输入: nums = [4,3,1,2,9,6],
输出: nums = [1,2,3,4,6,9]
图解如下:
Java代码实现
核心代码
运行结果:
算法分析
时间复杂度
快速排序的最佳情况就是每一次取到的元素都刚好平分整个数组,由于快速排序用到了递归调用,因此计算其时间复杂度也需要用到递归算法来计算。T[n] = 2T[n/2] + f(n);此时时间复杂度是O(nlogn)。最坏的情况,则和冒泡排序一样,每次比较都需要交换元素,此时时间复杂度是O(n^2)。
因此,快速排序的时间复杂度为:O(nlogn)。
空间复杂度
空间复杂度主要是递归造成的栈空间的使用,最佳情况是,递归树的深度为log2n,此时空间复杂度为O(logn),最坏情况,则需要进行n‐1递归调用,此时空间复杂度为 O(n)。
因此,快速排序的空间复杂度为: O(logn)。
到此这篇关于图解Java经典算法快速排序的原理与实现的文章就介绍到这了,更多相关Java快速排序内容请搜索编程学习网以前的文章希望大家以后多多支持编程学习网!