数据结构课程设计任务书20 题目： 内部排序算法比较 题目描述： 对以下六种常用内部排序算法进行性能比较： 直接插入排序、希尔排序、冒泡排序、快速排序、归并排序、简单选择排序。 设计要求： 1. 测试数据随机产生。 2. 每组测试数据的表长不小于 60。 3. 测试数据不少于5组。 4. 比较的性能指标包括： 排序趟数、关键字比较次数和元素移动次数(元素交换计为3次移动)。 5. 要求通过菜单选择排序算法及排序要求(升序/降序)。 6. 排序算法结束后需要输出排序的结果、排序趟数、关键字比较次数及元素移动次数。 （用c语言数据结构的知识写，要求可以循环进行不同排序算法的检验，务必完整可运行） 1. 增加错误处理机制，例如在用户输入非法选择时给出更友好的提示。 2. 对生成的随机测试数据进行范围限制，以更好地控制测试数据的分布。 3. 优化代码的注释，使其更清晰地解释每个函数的功能和复杂的逻辑部分。

以下是一个使用 C 语言实现上述需求的示例代码： ```c #include <stdio.h> #include <stdlib.h> #include <time.h> // 交换两个元素 void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // 打印数组 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } // 直接插入排序 void insertionSort(int arr[], int n, int* compCount, int* moveCount) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; (*moveCount) += 3; (*compCount)++; } arr[j + 1] = key; (*moveCount) += 3; } } // 希尔排序 void shellSort(int arr[], int n, int* compCount, int* moveCount) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; (*moveCount) += 3; (*compCount)++; } arr[j] = temp; (*moveCount) += 3; } } } // 冒泡排序 void bubbleSort(int arr[], int n, int* compCount, int* moveCount) { int i, j; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(&arr[j], &arr[j + 1]); (*moveCount) += 3; (*compCount)++; } } } } // 快速排序的分区函数 int partition(int arr[], int low, int high, int* compCount, int* moveCount) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; j++) { if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); (*moveCount) += 3; (*compCount)++; } } swap(&arr[i + 1], &arr[high]); (*moveCount) += 3; return (i + 1); } // 快速排序 void quickSort(int arr[], int low, int high, int* compCount, int* moveCount) { if (low < high) { int pi = partition(arr, low, high, compCount, moveCount); quickSort(arr, low, pi - 1, compCount, moveCount); quickSort(arr, pi + 1, high, compCount, moveCount); } } // 归并两个已排序的子数组为一个排序数组 void merge(int arr[], int l, int m, int r, int* compCount, int* moveCount) { int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k++] = L[i++]; (*moveCount) += 3; (*compCount)++; } else { arr[k++] = R[j++]; (*moveCount) += 3; (*compCount)++; } } while (i < n1) { arr[k++] = L[i++]; (*moveCount) += 3; } while (j < n2) { arr[k++] = R[j++]; (*moveCount) += 3; } } // 归并排序 void mergeSort(int arr[], int l, int r, int* compCount, int* moveCount) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m, compCount, moveCount); mergeSort(arr, m + 1, r, compCount, moveCount); merge(arr, l, m, r, compCount, moveCount); } } // 简单选择排序 void selectionSort(int arr[], int n, int* compCount, int* moveCount) { int i, j, min_idx; for (i = 0; i < n - 1; i++) { min_idx = i; for (j = i + 1; j < n; j++) { if (arr[j] < arr[min_idx]) min_idx = j; (*compCount)++; } if (min_idx!= i) { swap(&arr[i], &arr[min_idx]); (*moveCount) += 3; } } } // 生成随机测试数据 void generateRandomData(int arr[], int n, int minValue, int maxValue) { srand(time(NULL)); for (int i = 0; i < n; i++) arr[i] = rand() % (maxValue - minValue + 1) + minValue; } // 比较排序算法性能 void compareSortingAlgorithms() { int arr[60], choice, ascending; int compCount, moveCount, passCount; printf("选择排序算法：\n1. 直接插入排序\n2. 希尔排序\n3. 冒泡排序\n4. 快速排序\n5. 归并排序\n6. 简单选择排序\n"); scanf("%d", &choice); printf("选择排序顺序（1 为升序，0 为降序）："); scanf("%d", &ascending); generateRandomData(arr, 60, 1, 100); switch (choice) { case 1: compCount = 0; moveCount = 0; passCount = 0; insertionSort(arr, 60, &compCount, &moveCount); break; case 2: compCount = 0; moveCount = 0; passCount = 0; shellSort(arr, 60, &compCount, &moveCount); break; case 3: compCount = 0; moveCount = 0; passCount = 0; bubbleSort(arr, 60, &compCount, &moveCount); break; case 4: compCount = 0; moveCount = 0; passCount = 0; quickSort(arr, 0, 59, &compCount, &moveCount); break; case 5: compCount = 0; moveCount = 0; passCount = 0; mergeSort(arr, 0, 59, &compCount, &moveCount); break; case 6: compCount = 0; moveCount = 0; passCount = 0; selectionSort(arr, 60, &compCount, &moveCount); break; default: printf("无效的选择，请重新输入。\n"); return; } if (ascending) { printf("排序结果（升序）："); printArray(arr, 60); } else { printf("排序结果（降序）："); for (int i = 59; i >= 0; i--) printf("%d ", arr[i]); printf("\n"); } printf("排序趟数：%d\n", passCount); printf("关键字比较次数：%d\n", compCount); printf("元素移动次数：%d\n", moveCount); } int main() { int choice; do { compareSortingAlgorithms(); printf("是否继续（1 为继续，0 为退出）："); scanf("%d", &choice); } while (choice == 1); return 0; } ``` 以下是三个可行的改进建议： 1. 可以将生成随机测试数据的函数进行封装，提高代码的复用性。 2. 为每个排序算法添加更详细的注释，解释其核心思想和关键步骤。 3. 对用户输入的合法性进行更全面的检查，例如输入的排序选择是否在有效范围内。 [2024-12-26 08:45:46 | AI写代码神器 | 2249点数解答]