Partition算法详解

partition算法有着非常重要的应用，这个算法的思想虽然简单，但具体实现的细节却比较多，今天我重点复习了这个算法，本文记录我对这个算法的理解。

Partition算法解析

二分Partition

快速排序作为非常著名的排序算法，其思想却很简单：每次从数组中选一个数作为pivot，然后将数组划分为2部分，小于等于pivot数的在其左边，大于等于pivot的数在其右边，然后分别对pivot的左边和右边进行递归。
二分partition的实现用到了双指针，left寻找一个比pivot大的数，right寻找一个比pivot小的数，然后交换它们，循环这一过程直到left == right，将pivot放到这个位置。
注意: 如果pivot选的是最左的元素，则要先移动right；如果pivot选的是最右的元素，则要先移动left。

int partition(vector<int>& nums, int left, int right) {
   
    int pivot = nums[left], base = left;
    while (left < right) {
   
        while (left < right && nums[right] >= pivot) right--;
        while (left < right && nums[left] <= pivot) left++;
        swap(nums[left], nums[right]);
    }
    nums[base] = nums[left];
    nums[left] = pivot;
    return left;
}
<

最后

以上就是忧郁蜡烛为你收集整理的Partition算法详解的全部内容，希望文章能够帮你解决Partition算法详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。