Sorting_quicksort_anim.gif
维基百科：快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，最早由东尼·霍尔提出。在平均状况下，排序n 个项目要
(
log
) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。
快速排序思想
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第2步，直到各区间只有一个数。
完整实现
public class FastSort {
private static int a[] = {8, 4, 9, 1, 10, 6};
public static void main(String args[]) {
sortNormalArray();
//sortBigArray();
}
private static void sortNormalArray() {
quickSort(a, 0, a.length - 1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ",");
}
}
/**
* 对一个大数组排序
*/
private static void sortBigArray() {
long currTime = System.currentTimeMillis();
int[] random = new int[1000000];
for (int i = 0; i < random.length; i++) {
random[i] = (int) (Math.random() * 10000000);
}
quickSort(random, 0, random.length - 1);
System.out.println("耗时" + (System.currentTimeMillis() - currTime) + "ms");
for (int i = 0; i < random.length; i++) {
System.out.println(random[i] + "");
}
}
/**
* 调用者请确保传入正确的参数
*
* @param a 要排序的数组
* @param left 0
* @param right 数组的长度减去1
*/
private static void quickSort(int[] a, int left, int right) {
if (left < right) {
int i = left;
int j = right;
int pivot = a[left];
while (i < j) {
while (i < j && a[j] >= pivot) {
j--;
}
if (i < j) {
a[i] = a[j];
i++;
}
while (i < j && a[i] < pivot) {
i++;
}
if (i < j) {
a[j] = a[i];
j--;
}
}
a[i] = pivot;
//递归排序
quickSort(a, left, i - 1);
quickSort(a, i + 1, right);
}
}
}
参考链接：
