原理：不断寻找一个序列的中点，然后对中点左右的序列递归的进行排序，直至全部序列排序完成，使用了分治的思想。
要点：递归、分治
//注意：[start, end]
private static void sortQuick(int[] array, int start, int end) {
if (start < end) {
int key = array[start]; //初始化保存基元 (以数组首元素作为基元)
int i = start;
for (int j = start + 1; j <= end; j++) {
//如果此处元素小于基元，则把此元素和i+1处元素交换，并将i加1，如大于或等于基元则继续循环
if (array[j] < key) {
int temp = array[i + 1];
array[i + 1] = array[j];
array[j] = temp;
i++;
}
}
//交换i处元素和基元
array[start] = array[i];
array[i] = key;
printArray(String.format(Locale.getDefault(), "start = %2d , end = %2d : ", start, end), array);
//递归调用
sortQuick(array, start, i - 1);
sortQuick(array, i + 1, end);
}
}
结果：
数组： 55 22 66 33 11 99 77 44 88
快速排序：
start = 0 , end = 8 : 44 22 33 11 55 99 77 66 88
start = 0 , end = 3 : 11 22 33 44 55 99 77 66 88
start = 0 , end = 2 : 11 22 33 44 55 99 77 66 88
start = 1 , end = 2 : 11 22 33 44 55 99 77 66 88
start = 5 , end = 8 : 11 22 33 44 55 88 77 66 99
start = 5 , end = 7 : 11 22 33 44 55 66 77 88 99
start = 5 , end = 6 : 11 22 33 44 55 66 77 88 99
以中间元素作为基元
//注意：[start, end]
private static void sortQuick2(int[] array, int start, int end) {
if (start < end) {
int index = (start + end) / 2; //以中间值作为分界值key
int key = array[index];
int lt = start, rt = end;
while (lt < rt && lt < end && rt > start) {
while (lt < end && array[lt] < key) {
lt++;
}
while (rt > start && array[rt] > key) {
rt--;
}
if (lt < rt) {
int temp = array[rt];
array[rt] = array[lt];
array[lt] = temp;
lt++;
if (rt < end) {
rt++;
}
}
}
//寻找分界值key所在位置
if (array[lt] == key) {
index = lt;
} else if (array[rt] == key) {
index = rt;
} else {
for (int i = 0; i < array.length; i++) {
if (key == array[i]) {
index = i;
break;
}
}
}
printArray(String.format(Locale.getDefault(), "start = %2d , end = %2d : ", start, end), array);
//递归
sortQuick2(array, start, index - 1);
sortQuick2(array, index + 1, end);
}
}
结果：
数组： 55 22 66 33 11 99 77 44 88
快速排序：
start = 0 , end = 8 : 11 22 66 33 55 99 77 44 88
start = 1 , end = 8 : 11 22 44 33 55 99 77 66 88
start = 1 , end = 3 : 11 22 33 44 55 99 77 66 88
start = 1 , end = 2 : 11 22 33 44 55 99 77 66 88
start = 5 , end = 8 : 11 22 33 44 55 66 77 99 88
start = 7 , end = 8 : 11 22 33 44 55 66 77 88 99
