数据结构课程设计任务书20 题目： 内部排序算法比较 题目描述： 对以下六种常用内部排序算法进行性能比较： 直接插入排序、希尔排序、冒泡排序、快速排序、归并排序、简单选择排序。 设计要求： 1. 测试数据随机产生。 2. 每组测试数据的表长不小于 60。 3. 测试数据不少于5组。 4. 比较的性能指标包括： 排序趟数、关键字比较次数和元素移动次数(元素交换计为3次移动)。 5. 要求通过菜单选择排序算法及排序要求(升序/降序)。 6. 排序算法结束后需要输出排序的结果、排序趟数、关键字比较次数及元素移动次数。

以下是使用 Python 实现的代码示例： ```python import random # 直接插入排序 def insertion_sort(arr, ascending=True): """ 直接插入排序函数 :param arr: 待排序数组 :param ascending: 排序顺序，True 为升序，False 为降序 :return: 排序后的数组、排序趟数、关键字比较次数、元素移动次数 """ count_compare = 0 # 关键字比较次数 count_move = 0 # 元素移动次数 n = len(arr) for i in range(1, n): key = arr[i] j = i - 1 while j >= 0 and ((ascending and arr[j] > key) or (not ascending and arr[j] < key)): arr[j + 1] = arr[j] count_move += 1 j -= 1 count_compare += 1 arr[j + 1] = key return arr, i, count_compare, count_move # 希尔排序 def shell_sort(arr, ascending=True): """ 希尔排序函数 :param arr: 待排序数组 :param ascending: 排序顺序，True 为升序，False 为降序 :return: 排序后的数组、排序趟数、关键字比较次数、元素移动次数 """ count_compare = 0 # 关键字比较次数 count_move = 0 # 元素移动次数 n = len(arr) gap = n // 2 while gap > 0: for i in range(gap, n): temp = arr[i] j = i while j >= gap and ((ascending and arr[j - gap] > temp) or (not ascending and arr[j - gap] < temp)): arr[j] = arr[j - gap] count_move += 1 j -= gap count_compare += 1 arr[j] = temp gap //= 2 return arr, (n // gap) - 1, count_compare, count_move # 冒泡排序 def bubble_sort(arr, ascending=True): """ 冒泡排序函数 :param arr: 待排序数组 :param ascending: 排序顺序，True 为升序，False 为降序 :return: 排序后的数组、排序趟数、关键字比较次数、元素移动次数 """ count_compare = 0 # 关键字比较次数 count_move = 0 # 元素移动次数 n = len(arr) swapped = True num_passes = 0 while swapped: swapped = False for i in range(0, n - 1): if ((ascending and arr[i] > arr[i + 1]) or (not ascending and arr[i] < arr[i + 1])): arr[i], arr[i + 1] = arr[i + 1], arr[i] count_move += 3 swapped = True count_compare += 1 num_passes += 1 return arr, num_passes, count_compare, count_move # 快速排序 def quick_sort(arr, low, high, ascending=True): """ 快速排序函数 :param arr: 待排序数组 :param low: 起始索引 :param high: 结束索引 :param ascending: 排序顺序，True 为升序，False 为降序 :return: 排序后的数组、排序趟数、关键字比较次数、元素移动次数 """ count_compare = 0 # 关键字比较次数 count_move = 0 # 元素移动次数 if low < high: pi = partition(arr, low, high, ascending) quick_sort(arr, low, pi - 1, ascending) quick_sort(arr, pi + 1, high, ascending) return arr, 0, count_compare, count_move # 快速排序的趟数难以准确计算，这里暂时返回 0 def partition(arr, low, high, ascending=True): """ 分区函数，用于快速排序 :param arr: 数组 :param low: 起始索引 :param high: 结束索引 :param ascending: 排序顺序，True 为升序，False 为降序 :return: 基准元素的最终位置 """ pivot = arr[high] i = (low - 1) for j in range(low, high): if ((ascending and arr[j] <= pivot) or (not ascending and arr[j] >= pivot)): i += 1 arr[i], arr[j] = arr[j], arr[i] count_move += 3 count_compare += 1 arr[i + 1], arr[high] = arr[high], arr[i + 1] count_move += 3 return (i + 1) # 归并排序 def merge_sort(arr, ascending=True): """ 归并排序函数 :param arr: 待排序数组 :param ascending: 排序顺序，True 为升序，False 为降序 :return: 排序后的数组、排序趟数、关键字比较次数、元素移动次数 """ count_compare = 0 # 关键字比较次数 count_move = 0 # 元素移动次数 if len(arr) > 1: mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] merge_sort(left_half, ascending) merge_sort(right_half, ascending) i = j = k = 0 while i < len(left_half) and j < len(right_half): if ((ascending and left_half[i] <= right_half[j]) or (not ascending and left_half[i] >= right_half[j])): arr[k] = left_half[i] i += 1 else: arr[k] = right_half[j] j += 1 k += 1 count_compare += 1 count_move += 1 while i < len(left_half): arr[k] = left_half[i] i += 1 k += 1 count_move += 1 while j < len(right_half): arr[k] = right_half[j] j += 1 k += 1 count_move += 1 return arr, 0, count_compare, count_move # 归并排序的趟数难以准确计算，这里暂时返回 0 # 简单选择排序 def selection_sort(arr, ascending=True): """ 简单选择排序函数 :param arr: 待排序数组 :param ascending: 排序顺序，True 为升序，False 为降序 :return: 排序后的数组、排序趟数、关键字比较次数、元素移动次数 """ count_compare = 0 # 关键字比较次数 count_move = 0 # 元素移动次数 n = len(arr) for i in range(n - 1): min_idx = i for j in range(i + 1, n): if ((ascending and arr[j] < arr[min_idx]) or (not ascending and arr[j] > arr[min_idx])): min_idx = j count_compare += 1 if min_idx!= i: arr[i], arr[min_idx] = arr[min_idx], arr[i] count_move += 3 return arr, n - 1, count_compare, count_move # 生成随机测试数据 def generate_test_data(length): return [random.randint(1, 1000) for _ in range(length)] # 主函数 def main(): test_data = [] for _ in range(5): # 生成 5 组测试数据 test_data.append(generate_test_data(60)) print("请选择排序算法（1. 直接插入排序 2. 希尔排序 3. 冒泡排序 4. 快速排序 5. 归并排序 6. 简单选择排序）：") choice = int(input()) print("请选择排序顺序（1. 升序 2. 降序）：") sort_order = int(input()) ascending = sort_order == 1 results = [] if choice == 1: for data in test_data: result = insertion_sort(data.copy(), ascending) results.append(result) elif choice == 2: for data in test_data: result = shell_sort(data.copy(), ascending) results.append(result) elif choice == 3: for data in test_data: result = bubble_sort(data.copy(), ascending) results.append(result) elif choice == 4: for data in test_data: result = quick_sort(data.copy(), 0, len(data) - 1, ascending) results.append(result) elif choice == 5: for data in test_data: result = merge_sort(data.copy(), ascending) results.append(result) elif choice == 6: for data in test_data: result = selection_sort(data.copy(), ascending) results.append(result) else: print("无效的选择") return for i, result in enumerate(results): sorted_arr, num_passes, count_compare, count_move = result print(f"第 {i + 1} 组测试数据的排序结果：{sorted_arr}") print(f"排序趟数：{num_passes}") print(f"关键字比较次数：{count_compare}") print(f"元素移动次数：{count_move}") if __name__ == "__main__": main() ``` 1. 注意测试数据的随机性和规模，确保能够充分测试各种排序算法的性能。 2. 对于每种排序算法的性能指标计算要准确，特别是元素移动次数的计算。 3. 在实现排序算法时，要注意边界情况和异常处理，以保证程序的稳定性。 [2024-12-21 21:45:53 | AI写代码神器 | 2396点数解答]