In [5]:
"""
搜索最小值
"""
def find_min(data):
min_idx = 0
current_idx = 1
while current_idx < len(data):
if data[min_idx] > data[current_idx]:
min_idx = current_idx
current_idx += 1
return min_idx
data = [2, 10, 5, 12, 1, 6, 3]
find_min(data)
Out[5]:
In [11]:
"""
顺序搜索或线性搜索（Python中in使用的方法）
"""
def find_target(target, data):
idx = 0
while idx < len(data):
if data[idx] == target:
return idx
idx += 1
return -1
target = 12
data = [1, 2, 50, 12, 12, 2, 5]
find_target(target, data)
Out[11]:
In [27]:
"""
二叉搜索：
搜索的数据必须是已经排序过的数据
"""
def binary_search(target, sorted_data):
left_idx = 0
right_idx = len(sorted_data) - 1
while left_idx <= right_idx:
mid_idx = round((left_idx + right_idx) / 2)
if target == sorted_data[mid_idx]:
return mid_idx
elif target < sorted_data[mid_idx]:
right_idx = mid_idx - 1
else:
left_idx = mid_idx + 1
return -1
target = 12
sorted_data = [1, 2, 5, 6, 7, 10, 11, 12, 15, 20, 50]
binary_search(target, sorted_data)
Out[27]:
In [11]:
"""
选择排序:
1. 搜索整个列表，为第一个位置（即i=0）找到整个列表中的最小值，如果最小值的位置不等于第一个位置，则交换位置的值。
2. 继续搜索第二个位置的最小值，同理直到搜索到第n-1个位置的最小值（这里到n-1停止是因为我们要与最后一个位置n进行比较）
"""
def selection_sort(data):
i = 0
while i < len(data) - 1:
j = i + 1
min_idx = i
while j < len(data):
if data[j] < data[min_idx]:
min_idx = j
j += 1
# 如果初始位置索引的值不是最小值，则需要把最小值与i位置的值交换位置
if min_idx != i:
data[i], data[min_idx] = data[min_idx], data[i]
i += 1
data = [20,5,10,6,2,12]
selection_sort(data)
print(data)
In [5]:
"""
冒泡排序：
1. 从列表的开头比较一对（i, i+1）数据项的值，如果i的值大于i+1的值，则将i与i+1的值交换位置。
2. 内部第一次循环，把最大值放到最后。内部第二次循环，把第二大的值放到倒数第二个位置......`
"""
def bubble_sort(data):
n = 0
while n < len(data) - 1:
i = 0
while i < len(data) - 1:
if data[i] > data[i + 1]:
data[i], data[i + 1] = data[i + 1], data[i]
i += 1
n += 1
data = [20, 50, 10, 1]
bubble_sort(data)
print(data)
In [1]:
"""
插入排序：将一个数据插入到已经排好序的有序数据
1. 定义一个i（1<i<n），找到i前面的j个列表（j=i-1）。
2. 用当前的i的值（假设为cur_val）与前面的j个列表的值进行比较。
3. 如果cur_val小于j的值，则把这个j值的位置向前移动一位（即为j+1）的值。
4. 否则如果cur_val大于j的值，则跳出内部循环，然后把当前的值放到j的前面（即作为j+1的值）
"""
def insertion_sort(data):
i = 1
while i < len(data):
j = i - 1
current_item = data[i]
while j >= 0:
if current_item < data[j]:
data[j+1] = data[j]
else:
break
j -= 1
data[j+1] = current_item
i += 1
data = [10, 5, 2, 6, 8, 1, 3]
insertion_sort(data)
print(data)
In [2]:
"""
快速排序：是一种效率很高的排序算法，使用了分而治之（D&C)。
1. 从数组中选择一个元素，这个元素被称为基准值（pivot）。
2. 找出比基准值小的元素以及比基准值大的元素，这被称为分区（partitioning）。
3. 对这两个分区的子数组递归重新排序。
"""
def quick_sort(data):
if len(data) <= 1:
return data
# 拿到中间值并把中间值从数组中去掉
mid_position = len(data)//2
mid_val = data[mid_position]
data.pop(mid_position)
# 定义所有小于中间值的数组和所有大于中间值的数组
left_arr = []
right_arr = []
for v in data:
if v < mid_val:
left_arr.append(v)
else:
right_arr.append(v)
return quick_sort(left_arr) + [mid_val] + quick_sort(right_arr)
data = [20, 5, 10, 4, 12]
sort_data = quick_sort(data)
print(sort_data)