十大排序算法之快速排序

阳光穿透心脏的1/2处 2024-04-18 16:27 70阅读 0赞

例题：  
对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序  
要求从小到大排列。  
介绍：  
快速排序是改进的冒泡排序，  
快排和冒泡的关系就像是希尔和插入的关系一样  
希尔想怎样能够跳跃性的插入  
快排想一次冒大泡，  
虽然名字叫快速排序，但实际上也不快。。。  
思路：  
首先选定一端作为分割点，为参照物  
然后使用两枚指针，分别从左往右，从右往左进行查询  
从左往右查找大于参照物的值，并记录下这个值的下标  
从右往左查找小于参照物的值，并记录下这个值的下标  
根据下标交换对应的两个值，继续寻找  
当两指针相遇时，记录相遇地点下标，  
交换相遇地点下标和参照物下标，  
此时参照物左边的值均小于参照物的值，参照物右边均大于参照物的值  
然后对两部分分别重复进行上述操作，直到排序完成  
难点：  
左右指针查找时的优先级问题：默认左指针先查找，  
评价：  
一个优于冒泡排序的高级冒泡排序

![在这里插入图片描述][20190909215227969.gif]代码：

package 日常练习;
    
    import java.util.Arrays;
    
    public class 快速排序 {
    	public static void main(String[] args) {
    		int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };
    		q(a,0,a.length-1);
    		System.out.println(Arrays.toString(a));
    	}
    	public static void q(int[] a, int begin, int end) {
    		if(begin>=end) {
    			return;
    		}
    		//设置最左边的元素为参照物
    		int refer=a[begin];
    		//数组中比key小的放在左边，比key大的放在右边，key值下标为i
    		int left=begin;
    		int right=end;
    		while(left<right){
    			//j向左移，直到遇到比key小的值
    			while(a[right]>=refer && left<right){
    				right--;
    			}
    			//i向右移，直到遇到比key大的值
    			while(a[left]<=refer && left<right){
    				left++;
    			}
    			//i和j指向的元素交换
    			if(left<right){
    				int temp=a[left];
    				a[left]=a[right];
    				a[right]=temp;
    			}
    		}
    		a[begin]=a[left];
    		a[left]=refer;
    		q(a,begin,left-1);
    		q(a,left+1,end);
    	}
    }

[20190909215227969.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4f6974a8136e4e0c810808c6781d19d8.gif