Java的快速排序法代码分步解析

青旅半醒 2022-02-05 10:17 190阅读 0赞

刚开始看快速排序的时候，还是有点懵的，虽然大体意思上算是了解了，但是整体流程还不够清晰，网上已经有很多分析快速排序的博客了，介绍的话不在这里说了，写下这篇博客就是为了以后再看快排的时候可以快速复习。

**以下分为两个部分，第一部分为代码部分，第二部分为分步讲解，两部分对比着看。**

## 一 代码区 ##

public class QuickSort { 
    	private static int count;
    	/** * 测试 * @param args */
    	public static void main(String[] args) { 
    		int[] num = { 3,45,78,52,2};
    		System.out.println(arrayToString(num,"未排序"));
    		QuickSort(num,0,num.length-1);
    		System.out.println(arrayToString(num,"排序"));
    		System.out.println("数组个数："+num.length);
    		System.out.println("循环次数："+count);
    		
    	}
    	/** * 快速排序 * @param num 排序的数组 * @param left 数组的前针 * @param right 数组后针 */
    	private static void QuickSort(int[] num, int left, int right) { 
    		//如果left等于right，即数组只有一个元素，直接返回
    		if(left>=right) { 
    			return;
    		}
    		//设置最左边的元素为基准值
    		int key=num[left];
    		//数组中比key小的放在左边，比key大的放在右边，key值下标为i
    		int i=left;
    		int j=right;
    		while(i<j){ 
    			//j向左移，直到遇到比key小的值
    			while(num[j]>=key && i<j){ 
    				j--;
    			}
    			//i向右移，直到遇到比key大的值
    			while(num[i]<=key && i<j){ 
    				i++;
    			}
    			//i和j指向的元素交换
    			if(i<j){ 
    				int temp=num[i];
    				num[i]=num[j];
    				num[j]=temp;
    			}
    		}
    		num[left]=num[i];
    		num[i]=key;
    		count++;
    		QuickSort(num,left,i-1);
    		QuickSort(num,i+1,right);
    	}
    
    	/** * 将一个int类型数组转化为字符串 * @param arr * @param flag * @return */
    	private static String arrayToString(int[] arr,String flag) { 
    		String str = "数组为("+flag+")：";
    		for(int a : arr) { 
    			str += a + "\t";
    		}
    		return str;
    	}
     
    }

## 二 分步分析 ##

1、首先准备一个数组：  
![在这里插入图片描述][20190505160253824.png]  
2、目前各变量的值：

left=0
    right=4
    key=3	
    i=0	
    j=4

3、首先j开始左移，直到找到比key值小的值为止，结果第一个值就比key小，所以j依然为4  
4、接下来i开始右移，直到找到比key值大的值为止，当i移动到索引1时，值大于key值，所以i的值变更为1  
5、索引i的值与索引j的值交换，数组变更为如下：  
![在这里插入图片描述][20190505160630127.png]  
6、目前各变量的值：由于i<j，所以重复第三步和第四步的操作。

left=0
    right=4
    key=3
    i=1
    j=4

7、j继续左移，寻找比key小的值，最后j停留在索引为1的位置  
8、由于i等于j所以不再右移  
9、退出循环，各变量如下

left=0
    right=4
    key=3
    i=1
    j=1

10、数组索引为0的值与索引为i的值交换，这样i左边的值都比i小，右边的值都比i大，数组如下图：  
![在这里插入图片描述][20190505160835876.png]  
11、此时数组被分割成两部分，两部分如下：  
![在这里插入图片描述][20190505160858959.png]  
12、第二部分与前面的操作类似，不再赘述。  
第一部分只有一个值，目前left=0，right=0，这将会因为以下代码结束排序

//如果left等于right，即数组只有一个元素，直接返回
    if(left>=right) { 
       return;
    }

[20190505160253824.png]: /images/20220205/6550926fec314d56afa8b8dd0863a32f.png
[20190505160630127.png]: /images/20220205/77002ca2c56a46a2943ca329d7cf2e0e.png
[20190505160835876.png]: /images/20220205/3f9b74ce52fe42498f17b652b5b8774d.png
[20190505160858959.png]: /images/20220205/05b3737e4d7b4ea2a6679ba6935e2e99.png