基础知识还是要经常复习的！用的时候又有点忘了,特来复习一下。
网上快排大概有两种写法 不过思想差不多
一种是把第一个元素作为基准，先从右向左扫描，替换数组元素的值，最后把基准赋给i=j相遇时位置的值
另一种是往左移，往右移找出比基准大和往左移比基准小的元素交换位置，如果下标i<j的话，就交换两个元素，如果i=j的话，就把这个位置数组和元素的值和基准交换1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.*;
public class postOr {
public static void Q1sort(int[] nums,int low,int high)
{
if(low>high) return;
int tmp=nums[low];//以第一个元素为基准
int i=low,j=high;
while(i<j)
{
while(nums[j]>=tmp&&i<j)//从右向左扫描
//往左移，找出比基准小的记录位置
j--;
while(nums[i]<=tmp&&i<j)//从左向右扫描
//要有等于号！ 往右移，找比基准大的记录位置
i++;
if(i<j) //如果i<j，交换它们
{
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
nums[low]=nums[i];
nums[i]=tmp;
Q1sort(nums,low,i-1 );
Q1sort(nums,i+1,high );
}
public static void Q2sort(int[] nums,int low,int high)
{
if(low>=high) return;
int tmp=nums[low];
int i=low,j=high;
while(i<j)
{
while(nums[j]>=tmp&&i<j)//从右向左扫描, 必须先从右向左，之前的tmp保存的是左边的值
j--;
nums[i]=nums[j];
while(nums[i]<=tmp&&i<j)//从左向右扫描
i++;
nums[j]=nums[i];
}
nums[i]=tmp;
Q2sort(nums,low,i-1 );
Q2sort(nums,i+1,high );
}
public static void main(String[] args)
{
int[] a=new int[20];
Scanner in = new Scanner(System.in);
int n=in.nextInt();
for(int i=0;i<n;i++)
a[i]=in.nextInt();
Q1sort(a,0,n-1);
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
Q2sort(a,0,n-1);
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
}
}
参考链接
https://www.jianshu.com/p/442399ef0cf7
http://www.cnblogs.com/vanezkw/archive/2012/06/21/2557685.html
http://www.cnblogs.com/kkun/archive/2011/11/23/quick_sort.html