成品网站w灬源码伊园,上海建设银行官网网站,wordpress閱讀主题,个人公众号登录平台第二章 算法设计思想
一、搜索排序
1.排序算法
https://visualgo.net/zh/sorting
(1)冒泡排序
# 思路#xff1a;
# (1)比较相邻元素#xff0c;如果第一个比第二个大#xff0c;则交换他们
# (2)第一轮下来#xff0c;可以保证最后一个数一定是最大的#xff1b;第二…第二章 算法设计思想
一、搜索排序
1.排序算法
https://visualgo.net/zh/sorting
(1)冒泡排序
# 思路
# (1)比较相邻元素如果第一个比第二个大则交换他们
# (2)第一轮下来可以保证最后一个数一定是最大的第二轮下来可以保证倒数第二个数一定是第二大的。
# (3)执行n-1轮可以完成排序。
# 比较n-1次用[3,2,1]冒泡排序后只需要比较2次。
def bubleSort(arr):for j in range(len(arr) - 1):for i in range(len(arr) - 1):if arr[i] arr[i1]:temp arr[i]arr[i] arr[i 1]arr[i 1] temparr [5, 4, 3, 2, 1]
bubleSort(arr)
print(arr)(2)选择排序
# 思路
# (1)找到数组中的最小值选中它并将其放置在第一位 → 经过第一轮交换第一个值肯定是最小的。
# (2)接着找到第二小的值选中必将其放置在第二位 → 经过第二轮交换第二个值肯定是第二小的。
# 以此类推交换n-1轮def selectionSort(arr):for i in range(len(arr) - 1):indexMin ifor j in range(i, len(arr)):if arr[j] arr[indexMin]:indexMin jtemp arr[i]arr[i] arr[indexMin]arr[indexMin] temparr [2, 3, 1] # 最坏的情况
selectionSort(arr)
print(arr)2.搜索算法
http://data.biancheng.net/view/336.html
# 二分插入
# 为什么更新左边界需1但是更新右边界却不需要1
# 使用了左闭右开的搜索区间即[l, r)。这意味着左边界l是包含在搜索区间内的而右边界r是不包含在搜索区间内的。所以当更新左边界l时需要加1因为已经排除了中间元素而当你更新右边界r时这不需要加1因为要保持右边界不包含在搜索区间内。这样做的好处是当搜索区间为空时l和r会相等而且l就是目标元素应该插入的位置。
# 二分查找从列表中查找元素下标
def binaryInsertIndex(arr, ele):if ele not in arr:return -1l 0r len(arr) - 1while l r:mid (l r) // 2if ele arr[mid]:r midelse:l mid 1 # ele不小于arr[mid]意味着ele arr[mid]所以需加上1。return larr [2,3,6,7]
element 3
arr.insert(binaryInsertIndex(arr, element), element)
print(arr)
