java数据结构之快速排序

排序算法是java数据结构的基础，也是程序员必备的基础算法之一，个人认为，了解并掌握排序算法的思想比起单纯用代码实现功能更有意义，毕竟创造这套算法的思想才是最高的智慧嘛，下面就来说说关于排序算法中的比较经典的算法——快速排序；

先用几张示意图来说说快速排序的思想，

1、首先给定一个无序的数组，定义两个指针i和j，他们的起始位置分别是左边的最小下标和右边的最大下标，同时为方便起见，这里使用数组的第一个数作为基准值，这个基准值就是整个快速排序过程中第一轮循环需要使用的值，

2、首先移动j的值，从最右边开始查找，找到第一个比66小的值，即找到第一个小于基准值的值，然后取出来，填补到66所在的第一个位置，即i=0处，

找了第一个比66小的值42，取出来，填充到1=0处，然后，再移动左指针，从左往右找，找到第一个比66大的值，88，填补j=5的位置，

然后，再从右边向左边找，移动j，每次j–，找到比66小的位置，再从左往右找，重复上面的过程，直到i=j两个位置重合，此时的意思是i=j的位置上，左边的数都比66小，右边的都比66大，第一轮循环查找结束，同时将66填充到i=j=4的位置上；

接下来，将以i=j=66的位置为分界线，分成左右两个新的数组，左右两边的数组同样适用上述的方式进行查找排序，由此，我们是不是可以想到适用什么比较适合呢？没错，就是递归，接下去就是递归不断重复排序的过程，最终可以得到排序后的数组；

下面用具体的代码来实现排序的功能，具体的解释可参考注释，

public class FastSortOrderMath {
	
	public static void main(String[] args) {
		//1、给定一个无序数组
		int[] arr = {66,13,58,88,59,42,83,74,48,95};
		//2、输出无序数组
		System.out.println(Arrays.toString(arr));
		//3、快速排序
		quickSort(arr);
		//4、输出排序后的有序数组
		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] arr) {
		int low = 0;
		int high = arr.length - 1;
		quickSort(arr,low,high);
	}

	private static void quickSort(int[] arr, int low, int high) {
		if(low < high){
			//分区，将一个数组分成两个数组，找到分区界限的值的索引并返回
			int index = partition(arr,low,high);
			//对左边的分区进行快排
			quickSort(arr,low,index-1);
			//再对右边的分区进行快排序
			quickSort(arr,index+1,high);
		}
	}

	//分区方法
	private static int partition(int[] arr, int low, int high) {
		//指定两个指针i , j
		int i = low;
		int j = high;
		//将第一个数作为基准值，挖坑
		int x = arr[low];
		//使用循环进行分区操作
		while(i<j){
			//1、从右向左移动，找到第一个小于基准值的值，arr[j]
			while(arr[j] >= x && i<j){
				j--;
			}
			//2、将右侧找到的小于基准值的值取出来填充到左边的 i的位置即坑的位置，然后i++，左指针向中间移动位置
			if(j > i){
				arr[i]=arr[j];
				i++;
			}
			//3、再从左侧i的位置开始移动，找到第一个大于基准值的位置arr[i]
			while(arr[i] < x && i<j){
				i++;
			}
			//4、将左侧找到的大于等于基准值的值加入到右侧的坑中，然后右指针向左边移动一个位置，j--
			if(i<j){
				arr[j] = arr[i];
				j--;
			}
		}
		//使用基准值填坑，这个就是基准值的最后的位置
		arr[i]=x;
		//返回基准值所在的索引位置
		return i;
	}

运行一下，看到控制台的打印结果，

总结来说，快速排序 = 冒泡+分区治理+递归，整个过程用一句通俗的话来说，就是东拆西补或西拆东补，一边拆，一边补，这样的思想是不是很有意思。

以上演示了快速排序的过程，由于个人经验有限，如有理解上的偏差，请多多包涵，示意图的细节没有全部添加，主要是帮助理解排序过程，谢谢观看！