快速排序之一路快速排序（Java实现）

不念不忘少年蓝@ 2022-02-05 05:34 384阅读 0赞

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

# 一路排序不考虑等于的情况，将等于的数字划分到大于区或者等于区，还有一个特点就是一路排序从左到右遍历。废话不多说，直接上代码，好东西都在代码里。边看图边写代码边写注释，真的是美滋滋了呢！ #

package sort;
    
    public class QuickSort { 
    	/* * 4 3 2 4 5 8 7 3 6 * 4 3 2 4 */
    	public static void sort(int[] arr) { 
    		quicksort(arr, 0, arr.length - 1);
    	}
    
    	private static void quicksort(int[] arr, int start, int end) { 
    		// TODO Auto-generated method stub
    		if(end-start<=15) { 
    			/* * 当最后剩下需要排的数据少的时候， * 这些剩下的数据已经极度有序了，用插入排序。 */
    			InsertSort.sort(arr, start, end);
    			return;
    		}
    		int target=findpartition(arr,start,end);
    		quicksort(arr, start, target);//对小于等于部分排序
    		quicksort(arr, target+1, end);//对大于部分排序
    	}
    
    	private static int findpartition(int[] arr, int start, int end) { 
    		// TODO Auto-generated method stub
    		/* * 由于刚开始的start位置的值V有可能左边的值都比他大， * 造成递归形成的树左偏或者右偏，为不平衡二叉树。 * 所以要将V值随机。 */
    		swap(arr,start,(int) (Math.random()*(start-end+1)+start));
    		int v=arr[start];
    		int j=start;
    		for(int i=start+1;i<=end;i++) { 
    			if(arr[i]<=v) { 
    				/* * 4 3 2 4 5 8 7 3 6 * s j i * 4 3 2 4 把5和3交换 i在3的位置 j在4的位置 j++ * 4 3 2 4 3 8 7 5 6 * s j i s~j小于等于V j+1~到i 大于V */
    				swap(arr,j+1,i);
    				j++;
    			}
    			
    		}
    		//将分区设置好后，将j和start位置的值交换，
    		//4 3 2 4 3 8 7 5 6
    		//s j i
    		//此时，4的左边就是小于等于4的值，右边大于。
    		//3 3 2 4 4 8 7 5 6
    		//s j i
    		//然后返回j 再对j的两边排序
    		swap(arr,j,start);
    		return j;
    	}
    
    	private static void swap(int[] arr, int i, int j) { 
    		// TODO Auto-generated method stub
    		/* * 数字用这个 temp那个通用 * a:3 b:4 * a=3+4=7; * b=7-4=a-b=3 * a=a-b=q-3=4 * 不推荐 */
    		/* * 数据量大用异或 * a = a ^ b；将a变成中间变量 b = b ^ a； a = a ^ b； */
    		/* arr[i]=arr[i]+arr[j]; arr[j]=arr[i]-arr[j]; arr[i]=arr[i]-arr[j]; */
    		arr[i]=arr[i]^arr[j];
    		arr[j]=arr[i]^arr[j];
    		arr[i]=arr[i]^arr[j];
    	}
    }

# 测试代码 #

package sort;
    
    import java.util.Arrays;
    import java.util.Random;
    
    public class TestAllSort { 
    	public static void main(String[] args) { 
    		int arr[]= { 2,3,6,3,5,9,0,1,18,10,11,7};
    		/* int arr[]=new int[50000]; Random ro=new Random(); for(int i=0;i<arr.length;i++) { arr[i]=ro.nextInt(10000); }*/
    		int starttime=(int) System.currentTimeMillis();
    		//CountIntegerSort.sort(arr);
    		//Arrays.sort(arr);
    		//MergeSort.sort(arr);
    		QuickSort.sort(arr);
    		int endtime=(int) System.currentTimeMillis();
    		System.out.println(Arrays.toString(arr));
    		System.out.println(endtime-starttime+"ms");
    	}
    }

![在这里插入图片描述][20190505010619674.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70]: /images/20220205/3ff0361d97a9419db2a3445c1d4b7317.png
[20190505010619674.png]: /images/20220205/d444da96fdd54e47a3c5e83984f2a1f3.png