java数据结构之快速排序

柔光的暖阳◎ 2023-10-18 11:22 50阅读 0赞

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

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

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

2、首先移动j的值，从最右边开始查找，找到第一个比66小的值，即找到第一个小于基准值的值，然后取出来，填补到66所在的第一个位置，即i=0处，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 1]

找了第一个比66小的值42，取出来，填充到1=0处，然后，再移动左指针，从左往右找，找到第一个比66大的值，88，填补j=5的位置，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 3]

然后，再从右边向左边找，移动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;
    	}

运行一下，看到控制台的打印结果，  
![在这里插入图片描述][20181118113640750.png]

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20181118111853738.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20181118112302597.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20181118112355819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20181118112511919.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[20181118113640750.png]: https://img-blog.csdnimg.cn/20181118113640750.png