图解Java经典算法快速排序的原理与实现

第图解Java经典算法快速排序的原理与实现目录快速排序算法原理图解Java代码实现算法分析

快速排序

通过一趟排序将待排元素分成独立的两部分，其中一部分为比基准数小的元素，另一部分则是比基准数大的元素。然后对这两部分元素再按照前面的算法进行排序，直到每一部分的元素都只剩下一个。

本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

算法原理

从数列中挑出一个元素作为基准点重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面然后基准值左右两边，重复上述步骤通过递归把基准值元素左右两侧的数组排序，排完之后，整个数组就排序完成了

图解

问题描述：

给定一个无序排列的数组nums，使其能够按照有序输出

示例：

输入:nums=[4，3，1，2，9，6],

输出:nums=[1，2，3，4，6，9]

图解如下：

Java代码实现

核心代码

publicclassQuickSort{

//比较v是否小于w

publicstaticbooleanless(Comparablev,Comparablew){

returnpareTo(w)

//数组元素交换位置

privatestaticvoidswap(Comparable[]a,inti,intj){

Comparabletemp;

temp=a[i];

a[i]=a[j];

a[j]=temp;

//排序

publicstaticvoidsort(Comparable[]a){

intl=0;

inth=a.length-1;

sort(a,l,h);

privatestaticvoidsort(Comparable[]a,intl,inth){

if(h=l)return;

//对数组进行分组(左右两个数组)

//i表示分组之后基准值的索引

inti=partition(a,l,h);

//让左边的数组有序

sort(a,l,i-1);

//让有边的数组有序

sort(a,i+1,h);

publicstaticintpartition(Comparable[]a,intl,inth){

//确定基准值

Comparablekey=a[l];

//定义两个指针

intleft=l;

intright=h+1;

//切分

while(true){

//从右向左扫描，移动right指针找一个比基准值小的元素，找到就停止

while(less(key,a[--right])){

if(right==l)

break;

//从左向右扫描，移动left指针找一个比基准值大的元素，找到就停止

while(less(a[++left],key)){

if(left==h)

break;

if(left=right){

break;

}else{

swap(a,left,right);

//交换基准值

swap(a,l,right);

returnright;

}

publicclassQuickSortTest{

publicstaticvoidmain(String[]args){

Integer[]arr={3,1,2,4,9,6};

QuickSort.sort(arr);

System.out.println(Arrays.toString(arr));

//排序前：{3,1,2,4,9,6}

//排序后：{1,2,3,4,6,9}

运行结果：

算法分析

时间复杂度

快速排序的最佳情况就是每一次取到的元素都刚好平分整个数组，由于快速排序用到了递归调用，因此计算其时间复杂度也需要用到递归算法来计算。T[n]=2T[n/2]+f(n)；此时时间复杂度是O(nlogn)。最坏的情况，则和冒泡排序一样，每次比较都需要交换元素，此时时间复杂度是O(n^2)。

因此，快速排序的时间复杂度为：O(nlogn)。

空间复杂度

空间复杂度主要是递归造成