package com.itheima;
public class Test3 {
public static void println(int array[], int len) {// 打印数组。。
for (int i = 0; i < len; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void swap(int array[], int i, int j) {// 交换array[i],array[j]的值。
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static int partition(int array[], int low, int high) {// 划分过程的方法，low为最低端下标，high为最高端下标
// 基准点，即把这个数放到它应该在的位置。
// 什么是应该在的问题？即把它左边的数都小于等于它，右边的数都大于等于它。
int pv = array[low];// 用最低端的元素初始化基准。
while (low < high) {// 结束条件为low 和 high 交汇的时候。
while ((low < high) && (array[high] >= pv)) {// 如果array[high]比基准点大high--,否则不满足退出循环。
high--;// 为什么high--呢，因为该数大于等于基准点，的确应该在基准点左边。没错，所以可以high--，查看上一个数，是否也同样满足。
}
swap(array, low, high);// 不满足,即array[high]位置的数小于基准点的数，则交换两元素位置。
// 为什么交换呢，因为基准点的右边只允许放比它大的数，比它小的数，当然放基准点的左边了。
while ((low < high) && (array[low] <= pv)) {// 如果array[low]比基准点小high++,否则不满足退出循环。
low++;// 为什么high++呢，因为该数小于等于基准点，应该在基准点左边，没错。所以可以high++，查看上一个数，是否也同样满足。
}
swap(array, low, high);// 否则交换array[low],array[high]的值。
// 为什么交换呢，因为基准点的左边只允许放比它小的数，比它大的数，当然放基准点的右边了。
}
return low;// 返回划分好的位置，即它的左边的数都比它小，右边都比它大。
}
public static void QSort(int array[], int low, int high) {
if (low < high) {
int pivot = partition(array, low, high);// 划分array数组的low~high范围，划分后，基准点pivot左边数的都比array[len]小，基准点pivot右边的数都比大。此时array[pivot]在它应该在位置.
QSort(array, low, pivot - 1);// 递归快排pivot左边的数。
QSort(array, pivot + 1, high);// 递归快排pivot右边的数。
}
}
public static void QuickSort(int array[], int len) {
QSort(array, 0, len - 1);
}
public static void main(String[] args) {
int array[] = { 1, 5, 100, 22, 21, 25, 49, 25, 16, 8 };// 定义并初始化，数组。
int len = 10;// 数组长度.
println(array, len);// 打印排序前的数组。
QuickSort(array, len);// 快排
println(array, len);// 打印快排后的数组。
}
}
以前写的。看能不能帮到楼主。 |
收藏
淘帖
踩
