leetcode 排序算法汇总

快速排序

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]  # 选择中间值作为基准
        left = [x for x in arr if x < pivot]  # 小于基准的放左边
        middle = [x for x in arr if x == pivot]  # 等于基准的放中间
        right = [x for x in arr if x > pivot]  # 大于基准的放右边
        return quicksort(left) + middle + quicksort(right)  # 递归排序

# 测试快速排序算法
arr = [3, 6, 8, 10, 1, 2, 1]
print("原始数组:", arr)
sorted_arr = quicksort(arr)
print("排序后数组:", sorted_arr)
 

冒泡排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        # 标志位用于优化，如果在一轮比较中没有元素交换，说明数组已经有序，可以直接结束排序
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果没有发生交换，说明数组已经有序，退出循环
        if not swapped:
            break
    return arr

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array is:", sorted_arr)

直接插入排序

def insertion_sort(arr):
    # 遍历从1到len(arr)的所有元素
    for i in range(1, len(arr)):
        key = arr[i]  # 当前要插入的元素
        j = i - 1
        # 将当前元素与已排序部分的元素进行比较，找到合适的插入位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]  # 将已排序部分的元素向后移动
            j -= 1
        # 插入当前元素
        arr[j + 1] = key
    return arr

# 示例
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6]
    print("原始数组:", arr)
    sorted_arr = insertion_sort(arr)
    print("排序后数组:", sorted_arr)
 

二分查找法：

def binary_search(arr, target):
    """
    二分查找法
    :param arr: 有序数组
    :param target: 查找目标
    :return: 目标在数组中的索引，如果不存在返回-1
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    
    return -1

# 示例
if __name__ == "__main__":
    my_list = [1, 3, 5, 7, 9]  # 示例数组
    print(binary_search(my_list, 3))  # 输出：1，因为3在数组中的索引位置是1
    print(binary_search(my_list, -1)) # 输出：-1，因为-1不在数组中