399. Nuts & Bolts Problem

#meat
quick sort  #quicksort 思想.
任选一个数, 作为 pivot, 用 compare.cmp(a, b) 来 partition nuts and bolts 数组.
记录 pivot 位置 mid, [start, mid - 1], [mid + 1, end] 分成上半区和下半区, 递归, 排序.
    self.qsort(A, start, mid - 1)
    self.qsort(A, mid + 1, end)

递归出口: start >= end

有三种方法 partition.

way 1: 用两个辅助数组帮助完成分区 partition. 类似 merge sort 里面的 merge.

封装 partition(A, start, end):
pivot = A[start] # 通常情况,
pivot = A[i] if compare.cmp(A[i], B[start]) == 0; # 本题特别要求的比较查找.

low, high = [], []
比 pivot 小的数放进 low 数组, # if compare.cmp(A[i], B[start]) == -1:
比 pivot 大的数放进 high 数组, # if .. cmp() == 1:
A[start: end + 1] = low + [pivot] + high # 完成分区子数组,放回原区间.
mid = start + len(low)
return mid, 即分区中轴线.

note, mid = start + len(low_arr), 记得加上基准位置 start.

way 2: 类似 0,1,2 三色排序.

def partition(A, start, end):
区间第一个数 A[start] 作为 pivot.
左右指针 l, r = start + 1, end;
while l <= r: # 小于等于, 有等于, l 和 r 重合, 确保处理最后一个元素 r.
- 小于 pivot 的数在左指针 l 前边,
- 大于 pivot 的数在右指针 r 后边,
循环结束后, 交换 start, r 的数值, r 就是完成分区的中轴线, 左边小, 右边大.
返回 r , 即分区中轴线.

优点, 知道 pivot 的位置. mid - 1, mid + 1 两边递归.
缺点, 分区有等于条件, 极端情况每次走到尾, O(n^2) time.
 - i.e. [1,1,1,1,1,1,1,1,1], 每次分区只减少一个数, 不能两边均分, 大于 O(n log n) time.

def qsort(self, A, start, end):
    if start >= end:
        return
    mid = self.partition(A, start, end)
    self.qsort(A, start, mid - 1)
    self.qsort(A, mid + 1, end)

def partition(self, A, start, end):
    pivot = A[start]
    l, r = start + 1, end
    while l <= r:
        if A[l] <= pivot: # l 前边小于等于 pivot
            l += 1
        else: # A[l] > pivot: r 后边大于 pivot
            A[l], A[r] = A[r], A[l]
            r -= 1
    A[start], A[r] = A[r], A[start]
    return r

way 3: 中间数作为 pivot, 左右向中间逼近. - 九章算法班.
mid = (start + end)//2
pivot = A[mid]
l, r = start, end
while l <= r:
  while l <= r and A[l] < pivot:
    l += 1
  while l <= r and A[r] > pivot:
    r -= 1
  if l <= r:
    A[l], A[r] = A[r], A[l]
    l += 1
    r -= 1

最后 r 移到了 l 的前边/左边. A[start: r + 1] 小于等于中轴, A[l: end + 1] 大于等于中轴, 完成分区.
缺点: 不知道 pivot 的位置, 不知道 r, l 中间有没有 mid.
有一个迂回办法 workaround 就是用第1个数作为中轴 pivot，然后 partition 后边的,完成分区后右指针和第1个数交换,右指针的位置就是分区后的中轴线。
.



"""
class Comparator:
    def cmp(self, a, b)
You can use Compare.cmp(a, b) to compare nuts "a" and bolts "b",
if "a" is bigger than "b", it will return 1, else if they are equal,
it will return 0, else if "a" is smaller than "b", it will return -1.
When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
"""


class Solution:
    # @param nuts: a list of integers
    # @param bolts: a list of integers
    # @param compare: a instance of Comparator
    # @return: nothing
    def sortNutsAndBolts(self, nuts, bolts, compare):
        self.q_sort(nuts, bolts, compare, 0, len(nuts) - 1)
        print(nuts, bolts)

    def q_sort(self, A, B, compare, start, end):
        # print(f"start {start}, end {end}")
        if start >= end:
            return
        mid = (start + end)//2
        new_mid_i = self.partition(A, B, compare, start, end)
        # print(f"start {start}, mid {mid}, end {end}", "new_mid_i:", new_mid_i)

        self.q_sort(A, B, compare, start, new_mid_i - 1)
        self.q_sort(A, B, compare, new_mid_i + 1, end)

    def partition(self, A, B, compare, start, end):
        lo, hi, mi = [], [], []
        mid = (start + end)//2
        # print(A[start: end + 1])
        # print(B[start: end + 1])
        b_mid = B[mid]
        for v in A[start: end + 1]:
            if compare.cmp(v, b_mid) == -1:
                lo.append(v)
            elif compare.cmp(v, b_mid) == 0:
                mi.append(v)
                a_mid = v
            else:
                hi.append(v)
        # print("a,b mid:", a_mid, b_mid)
        # print("lo,mi,hi", lo, mi, hi)
        new_mid_i = start + len(lo)
        i = start
        for v in lo + mi + hi:
            A[i] = v
            i += 1

        lo, hi, mi = [], [], []
        for v in B[start: end + 1]:
            if compare.cmp(a_mid, v) == 1:
                lo.append(v)
            elif compare.cmp(a_mid, v) == 0:
                mi.append(v)
            else:
                hi.append(v)
        # print("lo,mi,hi", lo, mi, hi)
        i = start
        for v in lo + mi + hi:
            B[i] = v
            i += 1
        # print("after partition:")
        # print(A[start: end + 1])
        # print(B[start: end + 1])
        return new_mid_i