Sorting

1. 经典排序算法

Quick Sort

def QuickSort(A, start, end):
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quickSort(A, start, end):
            if start >= end:
                return
            left, right = start, end
            pivot = A[(start + end) // 2]
            while left <= right:    # 必须是<=以防止死循环
                while left <= right and A[left] < pivot:  #必须是<
                    left += 1
                while left <= right and A[right] > pivot:   #必须是<
                    right -= 1
                if left <= right:
                    A[left], A[right] = A[right], A[left]
                    left += 1
                    right -= 1
            # print(A, start, end, left, right)
            quickSort(A, start, right)
            quickSort(A, left, end)


        quickSort(nums, 0, len(nums) - 1)
        return nums

Merge Sort

        def mergeSort(nums):
            def merge(left_part, right_part, nums):
                i, j = 0, 0
                n1, n2 = len(left_part) - 1, len(right_part) - 1
                for w in range(len(nums)):
                    if j > n2 or (i <= n1 and left_part[i] < right_part[j]):
                        nums[w] = left_part[i] 
                        i += 1
                    elif i > n1 or (j <= n2 and left_part[i] >= right_part[j]):
                        nums[w] = right_part[j]
                        j += 1

            if len(nums) < 2:
                return nums
            mid = (len(nums) - 1)// 2
            left_part = nums[:mid + 1][:]
            right_part = nums[mid + 1:][:]
            mergeSort(left_part)
            mergeSort(right_part)
            merge(left_part, right_part, nums)

主要先将nums的左右两边分别复制到新数组，排序好后，再在原数组合并；或者在原数组左右分别排序，在新数组合并，在复制回原数组

Quick Select

        def quickSelect(lo_orig,hi_orig):
            if lo_orig >= hi_orig:
                return
            lo, hi = lo_orig,hi_orig
            pivot = arr[(lo + hi) // 2][0]
            while lo <= hi:
                while lo <= hi and arr[lo][0] > pivot:
                    lo += 1
                while lo <= hi and arr[hi][0] < pivot:
                    hi -= 1
                if lo <= hi:
                    arr[lo], arr[hi] = arr[hi], arr[lo]
                    lo += 1
                    hi -= 1
            if hi == k - 1: # 只考虑lower bound
                return
            elif hi > k - 1:
                quickSelect(lo_orig, hi)
            else:
                quickSelect(lo, hi_orig)

215. Kth Largest Element in an Array 912. Sort an Arrayquick sort 会tle， merge sort通过
347. Top K Frequent Elements

2. Perform sorting on multi-dim array based on one dimension.

The code to compare in python3:

// Python3 中compare func必须返回1/0/-1，而非boolean
def comparison_func(Interval &a, Interval &b):
    if a.start < b.start:
        return 1
    elif a.start > b.start:
        return -1
    else:
        return 0

sort(intervals.begin(), intervals.end(), key = itertools.cmp_to_key(comparison_func));
或sort(intervals.begin(), intervals.end(), key = lambda x: x.start);

Merge Intervals This is not as hard as it seems. Not even using divide and conquer. Just sort the element by the first value, and visit each element one by one. if the next start is smaller than the current end, then update end. otherwise, create new interval.

Meeting Rooms II Use a min heap to keep track the open rooms and each meeting end time.

3. Tri-Partition Problem

This is the famous Dutch Flag Problem, by keeping the lower, upper and curr pointer. All elements on the left of lower and right of upper has been visited and positioned, what is left to do is swap(lower, curr) if curr < mid; swap(lower, upper) if curr > mid; else curr++.

Wiggle Sort II I spent almost two half days on this question, still cannot understand the solution using the tri-partition method. To be further investigated.

• In C++, the data structure to keep track of a sorted rolling window is through "multiset", which is implemented through a self-balanced tree(Red Black Tree).

leetcode #75 Sort Colorstwo pointers from the two ends of the array, swapping elements when necessary, until they meet.

4. Merge Sort

Merge Sorted Array

5. Bucket Sort

220. Contains Duplicate III将num依照bucketSize=valueDiff+1放入bucket中，则num只可能与其左右两个bucket以及其自己中的元素组成pair，遍历num的同时将左边过期的bucket id 从bucket中剔除； bucket[id]中存num，因为若bucket[id]中已经有元素，那么就已经组成了pair\

Top K Frequent Elements First, create the hash table with element as the key, and count as the value; then convert it to a second hash table(bucket), with count as key. Then reversely visit the bucket add element to the res one by one, until the size is k.

Sort Characters By Frequency Create the character-freq map, and then create freq-chars map. Read map from largest to smallest, append to new string.

contains-duplicate-iii

each bucket stores [t * (i - 1), t * i], and maintaining a rolling buckets.

minimum-time-difference

have a time to min function and have a 1440 buckets.

6. Heap Sort

Kth Largest Element in an Array Although famous for sorting by random partition.