[数据结构与算法]快速排序

排序原理：

1. 首先设定一个分界值，通过该分界值将数组分为左右两部分

2. 将小于该分界值的元素置于左边，大于的元素置于右边

3. 左右两边独立排序

4. 重复此操作，知道两两排序后返回

public class quick {
 ? ?//交换
 ? ?public static void exch(Comparable[] a,int i,int j)
 ?  {
 ? ? ? ?Comparable temp;
 ? ? ? ?temp=a[i];
 ? ? ? ?a[i]=a[j];
 ? ? ? ?a[j]=temp;
 ?  }
 ? ?public static boolean less(Comparable i, Comparable j)
 ?  {
 ? ? ? ?return i.compareTo(j)<0;
 ?  }
 ? ?public static void sort(Comparable[] x)
 ?  {
 ? ? ? ?int lo=0;
 ? ? ? ?int hi=x.length-1;
 ? ? ? ?sort(x,lo,hi);
 ?  }
 ? ?public static void sort(Comparable[] x,int lo,int hi)
 ?  {
 ? ? ? ?//进行安全性校验
 ? ? ? ?if(hi<=lo)
 ? ? ?  {
 ? ? ? ? ? ?return;
 ? ? ?  }
 ? ? ? ?//将数组分为左子组和右子组
 ? ? ? ?int i=partition(x,lo,hi);
 ? ? ? ?//将左子组排序
 ? ? ? ?sort(x,lo,i-1);
 ? ? ? ?//将右子组排序
 ? ? ? ?sort(x,i+1,hi);
 ?  }
 ? ?private static int partition(Comparable[] x,int lo,int ?hi) {
 ? ? ? ?int left=lo;
 ? ? ? ?int right=hi+1;
 ? ? ? ?Comparable key=x[lo];
 ? ? ? ?while (true){
 ? ? ? ? ? ?while (true) {
 ? ? ? ? ? ? ? ?if(right==lo) {
 ? ? ? ? ? ? ? ?break;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ? ? ? ?if(less(x[--right],key)) {
 ? ? ? ? ? ? ? ? ? ?break;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  }
 ? ? ? ? ? ?while (true) {
 ? ? ? ? ? ? ? ?if (left==right) {
 ? ? ? ? ? ? ? ? ? ?break;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ? ? ? ?if (less(key,x[++left])) {
 ? ? ? ? ? ? ? ? ? ?break;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  }
 ? ? ? ? ? ?if (left>=right) {
 ? ? ? ? ? ? ? ?break;
 ? ? ? ? ?  }
 ? ? ? ? ? ?else {
 ? ? ? ? ? ? ? ?exch(x,left,right);
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?exch(x,lo,left);
 ? ? ? ?return left;
 ?  }
?
}

import java.util.Arrays;
?
public class QuicklyTest {
 ? ?public static void main(String[] args) {
 ? ? ? ?Integer[] array={1,5,-8,5,-1,14,-9,7,-8};
 ? ? ? ?Integer[] array2={-3,-2,-1,0,1,2,3};
 ? ? ? ?quick.sort(array);
 ? ? ? ?quick.sort(array2);
 ? ? ? ?System.out.println(Arrays.toString(array));
 ? ? ? ?System.out.println(Arrays.toString(array2));
 ?  }
}
?