快速排序
原理
快递排序其实是一个递归的过程。
快速排序中任意指定一个数为中轴值，将小于该数的都放到它的左边，大于该数的都放到它的右边。然后对它的左子序列和右子序列继续做快速排序。
过程
规定序列左边的第一个数为pivot，两个指针left和right分别指向序列的左边和右边；因为后面递归还需要用到left和right，所以使用l和r保存left和right的值，使用l和r进行移动定位；从右边开始（因为我将最左边的数作为pivot，所以从右边开始，如果将最右边的数作为pivot，则从最左边开始），寻找比基准值小的数，就停住；
接着从左边开始，寻找比基准值大的数，停住；交换a[l]和a[r]；依次反复，直到l和r相遇，将a[l/r]放到pivot所在的位置a[left]，pivot放到a[l/r]，一次快速排序就结束。此时pivot左边的数都比pivot小，右边都比pivot大。递归地对左子序列和右子序列做上面的过程。
代码实现
public static void quickSort(int[] a
, int left
, int right
) {
if (left
>= right
) return;
int pivot
= 0;
int l
= left
;
int r
= right
;
int temp
;
while (true) {
pivot
= a
[left
];
while (a
[r
] >= pivot
&& l
< r
) r
--;
while (a
[l
] <= pivot
&& l
< r
) l
++;
if (l
== r
) break;
temp
= a
[r
];
a
[r
] = a
[l
];
a
[l
] = temp
;
}
if (l
!= left
) {
a
[left
] = a
[l
];
a
[l
] = pivot
;
}
quickSort(a
, left
, l
- 1);
quickSort(a
, l
+ 1, right
);
}
public static void quickSort1(int[] a
, int left
, int right
) {
if (left
>= right
) return;
int pivot
= a
[left
];
int l
= left
;
int r
= right
;
while (true) {
while (a
[r
] >= pivot
&& l
< r
) {
r
--;
}
a
[l
] = a
[r
];
while (a
[l
] <= pivot
&& l
< r
) {
l
++;
}
a
[r
] = a
[l
];
if (l
== r
) break;
}
a
[l
] = pivot
;
quickSort1(a
, left
, l
- 1);
quickSort1(a
, l
+ 1, right
);
}
以上两段代码都可实现快速排序，经过测试排序1000万数据平均用时1.048s。移位法和交换法的区别不是很大，通过debug可以看到整个排序的详细过程。
