partition函数

这里的partition函数是快排使用的分区函数,即找一个pivot,使得分区后的元素左边都小于pivot,右边都大于pivot。

算法4提供的partition的实现比较长,容易写出bug。在这道题的评论中,yuanb10提供了一种简短的实现,可以在面试中很快的写出。

    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[hi];
        int i = lo;
        for (int j = lo; j < hi; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, hi);
        return i;
    }

使用场景:快排;Top k问题

pwrliang Uncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *