数据结构与算法-排序算法

1.顺序查找

def linear_search(iters, val):for i, v in enumerate(iters):if v == val:return ireturn

2.二分查找

# 升序的二分查找
def binary_search(iters, val):left = 0right = len(iters)-1while left <= right:mid = (left + right) // 2if iters[mid] == val:return midelif iters[mid] > val:right = mid - 1else:left = mid + 1else:return
lis = [1, 2, 3, 4]
print(binary_search(lis, 2))# 降序的二分查找
def binary_search(iters, val):left = 0right = len(iters)-1while left <= right:mid = (left + right) // 2if iters[mid] == val:return midelif iters[mid] > val:left = mid + 1else:right = mid - 1else:return
lis = [4, 3, 2, 1]
print(binary_search(lis, 2))

3.冒泡排序

# 升序冒泡排序
def bubble_sort(li):for i in range(len(li)-1): #第i趟exchange = False # 判断第i趟是否进行了交换for j in range(len(li)-1-i):if li[j] > li[j+1]:li[j], li[j+1] = li[j+1], li[j]exchange = Trueprint(li)if not exchange:return
li = [1, 4, 2, 9, 0]
bubble_sort(li)print("===========================================")# 降序冒泡排序
def bubble_sort(li):for i in range(len(li)-1): #第i趟exchange = False # 判断第i趟是否进行了交换for j in range(len(li)-1-i):if li[j] < li[j+1]:li[j], li[j+1] = li[j+1], li[j]exchange = Trueprint(li)if not exchange:return
li = [1, 4, 2, 9, 0]
bubble_sort(li)

4.选择排序

# 升序选择排序: 非原地排序(新增一个变量存储排序后的结果)
def select_sort_sample1(li):li_new = []for i in  range(len(li)):min_val = min(li)li_new.append(min_val)li.remove(min_val)return li_new
li = [3, 1, 4, 7, 4, 8]
print(select_sort_sample1(li))print("================================================")# 降序选择排序: 非原地排序(新增一个变量存储排序后的结果)
def select_sort_sample2(li):new_li = []for i in range(len(li)):max_val = max(li)new_li.append(max_val)li.remove(max_val)return new_li
li = [3, 1, 4, 7, 4, 8]
print(select_sort_sample2(li))print("=================================================")# 升序选择排序: 原地排序
def select_sort1(li):for i in range(len(li)-1):min_loc = ifor j in range(i+1, len(li)):if li[j] < li[min_loc]:min_loc = jli[i], li[min_loc] = li[min_loc], li[i]print(li)
li = [1, 4, 2, 8, 5]
select_sort1(li)print("==================================================")# 降序选择排序: 原地排序
def select_sort2(li):for i in range(len(li)-1):max_loc = ifor j in range(i+1, len(li)):if li[j] > li[max_loc]:max_loc = jli[i], li[max_loc] = li[max_loc], li[i]print(li)
li = [1, 4, 2, 8, 5]
select_sort2(li)

5.插入排序

# 升序插入排序
def insert_sort1(li):for i in range(1, len(li)): #i表示摸到的牌的下标tmp = li[i] #存放待插入的牌j = i - 1 #j表示手里的牌的下标while j >= 0 and li[j] > tmp:li[j+1] = li[j]j -= 1li[j+1] = tmpprint(li)
li = [1, 4, 2, 8, 5]
insert_sort1(li)print("=======================================")# 降序插入排序
def insert_sort2(li):for i in range(1, len(li)):tmp = li[i]j = i - 1while j >= 0 and li[j] < tmp:li[j+1] = li[j]j -= 1li[j+1] = tmpprint(li)
li = [1, 4, 2, 8, 5]
insert_sort2(li)

6.快速排序

# 升序快速排序
def partition1(li, left, right):tmp = li[left] #存放待归位的值while left < right:while left < right and li[right] >= tmp: #从右面找比tmp小的元素right -= 1 #往左走一步li[left] = li[right] #把右边的值写到左边while left < right and li[left] <= tmp: #从左面找比tmp大的元素left += 1 #往右走一步li[right] = li[left] #把左边的值写到右边li[left] = tmpreturn leftdef quick_sort1(li, left, right):if left < right: #至少两个元素mid = partition1(li, left, right)quick_sort1(li, left, mid-1)quick_sort1(li, mid+1, right)li = [4, 3, 5, 5, 8, 7]
quick_sort1(li, 0, len(li)-1)
print(li)print("======================================================")# 降序快速排序
def partition2(li, left, right):tmp = li[left]while left < right:while left < right and li[right] <= tmp:right -= 1li[left] = li[right]while left < right and li[left] >= tmp:left += 1li[right] = li[left]li[left] = tmpreturn leftdef quick_sort2(li, left, right):if left < right:mid = partition2(li, left, right)quick_sort2(li, left, mid-1)quick_sort2(li, mid+1, right)li = [4, 3, 5, 5, 8, 7]
quick_sort2(li, 0, len(li)-1)
print(li)

7.堆排序

# 升序堆排序
def shift(li, low, high):# 建大根堆""":param li: 列表:param low: 堆的根节点位置:param high: 堆的最后一个元素位置:return:"""i = low #i最开始指向根节点j = 2 * i + 1 #j开始是左孩子tmp = li[low] #把堆顶存起来while j <= high: # j位置有效if j + 1 <= high and li[j+1] > li[j]: #如果右孩子有且比较大j = j + 1 #j指向右孩子if li[j] > tmp:li[i] = li[j]i = jj = 2 * i + 1else:li[i] = tmpbreakelse:li[i] = tmp # 把tmp放到叶子节点上def heap_sort(li):n = len(li)for i in range((n-2)//2, -1, -1):# (n - 2) // 2表示最后一个有孩子节点的节点的下标# i表示建堆的时候要进行调整的二叉树的根的下标shift(li, i, n-1)# 建堆完成print("大根堆:{}".format(li))for i in range(n-1, -1, -1):# i指向当前堆的最后一个元素li[0], li[i] = li[i], li[0]shift(li, 0, i-1) # i-1是最新的high
import random
li = [i for i in range(10)]
random.shuffle(li)
print("初始列表:{}".format(li))
heap_sort(li)
print("排序列表:{}".format(li))print("============================================")# 降序堆排序
def shift1(li, low, high):# 建小根堆""":param li: 列表:param low: 堆的根节点位置:param high: 堆的最后一个节点的位置:return:"""i = low # 最开始指向根节点j = 2 * i + 1 # 左孩子节点tmp = li[low]while j <= high:if j + 1 <= high and li[j + 1] < li[j]:j = j + 1if li[j] < tmp:li[i] = li[j]i = jj = 2 * i + 1else:li[i] = tmpbreakelse:li[i] = tmpdef heap_sort1(li):n = len(li)for i in range((n-2)//2, -1, -1):shift1(li, i, n-1)print("小根堆:{}".format(li))# 建堆完成for i in range(n-1, -1, -1):li[0], li[i] = li[i], li[0]shift1(li, 0, i - 1)
import random
li = [i for i in range(10)]
random.shuffle(li)
print("初始列表:{}".format(li))
heap_sort1(li)
print("排序列表:{}".format(li))

8.归并排序

# 升序归并排序
def merge(li, low, mid, high):# 对两个有序列表进行合并""":param li: 列表:param low::param mid::param high::return:"""i = lowj = mid + 1ltmp = []while i <= mid and j <= high: #只要两边都有数if li[i] < li[j]:ltmp.append(li[i])i += 1else:ltmp.append(li[j])j += 1while i <= mid:ltmp.append(li[i])i += 1while j <= high:ltmp.append(li[j])j += 1li[low:high+1] = ltmpdef merge_sort(li, low, high):if low < high: # 至少有两个元素mid = (low + high) // 2merge_sort(li, low, mid)merge_sort(li, mid + 1, high)merge(li, low, mid, high)import random
li = [i for i in range(10)]
random.shuffle(li)
merge_sort(li, 0, len(li) - 1)
print(li)print("================================================")# 降序归并排序
def merge1(li, low, mid, high):# 对两个有序列表进行合并""":param li: 列表:param low::param mid::param high::return:"""i = lowj = mid + 1ltmp = []while i <= mid and j <= high: #只要两边都有数if li[i] > li[j]:ltmp.append(li[i])i += 1else:ltmp.append(li[j])j += 1while i <= mid:ltmp.append(li[i])i += 1while j <= high:ltmp.append(li[j])j += 1li[low:high+1] = ltmpdef merge_sort1(li, low, high):if low < high: # 至少有两个元素mid = (low + high) // 2merge_sort1(li, low, mid)merge_sort1(li, mid + 1, high)merge1(li, low, mid, high)import random
li = [i for i in range(10)]
random.shuffle(li)
merge_sort1(li, 0, len(li) - 1)
print(li)

9.希尔排序

# 升序希尔排序
def insert_sort_gap(li, gap):for i in range(gap, len(li)): #i表示摸到的牌的下标tmp = li[i] #存放待插入的牌j = i - gap #j表示手里的牌的下标while j >= 0 and li[j] > tmp:li[j + gap] = li[j]j -= gapli[j+gap] = tmpdef shell_sort(li):d = len(li) // 2while d >= 1:insert_sort_gap(li, d)d //= 2li = [1, 4, 2, 8, 5]
shell_sort(li)
print(li)

10.计数排序

# 升序计数排序
# 限制: 数值有确定的范围
def count_sort(li, max_count=100):count = [0 for _ in range(max_count+1)]for val in li:count[val] += 1li.clear()for ind, val in enumerate(count):for i in range(val):li.append(ind)
import random
li = [random.randint(0, 100) for i in range(1000)]
count_sort(li)
print(li)

11.桶排序

# 升序桶排序
def bucket_sort(li, n=100, max_num=10000):buckets = [[] for i in range(n)]  # 创建桶for var in li:i = min(var // (max_num // n), n - 1)  # i表示var放到第几个桶里buckets[i].append(var)  # 把var放桶里for j in range(len(buckets[i]) - 1, 0, -1):if buckets[i][j] < buckets[i][j - 1]:buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j]else:breaksorted_li = []for buc in buckets:sorted_li.extend(buc)return sorted_liimport random
li = [random.randint(0, 10000) for i in range(100)]
print(bucket_sort(li))

12.基数排序

def redix_sort(li):""":param li: 列表:return:限制于正整数的基数排序"""max_num = max(li)it = 0  # 0 -> 按个位分桶  1 -> 按十位分桶 2 -> 按百位分桶...while 10 ** it <= max_num:buckets = [[] for _ in range(10)]for var in li:digit = (var // 10 ** it) % 10  # it->0 取个位; it->1 取十位; it->2 取百位...(若该数位上没有数字, 取零)buckets[digit].append(var)# 分桶完成li.clear()for buc in buckets:li.extend(buc)# 把数重新写回liit += 1import random
li = [random.randint(0, 10000) for i in range(100)]
redix_sort(li)
print(li)