使用java实现快速排序（我认为是最简单最容易理解的版本）

左手的ㄟ右手 2022-05-11 06:28 197阅读 0赞

一切都在代码和注释之中。复制粘贴就能跑，边跑边看才是最愉快的。

所以，话不多说，放码过来。

public class QuickSort {
    
    	public static void main(String[] args) {
    		int x[]={6,1,2,7,9,100,100,4,5,10,8}; //i = 0, j = 10 
    		quickSort(x, 0, x.length-1);
    		for (int i = 0; i < x.length; i++) {
    				System.out.print(x[i] + " ");
    		}
    	}
    	//快排的核心是： 分治法
    	//步骤：
    	//1.选中一个基准值
    	//2.一次排序后，基准值的右边都大于基准值，基准值的左边都小于基准值
    	//3.一次排序完成后，一个数组就分成了两份，然后使用递归对这两份继续排序，直到每一份中只剩一个值
    	//4.进行排序的那一份只剩一个值时，出递归。
    	public static void quickSort(int[] arr, int low, int high) {
    		
    		if(low >= high) {
    			return;
    		}
    		//选择一个基准值,为了简单，我直接使用了数组中的第一个值来作为基准值
    		int middle = arr[low];
    		
    		//为什么要用left和right来表示 low 和 high呢？
    		//因为low和high要用在最后的递归调用，所以不能更改这两个变量的值。
    		
    		//声明一个从左往右找值的哨兵
    		int left = low;
    		//声明一个从右往左找值的哨兵
    		int right = high;
    		
    		while (left < right) {
    			
    			//从右往左找比中位数小的值
    			while(arr[right] >= middle && left < right) {
    				right --;
    			}
    			//从左往右找比中位数大的数
    			while(arr[left] <= middle && left < right) {
    				left ++;
    			}
    			
    			//当找到两个想要的值的时候，进行交换
    			if(left < right) {
    				int temp = arr[left];
    				arr[left] = arr[right];
    				arr[right] = temp;
    			}
    		}
    		
    		//一个while循环之后，left = right ，而且此时arr[left]的值小于middle，因为我们先从右边开始找的,
    		//所以肯定是right-1后碰到的left，如果left经历过交换的话，arr[left]的值肯定小于middle，
    		//没经历过交换的话arr[left]的值就是middle，所以把arr[left] 和 middle交换是没问题的
    		arr[low] = arr[left];
    		arr[left] = middle;
    		quickSort(arr, low, left-1);
    		quickSort(arr, left+1, high);
    	}
    	
    	//从右往左找比中位数小的数，这里要注意使用的是 >= 和 <= 
    	//如果不带=号会陷入一个死循环，为什么会陷入死循环呢？ 我给大家举一个栗子
    	
    	//假设要对这个数组{100,100,7,10,8}进行快排，而且不使用>= 和 <= 而是使用 > 和 <
    	//1.先从右往左找一个 不满足 >middle的值，也就是 <=middle的值，找到了arr[1] 也就是100
    	//2.然后从左往右找一个不满足 < middle的值，也就是 >=middle的值，找到了arr[0] 也就是 100
    	//3.两者进行交换后，再从右往左找<=middle的值，right-1后就与left相等了，下面交换中位数的位置
    	//4.发现中位数的位置是arr[0]，改变前后无异，然后递归继续排序左边的和右边的，
    	//可是左边为空，右边就一直都是死循环。