算法与数据结构-排序

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

排序是计算机科学中一个非常重要的概念，它涉及到将一组数字或字符串按照一定的顺序排列。排序有很多种方法，包括冒泡排序、选择排序、插入排序等。这些排序算法可以应用于各种场景，如数据分析、信息检索等。

**1. 冒泡排序**

冒泡排序是一种简单的排序算法，它通过反复地比较相邻的元素，并将较大的元素向后移动，直到所有元素都有序排列。冒泡排序的时间复杂度为 O(n^2)，其中 n 是数据集的大小。

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("原始数组：", arr)
print("排序后数组：", bubble_sort(arr))

**2.选择排序**

选择排序是一种简单的排序算法，它通过找到最小或最大元素，并将其放在首位，然后再次寻找下一个最小或最大元素，直到所有元素都有序排列。选择排序的时间复杂度为 O(n^2)。

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 # 如果找到更小或更大的元素，则交换它们 if min_idx != i:
 arr[i], arr[min_idx] = arr[min_idx], arr[i]
 return arr# 测试选择排序算法arr = [64,34,25,12,22,11,90]
print("原始数组：", arr)
print("排序后数组：", selection_sort(arr))

**3. 插入排序**

插入排序是一种简单的排序算法，它通过将每个元素插入到已经有序的列表中，直到所有元素都有序排列。插入排序的时间复杂度为 O(n^2)。

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("原始数组：", arr)
print("排序后数组：", insertion_sort(arr))

**4. 归并排序**

归并排序是一种高效的排序算法，它通过将数据分成小块，然后合并这些小块，直到所有元素都有序排列。归并排序的时间复杂度为 O(n log n)。

def merge_sort(arr):
 # 归并排序算法 if len(arr) <=1:
 return arr mid = len(arr) //2 left_half = arr[:mid]
 right_half = arr[mid:]
 # 递归地将左半部分和右半部分进行排序 left_half = merge_sort(left_half)
 right_half = merge_sort(right_half)
 return merge(left_half, right_half)

def merge(left, right):
 merged = []
 left_index =0 right_index =0 # 将左半部分和右半部分合并起来 while left_index < len(left) and right_index < len(right):
 if left[left_index] <= right[right_index]:
 merged.append(left[left_index])
 left_index +=1 else:
 merged.append(right[right_index])
 right_index +=1 # 将剩余的元素添加到合并列表中 merged.extend(left[left_index:])
 merged.extend(right[right_index:])
 return merged# 测试归并排序算法arr = [64,34,25,12,22,11,90]
print("原始数组：", arr)
print("排序后数组：", merge_sort(arr))

**5. 快速排序**

快速排序是一种高效的排序算法，它通过选择一个基准元素，然后将其他元素分成两部分，分别小于和大于该基准元素。快速排序的时间复杂度为 O(n 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("原始数组：", arr)
print("排序后数组：", quick_sort(arr))

**总结**

在本文中，我们介绍了五种常见的排序算法，包括冒泡排序、选择排序、插入排序、归并排序和快速排序。每种算法都有其特点和应用场景。通过理解这些算法的原理和实现细节，我们可以更好地选择合适的排序算法来解决实际问题。

**参考**

* [1] "Sorting Algorithms" by Wikipedia* [2] "Introduction to Algorithms" by Thomas H. Cormen et al.
* [3] "Algorithms" by Robert Sedgewick and Kevin Wayne