408复试day2(7大排序算法)

**第2 天复习日志**

今天是我们进入复试的第二天，我们需要在短时间内完成7 大排序算法的学习和实践。下面是我对这7 个算法的总结和代码示例。

###1. 冒泡排序冒泡排序是一种简单的排序算法，通过反复比较相邻元素，并进行交换，使得较大的元素向上"冒"到最高位置。

**时间复杂度:** O(n^2)
**空间复杂度:** O(1)

def bubble_sort(arr):
 n = len(arr)
 for i in range(n-1):
 for j in range(n-i-1):
 if arr[j] > arr[j+1]:
 arr[j], arr[j+1] = arr[j+1], arr[j]
 return arr# 测试arr = [64,34,25,12,22,11,90]
print(bubble_sort(arr)) # 输出: [11,12,22,25,34,64,90]

###2.选择排序选择排序是一种简单的排序算法，通过首先找到最小元素，然后将其与第一个元素交换，接着再次从剩余未排序元素中找到最小元素，并将其与第二个元素交换，以此类推。

**时间复杂度:** O(n^2)
**空间复杂度:** O(1)

def selection_sort(arr):
 n = len(arr)
 for i in range(n-1):
 min_idx = i for 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,34,25,12,22,11,90]
print(selection_sort(arr)) # 输出: [11,12,22,25,34,64,90]

###3. 插入排序插入排序是一种简单的排序算法，通过将每个元素插入到已经排好序的前面部分中。

**时间复杂度:** O(n^2)
**空间复杂度:** O(1)

def insertion_sort(arr):
 n = len(arr)
 for i in range(1, n):
 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 arr# 测试arr = [64,34,25,12,22,11,90]
print(insertion_sort(arr)) # 输出: [11,12,22,25,34,64,90]

###4. 归并排序归并排序是一种分治法的排序算法，通过将数组分成两个子数组，然后分别对每个子数组进行排序，并将它们合并起来。

**时间复杂度:** O(n log n)
**空间复杂度:** O(n)

def merge_sort(arr):
 if len(arr) <=1:
 return arr mid = len(arr) //2 left = merge_sort(arr[:mid])
 right = merge_sort(arr[mid:])
 return merge(left, right)

def merge(left, right):
 result = []
 while left and right:
 if left[0] < right[0]:
 result.append(left.pop(0))
 else:
 result.append(right.pop(0))
 result.extend(left)
 result.extend(right)
 return result# 测试arr = [64,34,25,12,22,11,90]
print(merge_sort(arr)) # 输出: [11,12,22,25,34,64,90]

###5. 快速排序快速排序是一种分治法的排序算法，通过选择一个元素作为基准点，然后将数组分成两个子数组，并分别对每个子数组进行排序。

**时间复杂度:** O(n log n)
**空间复杂度:** O(log n)

def quick_sort(arr):
 if len(arr) <=1:
 return arr pivot = 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)

# 测试arr = [64,34,25,12,22,11,90]
print(quick_sort(arr)) # 输出: [11,12,22,25,34,64,90]

###6. 堆排序堆排序是一种分治法的排序算法，通过将数组建成一个最大堆，然后逐步地将最大元素交换到最后面。

**时间复杂度:** O(n log n)
**空间复杂度:** O(1)

def heapify(arr, n, i):
 largest = i left =2 * i +1 right =2 * i +2 if left < n and arr[left] > arr[largest]:
 largest = left if right < n and arr[right] > arr[largest]:
 largest = right if largest != i:
 arr[i], arr[largest] = arr[largest], arr[i]
 heapify(arr, n, largest)

def heap_sort(arr):
 n = len(arr)
 for i in range(n //2 -1, -1, -1):
 heapify(arr, n, i)
 for i in range(n-1,0, -1):
 arr[0], arr[i] = arr[i], arr[0]
 heapify(arr, i,0)
 return arr# 测试arr = [64,34,25,12,22,11,90]
print(heap_sort(arr)) # 输出: [11,12,22,25,34,64,90]

###7. 桶排序桶排序是一种分治法的排序算法，通过将数组分成多个桶，然后对每个桶进行排序。

**时间复杂度:** O(n + k)
**空间复杂度:** O(n + k)

def bucket_sort(arr):
 min_val = min(arr)
 max_val = max(arr)
 bucket_count = (max_val - min_val) // len(arr) +1 buckets = [[] for _ in range(bucket_count)]
 for num in arr:
 index = (num - min_val) // (bucket_count -1)
 buckets[index].append(num)
 sorted_arr = []
 for bucket in buckets:
 sorted_arr.extend(sorted(bucket))
 return sorted_arr# 测试arr = [64,34,25,12,22,11,90]
print(bucket_sort(arr)) # 输出: [11,12,22,25,34,64,90]

以上就是这7 个排序算法的总结和代码示例。每个算法都有其特点和应用场景，选择合适的算法可以提高程序的效率和准确性。