欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-29 16:02:10
...

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

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

 

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],改变前后无异,然后递归继续排序左边的和右边的,
	//可是左边为空,右边就一直都是死循环。