A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 逆风TO 于 2020-4-8 14:23 编辑

在上一篇快速排序计算第K大的数中,我们解释了如何使用快排计算第K大的数,然后还发散思考了计算第K小的问题。在此基础上我们来想一下如何使用快排解决topK的问题。topK是很经典的面试题,在面试中会经常碰到,即使没有被问过,肯定也听说过。topK顾名思义就是在一组数据中排名前K的数。例如在 3, 2, 3, 1, 7, 4, 5, 5, 6 这组数中的 top3 就是求前3大的数(这里默认为是前K大的数),即 7,6,5。

上一篇中我们计算出了第K大的数,要想继续求出topK,只需要将1-K之间的数进行排序就行了,基于这个思路,我们得出了topK的第一个版本。

1.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[i]);
        }
        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[i];
        arr[i] = 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[i]);
        }
        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[i];
        arr[i] = 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[i]);
        }
        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[i];
        arr[i] = 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:
[Java] 纯文本查看 复制代码
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[i]);
        }
        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[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
 
 
}

这个版本的改动很简单,和上一篇一样,添加了 topBigK 作为标识可以用来求前K大的数或者前K小的数。将 topKSort 方法中的leftBorder ++ 和  rightBorder ++ 改成了 leftBorder = p 和 rightBorder = p ,效果是一样的。

总结:
无论是求第K个数还是求前K个数,它们和快速排序的契合度都很高,都可以在数据半排序的情况下得到结果。尤其是求第K个数,快排的每一次排序都会得到一个基准点,而基准点就是数组中某个数,可以说和快排完美匹配。在得到了第K个数之后,继续求前K个数就比较简单了,但是后续的也需要一定的算法基础。只有对排序的整个过程特别熟悉之后,才能在实现功能时做到最好,并进行一步步的优化和完善。


48 个回复

正序浏览
66666666666666666
回复 使用道具 举报
66666666666666666666666
回复 使用道具 举报
yujq 中级黑马 2020-4-24 12:39:43
47#
66666666666666666666666
回复 使用道具 举报
棒棒哒 ..................... ..................
回复 使用道具 举报
123123123123333333333333
回复 使用道具 举报
回复 使用道具 举报
受益匪浅
回复 使用道具 举报
感谢分享哦~
回复 使用道具 举报
66666666666666666666666666
回复 使用道具 举报
666666666666666666666666666
回复 使用道具 举报
谢谢分享,加油!~!!!~
回复 使用道具 举报
666666666666666666
回复 使用道具 举报
66666666666666
回复 使用道具 举报
感谢分享
回复 使用道具 举报
感谢分享哦~
回复 使用道具 举报
我爱我1022 来自手机 中级黑马 2020-4-23 18:11:18
34#
回复 使用道具 举报
小公举 来自手机 中级黑马 2020-4-23 17:58:09
33#
很受用,感谢了
回复 使用道具 举报
66666666666666666666666
回复 使用道具 举报
回复 使用道具 举报
123下一页
您需要登录后才可以回帖 登录 | 加入黑马