排序算法

排序算法是常练常新

选择

选择排序

# 1. 将索引位置 0 定义为最小的值 min_idx
# 2. 遍历数组，找到数组中最小的值
# 3. 在遍历的时候，如果找到任何小于 min_idx 的元素，则交换两个值
# 4. 移动 min_idx 指针
# 5. 重复上述动作直到数组排序完成

test_list = [64, 25, 12, 22, 11]
print(test_list)


def select_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr


select_sort(arr=test_list)

print(test_list)

冒泡

冒泡排序

# 1. 通过两个变量，i 和 j，跑两个嵌套循环遍历数组
# 2. if arr[i] > arr[j] 交换相邻元素


def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr) - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


result = bubble_sort([3, 5, 1, 6, 9, 2, 4, 7])
print(result)

插入

插入

# 1. 循环遍历数组 arr
# 2. 比较当前元素和其前身
# 3. 如果当前元素小于其前身，则将其与之前的元素进行比较。将较大的元素向后移动一个位置


def insert_sort(arr):
    for i in range(len(arr)):
        cur = arr[i]  # 指定当前元素
        j = i - 1
        # 当前元素和其前身比较
        while j >= 0 and arr[j] > cur:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = cur
    return arr


result = insert_sort([2, 5, 1, 7, 8, 3, 4, 6])
print(result)

147. 对链表进行插入排序

147. 对链表进行插入排序

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return head

        dummy = ListNode(0)
        dummy.next = head
        last_sorted = head
        cur = head.next
        while cur:
            if last_sorted.val <= cur.val:
                last_sorted = last_sorted.next
            else:
                prev = dummy
                while prev.next.val <= cur.val:
                    prev = prev.next
                last_sorted.next = cur.next
                cur.next = prev.next
                prev.next = cur
            cur = last_sorted.next
        return dummy.next

归并

分治的思路

归并

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result


def merge_sort(arr):
    if len(arr) < 2:
        return arr
    mid = 0 + ((len(arr) - 0) >> 1)
    left = arr[:mid]
    right = arr[mid:]
    return merge(merge_sort(left), merge_sort(right))


xxx = merge_sort([9, 10, 2, 8, 7, 100, 22, 99, 15])
print(xxx)

快排

和归并一样，也是分治的思路

快排

def partition(arr, low, high):
    # 总是选择最右的
    pi = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pi:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)


arr = [0, 5, 1, 8, 7, 9]
quick_sort(arr, 0, len(arr) - 1)
print(arr)

堆排

大根堆：每个节点的值都大于或等于其子节点的值

小根堆：每个节点的值都小于或等于其子节点的值

堆排

def heapify(arr, n, i):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)
    # 构建大根堆
    for i in range(n // 2, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)


arr = [10, 7, 8, 1, 5, 3, 2, 7, 6]
heap_sort(arr)
print(arr)