查找

1. 线性查找

算法思想：

线性查找，也被称为顺序查找，是一种最简单的查找算法。它的基本思想是从表的一端开始，逐个检查表中的元素，直到找到所需的元素为止。如果表中不存在该元素，则查找失败。

具体实现：太简单，略过

2.二分查找

算法思想：

二分查找是一种在有序列表中查找某一特定元素的搜索算法。搜索过程从列表的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在列表大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤列表为空，则代表找不到。

具体实现：

• 初始化两个指针（或索引）low和high，分别指向列表的起始和结束位置。
• 计算中间位置mid。
• 将中间位置的元素与目标元素进行比较。
  • 如果相等，则返回mid作为目标元素的位置。
  • 如果目标元素大于中间元素，则将low更新为mid+1，继续在右半部分查找。
  • 如果目标元素小于中间元素，则将high更新为mid-1，继续在左半部分查找。
• 重复步骤2和3，直到找到目标元素或low大于high（表示未找到）。

def binary_search(list, target):low = 0high = len(list) - 1while low <= high:mid = (low + high) // 2guess = list[mid]if guess == target:return midelif guess > target:high = mid - 1else:low = mid + 1return None  # 返回None表示查找失败

排序

基本排序算法

1.冒泡排序

算法思想：

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止，这时该数列已经排序完成。

具体实现：

def bubble_sort(arr):n = len(arr)for i in range(n):# 提前退出标志swapped = Falsefor 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:breakreturn arr# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array is:", sorted_arr)

2.选择排序

算法思想：

选择排序的工作原理是将未排序序列中最小（或最大）元素存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

具体实现：

def selection_sort(arr):n = len(arr)for i in range(n):# 假设当前元素为最小值min_idx = ifor j in range(i+1, n):if arr[j] < arr[min_idx]:min_idx = j# 交换找到的最小值和当前元素arr[i], arr[min_idx] = arr[min_idx], arr[i]return arr# 示例
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array is:", sorted_arr)

3.插入排序

算法思想：

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，找到相应位置并插入时，不需要移动元素（实际上是将大于插入元素的元素向后移动一位），只需将要插入的元素移到正确的位置即可。

具体来说，插入排序算法从数组的第二个元素开始，假设第一个元素已经被排序（即长度为1的有序序列）。然后，取出下一个元素，在已经排序的元素序列中从后向前扫描，找到相应位置并插入。重复以上步骤，直到所有元素都排序完毕。

具体实现：

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]  # 将大于key的元素向后移动一位j -= 1# 插入key到正确位置arr[j + 1] = keyreturn arr# 示例
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array is:", sorted_arr)

高级排序算法

1.归并排序

算法思想：

归并排序的核心思想是将一个大数组分成两个较小的子数组，分别进行排序，然后将排序好的两个子数组合并成一个有序的数组。这个过程可以递归地进行，直到每个子数组只包含一个元素或为空。归并排序类似于二叉树的后序遍历，会持续划分区间，直到区间内元素有序，然后利用额外空间对元素进行排序，并将它们合并回原区间，直至整个序列有序。

具体实现：

归并排序的具体实现可以分为递归和非递归两种方式。以下是递归实现的步骤：

• 确定递归的结束条件，即当数组长度为1时，认为已经有序，直接返回。
• 计算中间位置mid，将数组一分为二。
• 递归地对左半部分和右半部分进行归并排序。
• 合并两个有序的子数组，得到一个有序的数组。

非递归实现的思想与递归相似，但实现方式略有不同。它通常从单个元素的组开始，逐步扩大为2个元素、4个元素的组（二倍数扩大组数），然后依次合并这些组，直到整个数组有序。

def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left_half = merge_sort(arr[:mid])right_half = merge_sort(arr[mid:])return merge(left_half, right_half)def merge(left, right):sorted_arr = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:sorted_arr.append(left[i])i += 1else:sorted_arr.append(right[j])j += 1sorted_arr.extend(left[i:])sorted_arr.extend(right[j:])return sorted_arr# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array using Merge Sort:", sorted_arr)

2.快速排序

算法思想：

快速排序的核心思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序类似于二叉树的前序遍历，首先选择一个基准值（key），然后不断划分区间，对区间内的元素进行排序，直到整个序列有序。

具体实现：

快速排序的具体实现通常包括以下几个步骤：

• 选择一个基准元素（pivot），可以选择数组的第一个元素、最后一个元素、中间元素或随机选择的一个元素。
• 进行分区操作，重新排列数组，使得所有比基准元素小的元素都移动到基准的前面，所有比基准元素大的元素都移动到基准的后面（相同的数可以到任何一边）。
• 递归地对基准左侧和右侧的子数组进行快速排序。

def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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 quick_sort(left) + middle + quick_sort(right)# 或者使用原地快速排序（in-place quick sort）
def quick_sort_inplace(arr, low, high):if low < high:pi = partition(arr, low, high)quick_sort_inplace(arr, low, pi - 1)quick_sort_inplace(arr, pi + 1, high)def partition(arr, low, high):pivot = arr[high]  # 选择最后一个元素作为基准i = low - 1  # 较小元素的索引for j in range(low, high):if arr[j] <= pivot:i += 1arr[i], arr[j] = arr[j], arr[i]  # 交换arr[i + 1], arr[high] = arr[high], arr[i + 1]  # 将基准元素放到正确位置return i + 1# 示例（使用原地快速排序）
arr = [10, 7, 8, 9, 1, 5]
quick_sort_inplace(arr, 0, len(arr) - 1)
print("Sorted array using Quick Sort (in-place):", arr)