数据结构--------排序方法

数据结构的排序方法有多种，这些方法可以根据不同的性能要求和数据特点选择。

1. 冒泡排序（Bubble Sort）：通过比较相邻元素并交换它们，将最大（或最小）的元素逐渐“冒泡”到最后（或最前）。冒泡排序的时间复杂度为O(n^2)。

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # 标志位，如果某一轮没有发生交换操作，说明数组已经有序，可以提前结束
        swapped = False
 
        # 在每一轮中，比较相邻的元素并交换它们
        for 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:
            break
 
# 示例用法
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print("排序后的数组:", my_list)

1. 选择排序（Selection Sort）：每次选择最小（或最大）的元素，放置在已排序部分的末尾。选择排序的时间复杂度为O(n^2)。

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # 假设未排序部分的第一个元素是最小的
        min_index = i
        
        # 在未排序部分找到最小元素的索引
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # 将最小元素与未排序部分的第一个元素交换位置
        arr[i], arr[min_index] = arr[min_index], arr[i]
 
# 示例用法
my_list = [64, 34, 25, 12, 22, 11, 90]
selection_sort(my_list)
print("排序后的数组:", my_list)

1. 快速排序（Quick Sort）：通过选择一个基准元素，将数组分成两个子数组，然后递归地对子数组进行排序。快速排序的平均时间复杂度为O(n log n)，但最坏情况下可以达到O(n^2)。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        current_element = arr[i]
        j = i - 1
 
        # 将当前元素与已排序部分进行比较并插入正确位置
        while j >= 0 and current_element < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
 
        arr[j + 1] = current_element
 
# 示例用法
my_list = [12, 11, 13, 5, 6]
insertion_sort(my_list)
print("排序后的数组:", my_list)

1. 归并排序（Merge Sort）：将数组分成两个子数组，分别排序，然后合并这两个子数组以得到最终排序结果。归并排序的时间复杂度稳定在O(n log n)。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 计算中间位置
 
        left_half = arr[:mid]  # 划分左子数组
        right_half = arr[mid:]  # 划分右子数组
 
        merge_sort(left_half)  # 递归对左子数组进行归并排序
        merge_sort(right_half)  # 递归对右子数组进行归并排序
 
        i = j = k = 0
 
        # 合并左右子数组
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
 
        # 处理剩余的元素
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
 
# 示例用法
my_list = [12, 11, 13, 5, 6, 7]
merge_sort(my_list)
print("排序后的数组:", my_list)

1. 堆排序（Heap Sort）：将数组视为二叉堆（最大堆或最小堆），然后依次将堆顶元素取出，重新调整堆，直到整个数组有序。堆排序的时间复杂度为O(n log n)。

def heapify(arr, n, i):
    largest = i  # 初始化根节点为最大值
    left_child = 2 * i + 1
    right_child = 2 * i + 2
    
    # 找到左子节点和右子节点中的最大值
    if left_child < n and arr[left_child] > arr[largest]:
        largest = left_child
    if right_child < n and arr[right_child] > arr[largest]:
        largest = right_child
    
    # 如果最大值不是根节点，则交换根节点与最大值节点
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        
        # 递归调用heapify函数，确保交换后的子树也满足最大堆性质
        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)
 
# 示例用法
my_list = [64, 34, 25, 12, 22, 11, 90]
heap_sort(my_list)
print("排序后的数组:", my_list)

1. 计数排序（Counting Sort）：适用于有限范围内的整数排序，通过统计元素出现的次数来排序。计数排序的时间复杂度为O(n + k)，其中k是元素范围。

def counting_sort(arr):
    max_value = max(arr)
    min_value = min(arr)
    range_of_elements = max_value - min_value + 1
    
    # 创建计数数组，用于统计每个元素出现的次数
    count_arr = [0] * range_of_elements
    
    # 统计元素出现的次数
    for i in range(len(arr)):
        count_arr[arr[i] - min_value] += 1
    
    # 重新构建排序后的数组
    sorted_arr = [0] * len(arr)
    index = 0
    for i in range(range_of_elements):
        while count_arr[i] > 0:
            sorted_arr[index] = i + min_value
            index += 1
            count_arr[i] -= 1
    
    # 将排序后的数组赋值给原始数组
    for i in range(len(arr)):
        arr[i] = sorted_arr[i]
 
# 示例用法
my_list = [4, 2, 2, 8, 3, 3, 1]
counting_sort(my_list)
print("排序后的数组:", my_list)

1. 桶排序（Bucket Sort）：将数据分为若干个桶，每个桶内进行排序，然后合并所有桶的结果。桶排序的时间复杂度取决于桶的数量和桶内排序的算法。

def bucket_sort(arr):
    # 创建一个桶列表
    max_value = max(arr)
    min_value = min(arr)
    range_of_elements = max_value - min_value + 1
    bucket = [[] for _ in range(range_of_elements)]
    
    # 将元素分配到桶中
    for num in arr:
        index = num - min_value
        bucket[index].append(num)
    
    # 对每个桶中的元素进行排序（可以选择不同的排序算法）
    for i in range(range_of_elements):
        bucket[i].sort()
    
    # 将排序后的元素按顺序放回原始数组
    index = 0
    for i in range(range_of_elements):
        for num in bucket[i]:
            arr[index] = num
            index += 1
 
# 示例用法
my_list = [4, 2, 2, 8, 3, 3, 1]
bucket_sort(my_list)
print("排序后的数组:", my_list)

1. 基数排序（Radix Sort）：根据元素的位数，将数据分成若干个桶，从最低位到最高位依次排序。基数排序的时间复杂度也取决于位数。

def radix_sort(arr):
    # 找到数组中的最大值，以确定最大数字的位数
    max_num = max(arr)
    max_digit = len(str(max_num))
 
    # 初始化桶，每个桶用于存放相同位数的数字
    buckets = [[] for _ in range(10)]
 
    # 进行最大位数次排序，从个位开始到最高位
    for digit in range(max_digit):
        # 将数字放入桶中
        for num in arr:
            # 获取当前位的数字
            current_digit = (num // 10**digit) % 10
            buckets[current_digit].append(num)
 
        # 将桶中的数字按顺序放回原始数组
        index = 0
        for bucket in buckets:
            for num in bucket:
                arr[index] = num
                index += 1
 
        # 清空桶，以便下一轮排序
        buckets = [[] for _ in range(10)]
 
# 示例用法
my_list = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(my_list)
print("排序后的数组:", my_list)

每种排序算法的一些常见用例和适用情况：

因此，选择排序和冒泡排序主要用于教育目的或小型问题。对于大型数据集，通常选择快速排序、归并排序或堆排序，具体取决于性能要求和数据特征。计数排序、桶排序和基数排序适用于特殊情况，需要根据数据类型和范围来选择。

以下是六个常见的考试数据结构中关于排序的题目

**题目 1：选择排序**

题目描述：使用选择排序对以下整数数组进行升序排序：[64, 34, 25, 12, 22, 11, 90]。

答案和解析：
- 初始数组：[64, 34, 25, 12, 22, 11, 90]
- 第一次选择排序后：[11, 34, 25, 12, 22, 64, 90]
- 第二次选择排序后：[11, 12, 25, 34, 22, 64, 90]
- 第三次选择排序后：[11, 12, 22, 34, 25, 64, 90]
- 第四次选择排序后：[11, 12, 22, 25, 34, 64, 90]

**题目 2：归并排序**

题目描述：使用归并排序对以下整数数组进行升序排序：[38, 27, 43, 3, 9, 82, 10]。

答案和解析：
- 初始数组：[38, 27, 43, 3, 9, 82, 10]
- 归并排序过程：首先将数组分成单个元素，然后两两合并排序。
- 最终排序后的数组：[3, 9, 10, 27, 38, 43, 82]

**题目 3：快速排序**

题目描述：使用快速排序对以下整数数组进行升序排序：[56, 23, 11, 76, 98, 5, 44]。

答案和解析：
- 初始数组：[56, 23, 11, 76, 98, 5, 44]
- 快速排序过程：选择一个主元素（例如，中间元素），将数组分成两个子数组，小于主元素的放在左边，大于主元素的放在右边，然后递归排序子数组。
- 最终排序后的数组：[5, 11, 23, 44, 56, 76, 98]

**题目 4：计数排序**

题目描述：使用计数排序对以下整数数组进行升序排序：[8, 4, 7, 2, 5, 1, 6, 3].

答案和解析：
- 初始数组：[8, 4, 7, 2, 5, 1, 6, 3]
- 计数排序过程：创建计数数组统计每个元素的出现次数，然后构建有序数组。
- 最终排序后的数组：[1, 2, 3, 4, 5, 6, 7, 8]

**题目 5：桶排序**

题目描述：使用桶排序对以下整数数组进行升序排序：[0.32, 0.15, 0.47, 0.01, 0.83, 0.64, 0.79].

答案和解析：
- 初始数组：[0.32, 0.15, 0.47, 0.01, 0.83, 0.64, 0.79]
- 桶排序过程：将元素分配到多个桶中，然后对每个桶内的元素进行排序，最后合并所有桶。
- 最终排序后的数组：[0.01, 0.15, 0.32, 0.47, 0.64, 0.79, 0.83]

**题目 6：基数排序**

题目描述：使用基数排序对以下整数数组进行升序排序：[170, 45, 75, 90, 802, 24, 2, 66].

答案和解析：
- 初始数组：[170, 45, 75, 90, 802, 24, 2, 66]
- 基数排序过程：从最低位到最高位依次排序，每一轮排序根据当前位的数字分配到桶中，最后合并桶。
- 最终排序后的数组：[2, 24, 45, 66, 75, 90, 170, 802]