今天我们接着昨天的快速排序来说，主要进行一个代码的实现。具体的排序思想上一篇我已经说过了，这一篇主要是一个代码的实现：
private int getPivot(int begin, int end) {
return (begin + end) >> 1;
} // 一次排序
private int partition(int[] array, int begin, int end) {
int pivot = getPivot(begin, end);
int tmp = array[pivot];
array[pivot] = array[end];
while (begin != end) {
while (array[begin] < tmp && begin < end)
begin++;
if (begin < end) {
array[end] = array[begin];
end--;
}
while (array[end] > tmp && end > begin)
end--;
if (end > begin) {
array[begin] = array[end];
begin++;
}
}
// 此时两个下标指向同一个元素.以这个位置左右分治(分治点)
array[begin] = tmp;
return begin;
}
private void qsort(int[] array, int begin, int end) {
if (end - begin < 1)
return;
int pivot = partition(array, begin, end);
qsort(array, begin, pivot);
qsort(array, pivot + 1, end);
}
@Test
public void main() {
int[] array = {4,6,1,8,3,5,7};
qsort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
排序结果
