快速排序图解过程（AcWing 785.快速排序（Java））

题目来源：AcWing 785.快速排序

题目描述

给定你一个长度为 n的整数数列
  
  
  
  
  。

请你使用快速排序对这个数列按照从小到大进行排序  
  
  
  
  
 。

并将排好序的数列按顺序输出
 


 


 


 


 


。

输入格式

输入共两行           ，第一行包含整数 n
 
 
 
 
 。

第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内）
  
 
  
 
  
 
  
 
  
 
，表示整个数列   
   
   
   
   
 。

输出格式

输出共一行









，包含 n 个整数 
  
  
  
  
  ，表示排好序的数列
 

 

 

 

 

。

数据范围

1≤n≤1000001≤n≤100000

输入样例： 5 3 1 2 4 5 输出样例： 1 2 3 4 5

思路讲解

首先快速排序的话
  
  
  
  
  
，我们应当先确定一个基准点x
 


 


 


 


 

，这个基准点可以是左端点 
 
 
 
 
 ，可以是右端点
   
   
   
   
   
，可以是中间值
 

 

 

 

 
，也可以是数组中任意一值 确定了基准值x后 

 

 

 

 

 ，便是调整区间          ，将整个序列调整为小于等于x都在x左边, 大于等于x都在x右边 那么问题来了

 
 

 
 

 
 

 
 

 
 
，如何确定呢？这里我们使用双指针的方法









，i作为左指针                ，j作为右指针
 
 
 
 
 
 
 
 
 
 
，分别向中间进行移动














，移动条件便是q[i]与q[j]分别于x进行对比           ，看是否满足左右两边的定义
  
 
  
 
  
 
  
 
  
 
，当不满足时









，停止移动 
  
  
  
  
  ，并交换双方的值
  
  
  
  
  
，然后接着移动直到i=j 当i=j后
 


 


 


 


 

，我们可以发现x左端皆小于x 
 
 
 
 
 ，右端皆大于x

 

 

 

 

 。但是并不是有序排序
   
   
   
   
   
，那么我们采用递归的方法
 

 

 

 

 
，再次对左右两边的两端进行上述操作 

 

 

 

 

 ，而在这两次循环中我们又可以再进行递归操作......直到递归到i==j          ，结束递归 这样我们就得到了一个有序数组

代码

import java.util.Scanner; public class Main { public static void main(String[] args) { //输入数组大小与数组的值 Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int []q = new int[n]; for (int i = 0; i < n; i++) { q[i] = sc.nextInt(); } //进行排序 quick_sort(q,0,n-1); //输出结果 for(int i=0; i<n; i++) System.out.print(q[i] + " "); } public static void quick_sort(int q[],int left,int right){ if(left >= right) return;//如果左端比右端大或者相等

 
 

 
 

 
 

 
 

 
 
，无需排序直接结束 int x= q[left + (right - left) / 2]; //基准为中间值 //定义两个指针 int i = left - 1; int j = right + 1; // while (i < j){ do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); //手打一个swap交换i









，j双指针 if(i < j){ int t = q[i]; q[i] = q[j]; q[j] = t; } } //进行递归,各自对两边进行排序 quick_sort(q,left,j); quick_sort(q,j+1,right); } }

通过截图