分析：
取一个数P作为基准，然后将小于P的数放在P的左边，大于P的数放在P的右边
JAVA实现：
public class Main {
public static void main(String[] args) {
int[] arr = new int[100];
for(int i=0;i<100;i++) {
arr[i] = (int) (Math.random() * 100);
}
sort(arr);
for(int i=0;i<100;i++){
System.out.println(arr[i]);
}
}
public static void sort(int[] arr) {
sort(arr, 0, arr.length-1);
}
public static void sort(int[] arr, int l, int r) {
if(l > r){
return;
}
int p = arr[l];
int i=l;
int j=r;
while(i < j){
while(i < j && arr[j] >= p) {
j--;
}
while(i < j && arr[i] <= p) { //必须是小于等于，忽略第一个基准数
i++;
}
if(i<j){
swap(arr, i,j);
}
}
if(i != l){
swap(arr, i, l); //将基准数p和位置i的数进行交换，因为i这个位置的数是小于p的
sort(arr, l, i-1);
}
sort(arr, i+1, r);
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
下面是数组的交换过程：
原始数组 [4,8,5,0,1,6,3]
交换：3,8
[4, 3, 5, 0, 1, 6, 8]
交换：1,5
[4, 3, 1, 0, 5, 6, 8]
基准交换：4,0
[0, 3, 1, 4, 5, 6, 8]
交换：3,1
[0, 1, 3, 4, 5, 6, 8]
