快速排序进阶：解决经典面试topK问题

深藏阁楼爱情的钟 2023-07-21 05:26 7阅读 0赞

在上一篇[快速排序计算第K大的数][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**： ##

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版本：

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： ##

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循环中，加了如下这段代码：

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的算法。

优化效果比较：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70][]         ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70 1][]

**优化前                                                                              ** **优化后**

左边这幅图是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[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个数就比较简单了，但是后续的也需要一定的算法基础。只有对排序的整个过程特别熟悉之后，才能在实现功能时做到最好，并进行一步步的优化和完善。

[K]: https://blog.csdn.net/Royal_lr/article/details/105074745
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200407153544459.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70 1]: /images/20230528/c3a31c748df3462a898e048353bdaef3.png