时间复杂度为 O(NlogN) 不稳定
主要思想就是分治
注释给的非常详细了,自己debug领悟一下
package com.xizi.sort; import java.io.BufferedInputStream; import java.util.Arrays; import java.util.Scanner; public class QuickSort { public static void main(String[] args) { int[] arr=new int[]{5,4,3,2,1}; int n=arr.length; quickSort(arr,0,n-1); for(int a:arr) { System.out.print(a+" "); } //底层使用双轴快速排序 Arrays.sort(arr); } //时间复杂度 O(NlogN) //1. 选取pivot //2. 划分,根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分 //3. 递归求解小于pivot和大于pivot的部分 public static void quickSort(int[] arr,int left,int right) { //边界判断 区间只剩下一个元素时直接返回 if(left>=right) { return; } //取左边界为分界点 int pivot=arr[left]; //下面使用do while循环 i先减1 j加1 int i=left-1,j=right+1; // 调整区间 使小于pivot的值在左边 大于pivot的值在右边 // 当i==j相遇 arr[]就会被划分为两个区域 while(i<j) { //从前往后找到第一次小于pivot的值 do {i++;}while(arr[i]<pivot); //从后往前找到第一次大于pivot的值 do {j--;}while(arr[j]>pivot); //然后进行交换 if(i<j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } //递归处理 左右区间 quickSort(arr,left,j); quickSort(arr,j+1,right); } }