C语言实现六种内部排序算法性能比较：附代码及改进建议

以下是一个使用 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* comparisons, int* moves) { 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; (*comparisons)++; (*moves) += 3; } arr[j + 1] = key; } } // 希尔排序 void shellSort(int arr[], int n, int* comparisons, int* moves) { int gap, i, j, temp; for (gap = n / 2; gap > 0; gap = gap / 2) { for (i = gap; i < n; i++) { temp = arr[i]; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; (*comparisons)++; (*moves) += 3; } arr[j] = temp; } } } // 冒泡排序 void bubbleSort(int arr[], int n, int* comparisons, int* moves) { 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]); (*comparisons)++; (*moves) += 3; } } } } // 快速排序 int partition(int arr[], int low, int high, int* comparisons, int* moves) { 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]); (*comparisons)++; (*moves) += 3; } } swap(&arr[i + 1], &arr[high]); (*moves) += 3; return (i + 1); } void quickSort(int arr[], int low, int high, int* comparisons, int* moves) { if (low < high) { int pi = partition(arr, low, high, comparisons, moves); quickSort(arr, low, pi - 1, comparisons, moves); quickSort(arr, pi + 1, high, comparisons, moves); } } // 归并排序 void merge(int arr[], int l, int m, int r, int* comparisons, int* moves) { 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++]; (*comparisons)++; } else { arr[k++] = R[j++]; (*comparisons)++; } (*moves) += 3; } while (i < n1) { arr[k++] = L[i++]; (*moves) += 3; } while (j < n2) { arr[k++] = R[j++]; (*moves) += 3; } } void mergeSort(int arr[], int l, int r, int* comparisons, int* moves) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m, comparisons, moves); mergeSort(arr, m + 1, r, comparisons, moves); merge(arr, l, m, r, comparisons, moves); } } // 简单选择排序 void selectionSort(int arr[], int n, int* comparisons, int* moves) { 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; (*comparisons)++; } if (min_idx!= i) { swap(&arr[i], &arr[min_idx]); (*moves) += 3; } } } // 生成随机测试数据 void generateRandomData(int arr[], int size) { srand(time(NULL)); for (int i = 0; i < size; i++) arr[i] = rand(); } // 菜单选择排序算法及排序要求 void menu(int arr[], int size) { int choice, ascending; int comparisons = 0, moves = 0; printf("1. 直接插入排序\n"); printf("2. 希尔排序\n"); printf("3. 冒泡排序\n"); printf("4. 快速排序\n"); printf("5. 归并排序\n"); printf("6. 简单选择排序\n"); printf("请选择排序算法: "); scanf("%d", &choice); printf("1. 升序\n"); printf("2. 降序\n"); printf("请选择排序顺序: "); scanf("%d", &ascending); switch (choice) { case 1: insertionSort(arr, size, &comparisons, &moves); break; case 2: shellSort(arr, size, &comparisons, &moves); break; case 3: bubbleSort(arr, size, &comparisons, &moves); break; case 4: quickSort(arr, 0, size - 1, &comparisons, &moves); break; case 5: mergeSort(arr, 0, size - 1, &comparisons, &moves); break; case 6: selectionSort(arr, size, &comparisons, &moves); break; default: printf("无效的选择\n"); return; } if (ascending == 1) { printf("排序结果（升序）: "); printArray(arr, size); } else { printf("排序结果（降序）: "); for (int i = size - 1; i >= 0; i--) printf("%d ", arr[i]); printf("\n"); } printf("排序趟数: %d\n", comparisons); printf("关键字比较次数: %d\n", comparisons); printf("元素移动次数: %d\n", moves); } int main() { int size = 60; int arr[size]; generateRandomData(arr, size); menu(arr, size); return 0; } ``` 以下是三个可能的改进建议： 1. 可以添加更多的错误处理机制，例如在用户输入无效选项时给出更明确的提示。 2. 对排序算法的性能分析部分可以更加详细和精确，例如计算每种算法的平均性能。 3. 可以将代码模块化，把不同的功能封装到单独的函数中，提高代码的可读性和可维护性。 ######[AI写代码神器 | 2009点数解答 | 2024-12-23 08:03:13]