排序

比较排序

HeapSort

• 第一步：O(N)建立最大堆

• 第二步：不停地从最大堆中pop出根，in-place的话只需要O(N)的空间

class Solution:
    def heapify(self, nums, n, i):
        # heapify nums[:n] by sinking nums[i] to correct place
        largest = i
        l, r = 2*i+1, 2*i+2
        if l<n and nums[i]<nums[l]:
            largest = l
        if r<n and nums[largest]<nums[r]:
            largest = r
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
            self.heapify(nums, n, largest)
    
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n>>1, -1, -1):
            self.heapify(nums, n, i)
        
        for i in range(n-1, 0, -1):
            nums[i], nums[0] = nums[0], nums[i]
            self.heapify(nums, i, 0)
        return nums

# 偷懒写法：需要O(N)额外的空间
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        heapq.heapify(nums)
        res = []
        while nums:
            res.append(heapq.heappop(nums))
        return res

MergeSort

• 用分治思路

• 主要步骤分治后merge结果，需要O(N)的空间。也有in-place的一些方法

class Solution:
    def merge(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        res = [None for _ in range(m+n)]
        i = j = k = 0
        while i<m and j<n:
            n1, n2 = nums1[i], nums2[j]
            res[k] = min(n1, n2)
            k += 1
            if n1<n2:
                i += 1
            else:
                j += 1
        res[k:] = nums1[i:] if i<m else nums2[j:]
        return res
    
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1: return nums
        m = len(nums) >> 1
        return self.merge(self.sortArray(nums[:m]),
                          self.sortArray(nums[m:]))

QuickSort

• 自上而下的分治，没有divide & conquer之后的combine那一步

• 如果每一次partition都拿到最大的一个数，那么最坏的时间复杂度是O(N²)。平均复杂度一般为O(N)，而且用随机选择pivot的partition能够摊平时间复杂度。

Fixed Pivot

class Solution:
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
    
    def partition(self, nums, l, r):
        pivot = nums[l]
        j = l
        for i in range(l+1, r+1):
            if nums[i] < pivot:
                j += 1
                self.swap(nums, i, j)
        self.swap(nums, l, j)
        return j
    
    def sortArray(self, nums, l=0, r=None):
        if r==None: r = len(nums)-1
        if l<r:
            p = self.partition(nums, l, r)
            self.sortArray(nums, l, p-1)
            self.sortArray(nums, p+1, r)
        return nums

Random partition

class Solution:
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
    
    def partition(self, nums, l, r):
        pivot = nums[l]
        j = l
        for i in range(l+1, r+1):
            if nums[i] < pivot:
                j += 1
                self.swap(nums, i, j)
        self.swap(nums, l, j)
        return j
    
    def randomPartition(self, nums, l, r):
        i = random.randint(l, r)
        self.swap(nums, l, r)
        return self.partition(nums, l, r)
        
    def sortArray(self, nums, l=0, r=None):
        if r==None: r = len(nums)-1
        if l<r:
            p = self.randomPartition(nums, l, r)
            self.sortArray(nums, l, p-1)
            self.sortArray(nums, p+1, r)
        return nums

线性时间排序

Counting Sort

假设已知数据的所有可能

• 第一步：统计每个数字对应的cumulative count，即最后结果应该在的位置i.e. rank

• 第二步：在每一个rank的位置填入数字

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def index(i): return i-minval

        minval, maxval = min(nums), max(nums)
        c = [0 for _ in range(minval, maxval+1)]
        for n in nums:
            c[index(n)] += 1
        for i in range(1, len(c)):
            c[i] += c[i-1]

        res = [None for _ in range(len(nums))]
        for n in nums:
            res[c[index(n)]-1] = n
            c[index(n)] -= 1
        return res

BucketSort

假设数据的范围，而且分布是均匀的，可以用桶排序。这里选择的数据范围根据例题。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        OFFSET = 50000
        STEP = 1000
        
        n = len(nums)
        for i in range(n):
            nums[i] += OFFSET
        
        nBuckets = max(nums) // STEP
        buckets = [[] for _ in range(nBuckets+1)]
        for n in nums:
            index = n // STEP
            buckets[index].append(n)
        
        for b in buckets:
            b.sort()
        
        return [x-OFFSET for b in buckets for x in b]