排序：冒泡、选择、归并、快排

# 冒泡排序，时间复杂度 O(n^2)，空间复杂度 O(1)
def bubble_sort(nums):
    for i in range(len(nums)):
        for j in range(len(nums)-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

# 冒泡排序优化，时间复杂度 O(n^2)，空间复杂度 O(1)
def bubble_sort_1(nums):
    for i in range(len(nums)):
        swapped = False
        for j in range(len(nums)-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = True
        if swapped == False:
            break
    return nums

# 选择排序，时间复杂度 O(n^2)，空间复杂度 O(1)
def select_sort(nums):
    for i in range(len(nums)-1):
        min_idx = i
        for j in range(i+1, len(nums)):
            if nums[j] < nums[min_idx]:
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

# 归并排序，时间复杂度 O(nlogn)，空间复杂度 O(n)
def merge_sort(nums):
    if len(nums) <= 1:
        return nums

    mid = len(nums)//2
    L, R = nums[:mid], nums[mid:]
    merge_sort(L)
    merge_sort(R)
    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            nums[k] = L[i]
            i += 1
        else:
            nums[k] = R[j]
            j += 1
        k += 1

    while i < len(L):
        nums[k] = L[i]
        i, k = i+1, k+1
    while j < len(R):
        nums[k] = R[j]
        j, k = j+1, k+1

    return nums

# 快速排序，时间复杂度 O(nlogn)，空间复杂度 O(logn)
def quick_sort(nums):

    def partition(nums, p, r):
        pivot = nums[r]
        i = p - 1
        for k in range(p, r):
            if nums[k] <= pivot:
                i += 1
                nums[i], nums[k] = nums[k], nums[i]
        nums[i+1], nums[r] = nums[r], nums[i+1]
        return i+1

    def _quick_sort(nums, p, r):
        if p < r:
            q = partition(nums, p, r)
            _quick_sort(nums, p, q-1)
            _quick_sort(nums, q+1, r)

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

test_case = [
    [],
    [0],
    [9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
    [0, 1, 2, 3, 4, 9, 8, 7, 6, 5],

]

for l in test_case:
    merge_sort(l)
    print(l)
meishaoming / blog

排序：冒泡、选择、归并、快排 #90
