1.冒泡排序

这个so easy，就是不断比较相邻的两个数字，if 后面比前面大，就exchange一下

代码

# 每一次冒泡会把最大的元素放到最后，
# 也就是第1次冒泡把最大的放在n-1的位置
# 那第n-1次冒泡就是把这一轮的最大值放在n-（n-1）= 1的地方，
# 也就是说冒泡到第n-1次return的位置是lst[1]
# which means 在第n-1次冒泡的时候只剩下lst[0]和lst[1]，已经是有序的了，
# range函数取不到右边界
def bubble(lst):
    if lst:
        for j in range(len(lst) - 1):
            # 定义一个布尔值来判断本轮有没有交换
            swapped = False
            for i in range(len(lst) - 1 - j):
                if lst[i] > lst[i + 1]:
                    lst[i], lst[i + 1] = lst[i + 1], lst[i]
                    swapped = True
            # if 没交换，就已经sorted，所以退出
            if not swapped:
                break
    return lst


nums = [4, 2, 6, 3, 4, 6, 2, 1]
x = bubble(nums)
print(x)

但是这个算法呢，分析一下复杂度，最坏的情况下要进行 （n - 1）* （n - 1) 次。

时间复杂度是O(n^2)，就很大，所以不是很好。

空间复杂度是O(n)

2.插入排序

假设我们要对一个列表 lst排序：

1. 将列表分为两部分：

   • 已排序区间：从索引 0 到 i-1

   • 未排序区间：从索引 i 到 n-1

2. 每次取出未排序区间的第一个元素（即 lst[i]），
   然后向左扫描，找到它在已排序区间中的正确位置并插入。

3. 重复该过程，直到所有元素都被插入到已排序区间。

代码

def insert_sorting(lst):
    for i in range(1, len(lst)):
        key = lst[i]  # 暂存要插入的元素
        j = i - 1
        # find the place for the current element
        while j >= 0 and lst[j] >= key:
            lst[j + 1] = lst[j]
            j -= 1

        lst[j + 1] = key

    return lst


nums = [4, 2, 6, 3, 4, 6, 2, 1]
y = insert_sorting(nums)
print(y)

3，合并排序

这个看图就很直观了

代码

def merge_sort(lst):

    # empty ---> break
    if not lst:
        return
    # basecase
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2

    left = lst[:mid]
    right = lst[mid:]

    sub_left = merge_sort(left)
    sub_right = merge_sort(right)

    sorted_nums = merge(sub_left, sub_right)

    return sorted_nums


def merge(left, right):
    merged = []

    i, j = 0, 0

    while i < len(left) and j < len(right):

        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # 但是循环结束的时候，必然有一个列表先被耗尽
    # 这里的_left是剩下的意思,我想不到别的名字了
    left_left = left[i:]
    right_left = right[j:]

    return merged + left_left + right_left


# test merge
# print(merge([1, 4, 7, 9, 11], [-1, 0, 2, 3, 8, 12]))
nums = [5, -12, 2, 6, 1, 23, 7, 7, -12, 6, 12, 1, -243, 1, 0]
print(merge_sort(nums))

4. 快速排序

快速排序的核心思想是：

1. 选择基准（Pivot）
   从数组中选择一个元素作为基准（可以是第一个、最后一个、中间或者随机选取）。

2. 分区（Partition）
   将数组重新排列，使得：

   • 所有小于基准的元素都在基准的左边

   • 所有大于基准的元素都在基准的右边
     分区完成后，基准元素就处于最终位置。

3. 递归排序子数组
   分别对基准左边和右边的子数组重复上述步骤，直到子数组长度为 0 或 1。

def quick_sort(lst):
    if len(lst) <= 1:
        return lst

    pivot = lst[0]

    left = [x for x in lst[1:] if x <= pivot]
    right = [y for y in lst[1:] if y > pivot]

    return quick_sort(left) + pivot + quick_sort(right)

但是递归排序面临比较大的list时比较浪费空间，所以有另一种快排方法。

就地快排

是为了给pivot找到绝对正确的位置

def find_pivot(lst, left=0, right=None):
    if right is None:
        right = len(lst) - 1
    # left is pivot
    # l and r are pointers/flags
    pivot = lst[left]
    l, r = left + 1, right
    print('pivot:', pivot, '\n')

    while l <= r:
        print('l:', l, 'r:', r, 'nums:', lst)
        if lst[r] < pivot and lst[l] > pivot:
            print('exchange list[l] and list[r]', lst)
            lst[l], lst[r] = lst[r], lst[l]
        # 从右向左移动右指针
        elif lst[r] >= lst[left]:
            r -= 1
            print('r continue move, r point to:', lst[r], '\n')
        elif lst[l] <= lst[left]:
            l += 1
            print('l continue move, l point to:', lst[l], '\n')
    lst[left], lst[r] = lst[r], lst[left]
    print('currern list is:', lst)

    return r

上面这个代码是我第一次写的，看起来可以执行成功，也确实执行成功了，

仔细分析一下，其实 while 里面的if语句逻辑是有问题的。

如果 r 指向的值 >= pivot，立即左移 r
否则如果 l 指向的值 <= pivot，立即右移 l
否则才交换


而每一次if条件为真后都会break当下的进程

下面的代码会更加符合逻辑：

不断让 l 右移直到出现 > pivot 的值
不断让 r 左移直到出现 < pivot 的值
此时交换 l 和 r
继续循环
最后交换 pivot 和 r

代码

def quick_inplace(lst, left=0, right=None):

    if right is None:
        right = len(lst) - 1

    if left < right:
        pivot = find_pivot(lst, left, right)
        quick_inplace(lst, left, pivot - 1)
        quick_inplace(lst, pivot + 1, right)

    return lst


def find_pivot(lst, left=0, right=None):
    if right is None:
        right = len(lst) - 1
    # left is pivot
    # l and r are pointers/flags
    pivot = lst[left]
    l, r = left + 1, right
    print('pivot:', pivot, '\n')

    while l <= r:
        # 不断向左推进右指针,直到找到第一个比pivot小的,break while return l and r
        while l <= r and lst[r] >= pivot:
            r -= 1
        while l <= r and lst[l] <= pivot:
            l += 1
        if l < r:
            print('exchange list[l] and list[r]', lst)
            lst[l], lst[r] = lst[r], lst[l]

    lst[left], lst[r] = lst[r], lst[left]

    return r


nums =  [6, 3, 8, 5, 2, 7, 4]
print(quick_inplace(nums))