public class TopK {
public static int k = 3;
public static void main(String[] args) {
int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
topKSort(arr);
StringBuilder topK = new StringBuilder();
for (int i = 0; i < k; i++) {
topK.append(arr);
}
System.out.println("TopK=" + topK);
}
public static int topKSort(int arr[]) {
int length = arr.length;
if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
int left = 0, right = length - 1;
int p = -1;
while (k != p + 1) {
if (k < p + 1) {
right = p - 1;
} else if (k > p + 1) {
left = p + 1;
}
p = partition(arr, left, right);
}
quickSort(arr, 0, k - 1);
return arr[p];
}
public static void quickSort(int arr[], int left, int right) {
if (left >= right) return;
int q = partition(arr, left, right);
quickSort(arr, left, q - 1);
quickSort(arr, q + 1, right);
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int sortIndex = left;
for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
if (arr[arrIndex] > pivot) {
swap(arr, arrIndex, sortIndex);
sortIndex++;
}
}
swap(arr, sortIndex, right);
return sortIndex;
}
public static void swap(int[] arr, int i, int j) {
if (i == j) return;
int tmp = arr;
arr = arr[j];
arr[j] = tmp;
}
}由于1-K之间的数下标是0-k-1,所以排序的时候左边界传0，右边界传k-1即可
2.0：下面我们继续看2.0版本：
[Java] 纯文本查看 复制代码public class TopK {
public static int k = 3;
public static void main(String[] args) {
int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
topKSort(arr);
StringBuilder topK = new StringBuilder();
for (int i = 0; i < k; i++) {
topK.append(arr);
}
System.out.println("TopK=" + topK);
}
public static int topKSort(int arr[]) {
int length = arr.length;
if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
int left = 0, right = length - 1;
int p = -1;
while (k != p + 1) {
if (k < p + 1) {
right = p - 1;
} else if (k > p + 1) {
left = p + 1;
}
p = partition(arr, left, right);
}
quickSort(arr, 0, k - 2);
return arr[p];
}
public static void quickSort(int arr[], int left, int right) {
if (left >= right) return;
int q = partition(arr, left, right);
quickSort(arr, left, q - 1);
quickSort(arr, q + 1, right);
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int sortIndex = left;
for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
if (arr[arrIndex] > pivot) {
swap(arr, arrIndex, sortIndex);
sortIndex++;
}
}
swap(arr, sortIndex, right);
return sortIndex;
}
public static void swap(int[] arr, int i, int j) {
if (i == j) return;
int tmp = arr;
arr = arr[j];
arr[j] = tmp;
}
}
这个版本只有一点小小的改动，是对1.0版本的优化。就是 topKSort 方法中 quickSort 排序的右边界改成了k-2。这里的思路就是依据快排的特点，在K左边位置的数已经都是大于K的，所以在K这个位置的数就不用参与排序了。于是排序的位置就变成了0至k-2之间。
2.0小结：
至此我们topK的问题基本就解决了。但是事实上我们还有优化的空间，优化点主要在quickSort的左边界0和右边界k-2这里。这个优化思路需要你对快速排序和求第K大的数的整个过程特别熟悉：首先在求K值的代码中，其实也是一个排序的过程。所以在0至k-2这个范围内很可能某些数已经是有序的了，这样我们就可以缩小0至k-2这个排序范围，从而缩短排序时间。基于这个思路我们得到了第三个版本。
3.0：
[Java] 纯文本查看 复制代码public class TopK {
public static int k = 8;
public static void main(String[] args) {
int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
topKSort(arr);
StringBuilder topK = new StringBuilder();
for (int i = 0; i < k; i++) {
topK.append(arr);
}
System.out.println("TopK=" + topK);
}
public static int topKSort(int arr[]) {
int length = arr.length;
if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
int left = 0, right = length - 1;
int p = -1;
int leftBorder = 0;
int rightBorder = k - 2;
while (k != p + 1) {
if (k < p + 1) {
right = p - 1;
} else if (k > p + 1) {
left = p + 1;
}
p = partition(arr, left, right);
if (p == leftBorder + 1) {
leftBorder++;
}
if (p == rightBorder - 1) {
rightBorder--;
}
}
quickSort(arr, leftBorder, rightBorder);
return arr[p];
}
public static void quickSort(int arr[], int left, int right) {
if (left >= right) return;
int q = partition(arr, left, right);
quickSort(arr, left, q - 1);
quickSort(arr, q + 1, right);
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int sortIndex = left;
for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
if (arr[arrIndex] > pivot) {
swap(arr, arrIndex, sortIndex);
sortIndex++;
}
}
swap(arr, sortIndex, right);
return sortIndex;
}
public static void swap(int[] arr, int i, int j) {
if (i == j) return;
int tmp = arr;
arr = arr[j];
arr[j] = tmp;
}
}
在topKSort方法的while循环中，加了如下这段代码：
[JavaScript] 纯文本查看 复制代码 if (p == leftBorder + 1) {
leftBorder++;
}
if (p == rightBorder - 1) {
rightBorder--;
}
并将 调用 quickSort 这个方法的左边界和右边界分别用变量 leftBorder 和 rightBorder 代替。
优化思路分析：
首先我们还是看上述代码中的数组 3, 2, 3, 1, 7, 4, 5, 5, 6 ：在第一次 partition 时，基准点是6，排序完成后是 7, 6, 3, 1, 3, 4, 5, 5, 2，下标P的值是1。根据快速排序的特点：因为我们是倒序的，所以基准点6左边的数都是大于6，并且6的下标值是1，它的左边只有一个数7，所以7和6一定是有序的，这样我们就可以将左边界加1，同理既然下标0和1的数都有序了，那么只要P值再出现2,3,4...以及以后的值，就可以将左边界的值加1。同理右边界也是一样的思路，只要P值出现比右边界小1，那么就可以将右边界减一。这样就缩小了排序的左边界和右边界，缩短了整个排序的时间，优化了整个topK的算法。
优化效果比较：
优化前
优化后
左边这幅图是top1-top9优化前的左右边界值，右边这幅图是top1-top9优化后的左右边界值。可以看出来在top3-top7中，左边界的变化还是挺大的，优化效果还是很明显的。
4.0：public class TopK {
public static int k = 8;
public static boolean topBigK = true;
public static void main(String[] args) {
int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
topKSort(arr);
StringBuilder topK = new StringBuilder();
for (int i = 0; i < k; i++) {
topK.append(arr);
}
System.out.println("TopK=" + topK);
}
public static int topKSort(int arr[]) {
int length = arr.length;
if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
int left = 0, right = length - 1;
int p = -1;
int leftBorder = 0;
int rightBorder = k - 2;
while (k != p + 1) {
if (k < p + 1) {
right = p - 1;
} else if (k > p + 1) {
left = p + 1;
}
p = partition(arr, left, right);
if (p == leftBorder + 1) {
leftBorder = p;
}
if (p == rightBorder - 1) {
rightBorder = p;
}
}
quickSort(arr, leftBorder, rightBorder);
return arr[p];
}
public static void quickSort(int arr[], int left, int right) {
if (left >= right) return;
int q = partition(arr, left, right);
quickSort(arr, left, q - 1);
quickSort(arr, q + 1, right);
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int sortIndex = left;
for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
if (topBigK ? arr[arrIndex] > pivot : arr[arrIndex] < pivot) {
swap(arr, arrIndex, sortIndex);
sortIndex++;
}
}
swap(arr, sortIndex, right);
return sortIndex;
}
public static void swap(int[] arr, int i, int j) {
if (i == j) return;
int tmp = arr;
arr = arr[j];
arr[j] = tmp;
}
}
6666666666666666666666666666666666666
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) | 黑马程序员IT技术论坛 X3.2 |