912. Sort an Array

https://leetcode.com/problems/sort-an-array/

solution

• 插入排序: 算法导论中的扑克牌插入，相邻比较

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums

        for i in range(1, len(nums)):
            j = i
            while j > 0 and nums[j] < nums[j-1]:  # 倒序
                nums[j-1], nums[j] = nums[j], nums[j-1]
                j -= 1
        return nums

时间复杂度：O(n^2) 空间复杂度：O(n)

递归写法

def insert_sort_rec(list, m):
    if m == 0:
        return
    mmax = m
    for i in range(m):
        if list[i] > list[mmax]:
            mmax = i
    list[m], list[mmax] = list[mmax], list[m]
    insert_sort_rec(list, m - 1)

• 冒泡排序: 两层for循环，相邻比较

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            for j in range(len(nums) - i - 1):  # 这里注意
                if nums[j] > nums[j+1]:
                    nums[j+1], nums[j] = nums[j], nums[j+1]
        return nums

时间复杂度：O(n^2) 空间复杂度：O(n)

• 归并排序

  • 树的后序遍历

  • divide & conquer: top down & bottom up

  • 排序的稳定性问题

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        l = 0
        r = len(nums) - 1
        self.merge_sort(nums, l, r)
        return nums

    def merge_sort(self, nums, l, r):
        if l < r:  # 注意是if
            mid = l + (r - l) // 2
            self.merge_sort(nums, l, mid)
            self.merge_sort(nums, mid+1, r)
            self.merge(nums, l, mid, r)

    def merge(self, nums, l, mid, r):
        pass

时间复杂度：O(nlog(n)) 空间复杂度：O(n)

def merge(lista, listb):
    output = []
    i, j = 0, 0
    while i < len(lista) and j < len(listb):
        if lista[i] > listb[j]:
            output.append(listb[j])
            j += 1
        else:
            output.append(lista[i])
            i += 1
    if i < len(lista):
        output += lista[i:]
    if j < len(listb):
        output += listb[j:]
    return output

def merge_sort(list):
    if len(list) <= 1:
        return list
    mid = len(list)//2
    return merge(merge_sort(list[:mid]), merge_sort(list[mid:]))

print(merge_sort([5,1,2,4,6,3]))

• 快速排序

  • 树的前序遍历

  • average O(nlog(n)) 最好O(1) 最差O(n^2)

  • 注意左闭右开/左闭右闭的统一

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        l = 0
        r = len(nums) - 1
        self.quick_sort(nums, l, r)
        return nums

    def quick_sort(self, nums, l, r):
        if l < r:  # 注意这里是if, 不是while
            p = self.partition(nums, l , r)
            self.quick_sort(nums, l, p - 1)
            self.quick_sort(nums, p + 1, r)

    def partition(self, nums, l, r):
        pivot = nums[r]
        i = l  # 第一个比pivot大的位置
        for j in range(l, r):
            if nums[j] <= pivot:  # 比较之后, 互换该位置和i位置的值
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i

时间复杂度：average O(nlog(n)) 最好O(1) 最差O(n^2) 空间复杂度：O(n)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick_sort(nums):
            if len(nums) <= 1:
                return nums

            left, equal, right = [], [], []
            pivot = random.choice(nums)
            for i in range(len(nums)):
                if nums[i] < pivot:
                    left.append(nums[i])
                elif nums[i] > pivot:
                    right.append(nums[i])
                else:
                    equal.append(nums[i])
            return quick_sort(left) + equal + quick_sort(right)
        return quick_sort(nums)

def partition(list, l, r):
    # 在list中[p, r]区间返回*位置*i，左边都小于list[i]，右边都大于list[i]
    key = list[r]  # 最后一个作为pivot
    i = l  # 分隔小于和大于key的位置, 也就是j循环之前第一个大于key的位置
    for j in range(l, r):
        if list[j] <= key:
            list[i], list[j] = list[j], list[i]
            i = i + 1
    list[i], list[r] = list[r], list[i]
    return i

def quick_sort_op(list, l, r):
    if l < r:
        q = partition(list, l, r)
        quick_sort_op(list, l, q - 1)
        quick_sort_op(list, q + 1, r)

list = [5, 2, 1, 4, 6, 3]
quick_sort_op(list, 0, len(list)-1)
print(list)

• 堆排序

# https://stackoverflow.com/questions/13979714/heap-sort-how-to-sort

def max_heapify(list, end, i):
    l = 2 * i + 1
    r = 2 * (i + 1)
    max = i
    if l < end and list[i] < list[l]:
        max = l
    if r < end and list[max] < list[r]:
        max = r
    if max != i:
        list[i], list[max] = list[max], list[i]
        max_heapify(list, end, max)

def heap_sort(list):
    end = len(list)
    start = end // 2 + 1
    for i in range(start, -1, -1):
        max_heapify(list, end, i)
    for i in range(end-1, 0, -1):
        list[i], list[0] = list[0], list[i]
        max_heapify(list, i, 0)

list = [2, 7, 1, -2, 56, 5, 3]
heap_sort(list)
print(list)

时间复杂度：O(nlog(n)) 空间复杂度：O(n)

• 桶排序

  • 为每个值设立一个桶，桶内记录这个值出现的次数或其它属性，然后对桶进行排序

时间复杂度：O() 空间复杂度：O()

• 计数排序

follow up

148. Sort List

75. Sort Colors

791. Custom Sort String

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        order_dict = {char: i for i, char in enumerate(order)}
        s = sorted(s, key=lambda x: order_dict.get(x, 0))  # x.sort() 只支持list?
        return "".join(s)  # sort生成之后生成的是list

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        res = ""
        counter = collections.defaultdict(int)

        for char in s:
            counter[char] += 1

        for char in order:
            if char in counter:
                res += char * counter[char]
                del counter[char]

        # 剩余字母
        for char, count in counter.items():
            res += char * count
        return res

147. Insertion Sort List

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        prev = dummy

        while head:
            nex = head.next
            if prev.val >= head.val:  # 如果prev本身已经比head大, 不必回到最前面。给head找的位置本身就是第一个比head大的位置
                prev = dummy

            while prev.next and prev.next.val < head.val:
                prev = prev.next

            head.next = prev.next  # 在prev和prev.next中插入head
            prev.next = head

            head = nex
        return dummy.next

386. Lexicographical Numbers