问题 1.什么是线性查找

在序列中查找元素的最简单方法是逐个检查每个元素。如果找到该元素，则查找结束并返回该元素，否则查找将持续到序列结束。这种查找方法称为线性查找或顺序查找。

顺序查找时，最好的情况是查找的元素是列表中的第一个元素，时间复杂度将为 O(1)。最差的情况是遍历整个序列，正在寻找的元素并不存在，时间复杂度将为 O(n)。

问题 2.编写代码以实现线性查找def search(lst, num): flag = 0 for i in range(len(lst)): if lst[i] == num: print("发现目标数字：", num, "索引：", i) flag = 1 if flag == 0: print("目标数字没有找到。")lst = [1,2,3,4,9,6,7,8,9,10]num = input ("请输入要查找的数字：")search(lst, int(num))

运行：

请输入要查找的数字：8发现目标数字： 8 索引： 7请输入要查找的数字：9发现目标数字： 9 索引： 4发现目标数字： 9 索引： 8请输入要查找的数字：11目标数字没有找到。问题 3.如何实现二分查找算法

二分查找法也叫折半查找算法，是一种分而治之的算法，其中问题被划分为子问题，逐步缩小求解范围。

实现二分查找算法的最简单方法是使用递归，值得注意的是被查找的必须是有序的序列。

问题 4.使用递归实现二分查找算法def bSearch(target, lst, left, right): if left > right: return -1 mid = (left + right) // 2 item = lst[mid] if item == target: return mid elif target < item: return bSearch(target, lst, left, mid - 1) else: return bSearch(target, lst, mid + 1, right)lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]s = 30l = 0r = len(lst) - 1m = bSearch(s, lst, l, r)if m > 0: print("找到目标数，索引：", m)else: print("未找到目标数。")问题 5不使用递归实现二分查找算法def bSearch(lst, target): left = 0 right = len(lst) - 1 while left <= right: mid = (right + left) // 2 #取中位数索引 if lst[mid] == target: return mid elif target > lst[mid]: # 目标数大于中位数 left = mid + 1 #缩小查找范围到右侧 else: right = mid - 1 #缩小查找范围到左侧 return -1 #未找到元素lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]s = 6m = bSearch(lst, s)if m > 0: print("找到目标数，索引：", m)else: print("未找到目标数。")问题 6.比较二分查找和线性查找二分查找需要对数据排序，线性查找不需要。二分查找需要大小比较(如>，<);线性搜索只需要相等比较(==)。二分查找的复杂度为O(log n);线性搜索的复杂度是O(n)。二分查找随机存取数据;线性搜索顺序存取数据。问题 7.如何设置哨兵元素提高线性查找效率def gentinelSearch(ar,n,l): last = ar[l-1] ar[l-1] = n i = 0 while ar[i] != n: i += 1 ar[l-1] = last if i < l-1 or n == ar[1-1]: print('找到目标数，索引：',i) else: print('未找到目标数。' )ar = [1,2,3,4,5,6,7,8,9]n = 6l = len(ar)gentinelSearch(ar,n,l)问题 8.什么是排序算法

排序算法是一种用于按特定顺序排列元素的方法，使数据更易于管理和搜索。

问题 9.什么是冒泡排序

冒泡排序是重复比较相邻元素，如果它们的排列顺序不对，则交换它们的位置。冒泡排序是一种稳定的就地排序算法。

def bubbleSort(arr): n = len(arr) for i in range (n): for j in range(0,n-i-1): if arr[j] > arr[j+1]: arr[j],arr[j+1] = arr[j+1],arr[j]lst = [6,2,7,4,9,8,3,1,5]bubbleSort(lst)print(lst)问题 10.什么是插入排序

插入排序是从第二个元素开始，将其与前面已排好序的子序列依次比较，并插入到合适的位置。

def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arrlst = [6,2,7,4,9,8,3,1,5]insertion_sort(lst)print(lst)问题 11.什么是合并排序

合并排序（归并排序）是一种分而治之、基于比较的排序算法，其思想是将一个列表分成几个子列表，直到每个子列表都只包含一个元素，然后将这些子列表合并成一个有序列表。

def merge(a, b): c = [] h = j = 0 while j < len(a) and h < len(b): if a[j] < b[h]: c.append(a[j]) j += 1 else: c.append(b[h]) h += 1 if j == len(a): for i in b[h:]: c.append(i) else: for i in a[j:]: c.append(i) return cdef merge_sort(lst): if len(lst) <= 1: return lst middle = len(lst)//2 left = merge_sort(lst[:middle]) right = merge_sort(lst[middle:]) return merge(left, right) lst = [6,2,7,4,9,8,3,1,5]print(merge_sort(lst))问题 12.什么是堆排序

堆排序是一种基于比较的排序算法。堆排序可以认为是一种改进的选择排序，它将输入分为已排序区域和未排序区域，并通过提取最大元素并将其移动到已排序区域来迭代收缩未排序区域。

def heap_sort(array): first = len(array) // 2 - 1 for start in range(first, -1, -1): # 从下到上，从右到左对每个非叶节点进行调整，循环构建成大顶堆 big_heap(array, start, len(array) - 1) for end in range(len(array) - 1, 0, -1): # 交换堆顶和堆尾的数据 array[0], array[end] = array[end], array[0] # 重新调整完全二叉树，构造成大顶堆 big_heap(array, 0, end - 1) return array def big_heap(array, start, end): root = start # 左孩子的索引 child = root * 2 + 1 while child <= end: # 节点有右子节点，并且右子节点的值大于左子节点，则将child变为右子节点的索引 if child + 1 <= end and array[child] < array[child + 1]: child += 1 if array[root] < array[child]: # 交换节点与子节点中较大者的值 array[root], array[child] = array[child], array[root] # 交换值后，如果存在孙节点，则将root设置为子节点，继续与孙节点进行比较 root = child child = root * 2 + 1 else: breaklst = [6,2,7,4,9,8,3,1,5]print(heap_sort(lst))问题 13.什么是计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，将数组的索引当做每一个元素，然后统计每个索引即元素出现的次数记录在该所索引位置处。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

def countSort(arr): max_value = max(arr) res = [] count_nums = [0 for i in range(max_value + 1)] for num in arr: count_nums[num] += 1 for i in range(len(count_nums)): if count_nums[i] != 0: res.extend(count_nums[i] * [i]) return reslst = [6,2,7,4,9,8,3,1,5]print(countSort(lst))问题 14.什么是桶排序

将未排序数组分到若干个「桶」中，每个桶的元素再进行单独排序。

def bucket_sort(array): min_num, max_num = min(array), max(array) bucket_num = (max_num-min_num)//3 + 1 buckets = [[] for _ in range(int(bucket_num))] for num in array: buckets[int((num-min_num)//3)].append(num) new_array = list() for i in buckets: for j in sorted(i): new_array.append(j) return new_arraylst = [6,2,7,4,9,8,3,1,5]print(bucket_sort(lst))

❝

文章创作不易，如果您喜欢这篇文章，请关注、点赞并分享给朋友。如有意见和建议，请在评论中反馈！

❞