class Solution:
    def insertionSort(self, l):
        sortedList = [] # 左手
        for item in l: # 右手从牌堆里一张一张拿牌
            itemIndex = len(sortedList) # 新牌一开始放在左手牌堆的最右边
            for index in range(len(sortedList) - 1, -1, -1): # 从右往左一张一张比较。注意这里隐含了左边没牌的情况
                if sortedList[index] > item: # 左边牌比新牌大
                    itemIndex = itemIndex - 1 # 新牌左移一格
                else: # 左边牌比新牌小或者一样大
                    break # 新牌不动
            sortedList.insert(itemIndex, item) # 插入新牌
        return sortedList

Solution().insertionSort([1, 3, 2, 5, -1])

[-1, 1, 2, 3, 5]

class Solution:
    def mergeSort(self, l):
        
        def _merge(l1, l2): # 定义一个合并函数，输入两个各自排好序的列表，输出它们合并后的、排好序的列表
            l = []
            while (l1 != []) and (l2 != []): # 牌堆1和牌堆2都有牌
                if l1[0] > l2[0]: # 当牌堆1最左边的牌大于牌堆2最左边的牌
                    l.append(l2.pop(0)) # 抽出牌堆2最左边的牌，放到左手边牌堆的最右端
                else:
                    l.append(l1.pop(0)) # 抽出牌堆1最左边的牌，放到左手边牌堆的最右端
            if l1 == []: # 牌堆1没牌了
                l.extend(l2) # 把牌堆2的所有牌整个原封不动放到左边牌堆的最右端
            else: # 牌堆2没牌了
                l.extend(l1) # 把牌堆1的所有牌整个原封不动放到左边牌堆的最右端
            return l
        
        sortedPiles = [[i] for i in l] # 把所有n张牌分成n堆，每堆一张牌
        while len(sortedPiles) != 1: # 桌上没有形成完整的1个牌堆
#             print(sortedPiles)
            if len(sortedPiles) % 2 == 0: # 桌上牌堆的数量是偶数，可以两两合并
                sortedPiles = [_merge(sortedPiles[2 * i], sortedPiles[2 * i + 1]) for i in range(0, len(sortedPiles) // 2)]
            else: # 桌上牌堆的数量是奇数，前面的可以两两合并；最后一堆只能放着，下一次再排
                sortedPiles = [_merge(sortedPiles[2 * i], sortedPiles[2 * i + 1]) for i in range(0, len(sortedPiles) // 2)] + sortedPiles[-1:]
        return sortedPiles[0]

Solution().mergeSort([1, 3, 2, 5, -1])

[-1, 1, 2, 3, 5]

class Solution:
    def quickSort(self, l):
        if len(l) in (0, 1): # 如果传进来的数组是空的（没有数比基准数大），或者只有一个
            return l # 那就不用排序
        elif len(l) == 2: # 如果有两个
            if l[0] <= l[1]: # 并且如果已经排好序了
                return l # 也不用排序
            else: # 但是如果倒序
                return [l[1], l[0]] # 就要排好再返回

        temp = [l[-1]] # 如果数组长度大于等于3
        pos = 0 # 这个变量用于记录基准数的index
        for i in l[0: -1]: # 逐个比较
            if i <= l[-1]: # 遇到比基准数小的或相等的
                temp.insert(0, i) # 就放到前面
                pos += 1 # 基准数的index增加1
            else: # 遇到比基准数大的
                temp.append(i) # 放到基准数后面，同时基准数index不用增加
                
        temp[0: pos] = self.quickSort(temp[0: pos]) # 把基准数前面的子数组排一遍
        temp[pos + 1:] = self.quickSort(temp[pos + 1:]) # 把基准数后面的子数组排一遍
        return temp

Solution().quickSort([1, 3, 2, 5])

[1, 2, 3, 5]

def f(l):
    l.reverse()
    
a = [1, 2, 3, 4]
f(a)
print(a) # 当然是[4, 3, 2, 1]

f(a[0: 2])
print(a) # 你可能会期待看到[3, 4, 2, 1]

f(a[:])
print(a) # 你可能会期待看到[1, 2, 4, 3]

[4, 3, 2, 1]
[4, 3, 2, 1]
[4, 3, 2, 1]

class Solution:
    def countingSort(self, l):
        if not l:
            return l
        counter = {} # 直方图，也可以叫计频器
        minimum = l[0] # 最小的数字
        maximum = l[0] # 最大的数字
        for value in l: # 一遍迭代就可以得到直方图、最大数、最小数
            if value < minimum:
                minimum = value
            if value > maximum:
                maximum = value # 一边遍历一边得到最小最大值，可以省时间
            counter[value] = counter.get(value, 0) + 1 # 直方图生成中
        # 该吐数据了
        sortedList = []
        for value in range(minimum, maximum + 1): # 从最小值到最大值
            for times in range(counter.get(value, 0)): # 吐数字，它出现几次就吐几个
                sortedList.append(value)
        return sortedList

Solution().countingSort([2, 5, 3, 0, 2, 3, 0, 3])

[0, 0, 2, 2, 3, 3, 3, 5]

Introduction to Algorithms¶

Foundation¶

Getting Started¶

Insertion sort¶

证明算法正确性的方法¶

分析算法的代价¶

分治法¶

Merge sort¶

Growth of Functions¶

Divide and Conquer¶

Maximum subarray problem¶

Strassen's algorithm for matrix multiplication¶

递归时间复杂度怎么算¶

Probabilistic Analysis and Randomized Algorithms¶

The hiring problem¶

Sorting and Order Statistics¶

Heapsort¶

把乱序数组变成堆¶

堆维护¶

Quicksort¶

Sorting in Linear Time¶

Counting sort¶

Radix sort¶