用c语言写出比较直接插入排序，快速排序，希尔排序，冒泡排序，简单选择排序，堆排序，归并排序，基数排序的关键字比较次数和关键字移动次数的代码，要求待排序的表长不能小于100；其中的数据要用伪随机数生成程序产生至少要用5组不同的输入数据比较；代码要给出注释

以下是使用C语言实现各种排序算法的关键字比较次数和关键字移动次数的代码。其中，数据使用伪随机数生成程序产生，共使用了5组不同的输入数据进行比较，排序算法包括直接插入排序、快速排序、希尔排序、冒泡排序、简单选择排序、堆排序、归并排序、基数排序。 ``` #include <stdio.h> #include <stdlib.h> #include <time.h> // 生成伪随机数 int* generateRandomArray(int length) { int* arr = (int*)malloc(sizeof(int) * length); srand((unsigned)time(NULL)); for (int i = 0; i < length; i++) { *(arr + i) = rand() % 10000; } return arr; } // 直接插入排序 void straightInsertionSort(int* arr, int length, int* compareCount, int* moveCount) { int temp, j; for (int i = 1; i < length; i++) { temp = *(arr + i); j = i - 1; (*compareCount)++; while (j >= 0 && temp < *(arr + j)) { *(arr + j + 1) = *(arr + j); j--; (*moveCount)++; (*compareCount)++; } *(arr + j + 1) = temp; (*moveCount)++; } } // 快速排序 void quickSort(int* arr, int start, int end, int* compareCount, int* moveCount) { if (start >= end) { return; } int i = start, j = end, pivot = *(arr + start); while (i < j) { (*compareCount)++; while (i < j && *(arr + j) >= pivot) { j--; (*compareCount)++; } if (i < j) { *(arr + i) = *(arr + j); i++; (*moveCount)++; } (*compareCount)++; while (i < j && *(arr + i) < pivot) { i++; (*compareCount)++; } if (i < j) { *(arr + j) = *(arr + i); j--; (*moveCount)++; } } *(arr + i) = pivot; (*moveCount)++; quickSort(arr, start, i - 1, compareCount, moveCount); quickSort(arr, i + 1, end, compareCount, moveCount); } // 希尔排序 void shellSort(int* arr, int length, int* compareCount, int* moveCount) { int temp, gap = length / 2; while (gap > 0) { for (int i = gap; i < length; i++) { temp = *(arr + i); int j = i - gap; (*compareCount)++; while (j >= 0 && *(arr + j) > temp) { *(arr + j + gap) = *(arr + j); j -= gap; (*moveCount)++; (*compareCount)++; } *(arr + j + gap) = temp; (*moveCount)++; } gap /= 2; } } // 冒泡排序 void bubbleSort(int* arr, int length, int* compareCount, int* moveCount) { for (int i = 0; i < length - 1; i++) { for (int j = 0; j < length - 1 - i; j++) { (*compareCount)++; if (*(arr + j) > *(arr + j + 1)) { int temp = *(arr + j); *(arr + j) = *(arr + j + 1); *(arr + j + 1) = temp; (*moveCount) += 3; } } } } // 简单选择排序 void selectionSort(int* arr, int length, int* compareCount, int* moveCount) { for (int i = 0; i < length - 1; i++) { int minIndex = i; for (int j = i + 1; j < length; j++) { (*compareCount)++; if (*(arr + j) < *(arr + minIndex)) { minIndex = j; } } if (minIndex != i) { int temp = *(arr + i); *(arr + i) = *(arr + minIndex); *(arr + minIndex) = temp; (*moveCount) += 3; } } } // 堆排序 void heapSort(int* arr, int length, int* compareCount, int* moveCount) { // 构建初始堆 for (int i = length / 2 - 1; i >= 0; i--) { int parent = i, child = 2 * i + 1, temp = *(arr + i); while (child < length) { (*compareCount)++; if (child < length - 1 && *(arr + child) < *(arr + child + 1)) { child++; } (*compareCount)++; if (temp >= *(arr + child)) { break; } *(arr + parent) = *(arr + child); (*moveCount)++; parent = child; child = 2 * parent + 1; } *(arr + parent) = temp; (*moveCount)++; } // 调整堆 for (int i = length - 1; i > 0; i--) { int temp = *(arr + i); *(arr + i) = *arr; *arr = temp; (*moveCount) += 3; int parent = 0, child = 1; while (child < i) { (*compareCount)++; if (child < i - 1 && *(arr + child) < *(arr + child + 1)) { child++; } (*compareCount)++; if (temp >= *(arr + child)) { break; } *(arr + parent) = *(arr + child); (*moveCount)++; parent = child; child = 2 * parent + 1; } *(arr + parent) = temp; (*moveCount)++; } } // 归并排序 void mergeSort(int* arr, int left, int right, int* compareCount, int* moveCount) { if (left >= right) { return; } int mid = (left + right) / 2; mergeSort(arr, left, mid, compareCount, moveCount); mergeSort(arr, mid + 1, right, compareCount, moveCount); int* tempArr = (int*)malloc(sizeof(int) * (right - left + 1)); int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { (*compareCount)++; if (*(arr + i) <= *(arr + j)) { *(tempArr + k) = *(arr + i); i++; } else { *(tempArr + k) = *(arr + j); j++; } k++; } while (i <= mid) { *(tempArr + k) = *(arr + i); i++; k++; } while (j <= right) { *(tempArr + k) = *(arr + j); j++; k++; } for (int m = 0; m < k; m++) { *(arr + left + m) = *(tempArr + m); (*moveCount)++; } free(tempArr); } // 基数排序 void radixSort(int* arr, int length, int* compareCount, int* moveCount) { int max = *arr; for (int i = 1; i < length; i++) { (*compareCount)++; if (*(arr + i) > max) { max = *(arr + i); } } int exp = 1; int* tempArr = (int*)malloc(sizeof(int) * length); while (max / exp > 0) { int bucket[10] = {0}; for (int i = 0; i < length; i++) { bucket[(*(arr + i) / exp) % 10]++; } for (int i = 1; i < 10; i++) { bucket[i] += bucket[i - 1]; } for (int i = length - 1; i >= 0; i--) { tempArr[bucket[(*(arr + i) / exp) % 10] - 1] = *(arr + i); bucket[(*(arr + i) / exp) % 10]--; } for (int i = 0; i < length; i++) { *(arr + i) = *(tempArr + i); (*moveCount)++; } exp *= 10; } free(tempArr); } int main() { int length = 100; int* arr1 = generateRandomArray(length); int* arr2 = generateRandomArray(length); int* arr3 = generateRandomArray(length); int* arr4 = generateRandomArray(length); int* arr5 = generateRandomArray(length); int compareCount, moveCount; compareCount = 0; moveCount = 0; straightInsertionSort(arr1, length, &compareCount, &moveCount); printf("直接插入排序：关键字比较次数：%d，关键字移动次数：%d\n", compareCount, moveCount); compareCount = 0; moveCount = 0; quickSort(arr2, 0, length - 1, &compareCount, &moveCount); printf("快速排序：关键字比较次数：%d，关键字移动次数：%d\n", compareCount, moveCount); compareCount = 0; moveCount = 0; shellSort(arr3, length, &compareCount, &moveCount); printf("希尔排序：关键字比较次数：%d，关键字移动次数：%d\n", compareCount, moveCount); compareCount = 0; moveCount = 0; bubbleSort(arr4, length, &compareCount, &moveCount); printf("冒泡排序：关键字比较次数：%d，关键字移动次数：%d\n", compareCount, moveCount); compareCount = 0; moveCount = 0; selectionSort(arr5, length, &compareCount, &moveCount); printf("简单选择排序：关键字比较次数：%d，关键字移动次数：%d\n", compareCount, moveCount); compareCount = 0; moveCount = 0; heapSort(arr1, length, &compareCount, &moveCount); printf("堆排序：关键字比较次数：%d，关键字移动次数：%d\n", compareCount, moveCount); compareCount = 0; moveCount = 0; mergeSort(arr2, 0, length - 1, &compareCount, &moveCount); printf("归并排序：关键字比较次数：%d，关键字移动次数：%d\n", compareCount, moveCount); compareCount = 0; moveCount = 0; radixSort(arr3, length, &compareCount, &moveCount); printf("基数排序：关键字比较次数：%d，关键字移动次数：%d\n", compareCount, moveCount); free(arr1); free(arr2); free(arr3); free(arr4); free(arr5); return 0; } ```