快速排序是冒泡排序的改进版,也是最好的一种内排序,在很多面试题中都会出现,也是作为程序员必须掌握的一种排序方法。
思想:
1.在待排序的元素任取一个元素作为基准(通常选第一个元素,但最的选择方法是从待排序元素中随机选取一个作为基准),称为基准元素;
2.将待排序的元素进行分区,比基准元素大的元素放在它的右边,比其小的放在它的左边;
3.对左右两个分区重复以上步骤直到所有元素都是有序的。
所以我是把快速排序联想成东拆西补或西拆东补,一边拆一边补,直到所有元素达到有序状态。
源码
package com; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner s=new Scanner (System.in); int n=s.nextInt(); int [] a=new int [n]; for(int i=0;i<n;i++) a[i]=(int)(Math.random()*100); quicksort(a,0,a.length-1); System.out.println(Arrays.toString(a)); } public static void quicksort(int[] a) { if(a==null||a.length<=1) return; quicksort(a,0,a.length-1); } public static void quicksort(int[] a,int left,int right) { if(left>=right) return; int midIndex=left+(int)(Math.random()*(right-left+1)); int i=left; int j=right-1; swap(a,midIndex,right); while(i<=j) { if(a[i]<=a[right]) { i++; }else { swap(a,i,j); j--; } } swap(a,i,right); quicksort(a,left,i-1); quicksort(a,i+1,right); } public static void swap(int[] a,int x,int y) { int temp=a[x]; a[x]=a[y]; a[y]=temp; } }
以上代码仅供参考