排序【数据结构】

**排序算法**

排序是一种常见的计算机科学概念，它涉及将一个未排序的集合（如列表或数组）重新排列为按某种顺序有序的集合。排序是许多应用程序中的关键组件，例如数据库管理系统、文件系统和图形用户界面。

在本文中，我们将讨论各种排序算法及其时间复杂度。我们还将提供一些示例代码，以帮助理解这些算法。

**1.选择排序**

选择排序是一种简单的排序算法，它通过反复遍历列表来找到最小或最大元素，并将其放在正确的位置。

**选择排序算法步骤：**

1. 初始化一个变量 `min_index`，用来存储当前最小元素的索引。
2. 遍历列表，从第一个元素开始到最后一个元素结束。
3. 在每个元素之后，比较该元素与当前最小元素（即 `min_index` 对应的元素），并更新 `min_index` 如果发现更小的元素。
4. 将 `min_index` 对应的元素交换到列表的第一个位置。
5. 重复步骤2-4，直到列表中所有元素都被排序。

**选择排序示例代码（Python）：**

def selection_sort(arr):
 n = len(arr)
 for i in range(n -1):
 min_index = i for j in range(i +1, n):
 if arr[j] < arr[min_index]:
 min_index = j # Swap elements at indices i and min_index arr[i], arr[min_index] = arr[min_index], arr[i]
 return arr# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)

**时间复杂度：**

选择排序的时间复杂度为 O(n^2)，其中 n 是列表中的元素数量。

**2. 插入排序**

插入排序是一种简单的排序算法，它通过反复遍历列表来将每个元素插入到正确的位置。

**插入排序算法步骤：**

1. 初始化一个变量 `i`，用来存储当前正在处理的元素。
2. 从第二个元素开始（即索引为1 的元素），遍历列表。
3. 对于每个元素，将其与前面的元素进行比较，如果它小于前面的元素，则将其插入到正确的位置。
4. 重复步骤2-3，直到列表中所有元素都被排序。

**插入排序示例代码（Python）：**

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# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)

**时间复杂度：**

插入排序的时间复杂度为 O(n^2)，其中 n 是列表中的元素数量。

**3. 归并排序**

归并排序是一种分治算法，它通过将列表分成两个子列表，然后对每个子列表进行排序，最后合并两个有序子列表来得到最终的有序列表。

**归并排序算法步骤：**

1. 如果列表中只有一个元素，则返回该元素（因为它已经是有序的）。
2. 将列表分成两个子列表。
3. 对每个子列表进行排序（递归地调用归并排序函数）。
4. 合并两个有序子列表。

**归并排序示例代码（Python）：**

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 = []
 while left and right:
 if left[0] <= right[0]:
 merged.append(left.pop(0))
 else:
 merged.append(right.pop(0))
 merged.extend(left or right)
 return merged# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)

**时间复杂度：**

归并排序的时间复杂度为 O(n log n)，其中 n 是列表中的元素数量。

**4. 快速排序**

快速排序是一种分治算法，它通过选择一个“基准”元素，然后将列表分成两个子列表（一部分小于基准，另一部分大于基准），最后对每个子列表进行排序。

**快速排序算法步骤：**

1.选择一个基准元素。
2. 将列表分成两个子列表，一部分小于基准，另一部分大于基准。
3. 对每个子列表进行排序（递归地调用快速排序函数）。

**快速排序示例代码（Python）：**

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)

# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)

**时间复杂度：**

快速排序的平均时间复杂度为 O(n log n)，但最坏情况下（即列表已经有序）其时间复杂度为 O(n^2)。

在本文中，我们讨论了四种常见的排序算法及其时间复杂度。我们还提供了一些示例代码，以帮助理解这些算法。