Partition的两种写法

快排中核心的方法应该算是Partition函数了，它的作用就是将整个数组分成小于基准值的左边，和大于基准值的右边。

定义函数签名

1	def partition(array, l, r)

表示按照array[l]的值，把数组中索引从l到r的部分的元素小于array[l]放在其左边，大于array[l]放在其右边。
为了代码的可读性，定义交换数组中交换两个位置的元素的工具函数（虽然用python写起来也非常方便）

1 2	def swap(array, l, r): array[l], array[r] = array[r], array[l]

最常见的写法:

用两个指针l和r，一个指向头，一个指向尾，将头指针移动到第一个不满足A[l]=k的数，交换两个数，然后重复往下查找不满足A[l]=k的数，继续交换。直到两指针相撞

def partition(array, l, r):
    key = array[l]
    while l < r:
        while array[r] > key and r > l:
            r -= 1
        while array[l] < key and r > l:
            l += 1
        swap(array, l, r)
    array[r] = key
    return r

第二种方法

定义数组中(l-1, small][注：这里的(]表示左开右闭区间，即不包括l-1位置的元素，包括small位置的元素]的区域为比key小的数，[big, r+1)[注：左闭右开]的区域为比key大的数，开始时两个区域中都没有数，将small初始化为l-1, big初始化为r+1。定义cur指针，指向当前遍历元素。当当前元素比key小时，将当前元素交换到small的右边，然后左边区域向右扩大一个，即small加1；当当前元素比key大时，将当前元素交换到big的左边，然后右边区域向左扩大一个，即big减一。函数最后返回划分完成之后第一个和最后一个等于key的元素的索引。

def partition(array, l, r):
    key = array[l]
    small = l - 1
    cur = l
    big = r + 1
    while cur != big:
        if array[cur] < key:
            small += 1
            swap(array, small, cur)
            cur += 1
        elif array[cur] > key:
            big -= 1
            swap(array, cur, big)
        else:
            cur += 1
    return small+1, big-1

应用

在数组中找到第k大的元素
思路： 每次把一个元素交换到正确的位置，同时把左边的都放上大的，右边都放上小的。这个算法每一次选取一个枢纽元，排序之后，查看枢纽元的位置。如果它的位置大于K，就说明，要求出前面一个子序列的第K大的元素。反之，如果小于K，就说明要求出在后面一个序列的第K - 前一个序列的长度个元素。
注意，与快排不同的是，这个算法的时间复杂度是O(N)，因为第一次交换，算法复杂度为O(N)，接下来的过程和快速排序不同，快速排序是要继续处理两边的数据，再合并，合并操作的算法复杂度是O(1)，于是总的算法复杂度是O(N*logN)（可以这么理解，每次交换用了N，一共logN次）。但是这里在确定枢纽元的相对位置（在K的左边或者右边）之后不用再对剩下的一半进行处理。也就是说第二次插入的算法复杂度不再是O(N)而是O(N/2)，这不还是一样吗？其实不一样，因为接下来的过程是1+1/2+1/4+........ < 2，换句话说就是一共是O(2N)的算法复杂度也就是O(N)的算法复杂度。

def kthLargestElement(k, nums):
    l, r = 0, len(nums)-1
    while True:
        ll, rr = partition(nums, l, r)
        if ll <= k - 1 <= rr:
            return nums[ll]
        elif k > rr:
            l = rr + 1
        else:
            r = ll - 1

数组划分

Partition的两种写法

最常见的写法:

第二种方法

应用