java实现快速排序图解_快速排序图文详解

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

快速排序法介绍

• 快速排序（QuickSort）是对冒泡排序的一种改进，基本思想是：通过一趟排序将 要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

图解

代码理解

public class QuickSort { 

//从小到大排序
public void quickSort(int left, int right, int[] nums){ 

if(left<right){ 

//将小于nums[left]的值放左边，大于nums[left]的值放右边
int index = partition(left, right, nums);
//对左边部分进行快速排序
quickSort(left, index, nums);
//对右边部分进行快速排序
quickSort(index+1, right, nums);
}
}
private int partition(int left, int right, int[] nums) { 

/** * 这一部分的理解，我们可以假设此时数组排序为【2,1,3,4,5】 * 那么while (left<right&&nums[right]>base) * 会循环到right=1 * 之后数组变化如下 * nums[left]=nums[right] * 【1,1,3,4,5】 * while (left<right&&nums[left]<base)循环到left=1 * nums[right]=nums[left]相当于什么都没做 * 此时left等于right，跳出循环 * 整个过程可以简化为 * base = nums[left] * nums[left]=nums[right] * nums[right]=base */
int base = nums[left];
while (left<right){ 

while (left<right&&nums[right]>=base){ 

right--;
}
nums[left] = nums[right];
while (left<right&&nums[left]<=base){ 

left++;
}
nums[right] = nums[left];
}
nums[right] = base;
return left;
}
public static void main(String[] args) { 

int[] nums = { 
2,3,1,5,4};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(0,nums.length-1, nums);
for(int num:nums){ 

System.out.println(num);
}
}
}

快速排序算法性能分析

• 快速排序的时间性能取决于快速排序递归的深度。
• 在最优的情况下，Partition每次都划分得很均匀，如果排序n个数值，那么递归树的深度就为.log2n.+1（.x.表示不大于x的最大整数），即仅需递归log2n次，其时间复杂度为O(nlogn)
• 在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个数值的子序列，此时需要执行n-1次递归调用且第i次划分需要经过n-i次比较才能得到第i个数值，其时间复杂度为O(n^2）

算法图

• 口诀：堆归选基与初始序列无关 快选希堆排序不稳定