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不在数组中