给定程序fun的数的功能是:将n个无序整数从小到大排序。用

### 排序算法的选择 对于将 n 个无序整数从小到大排序的任务，可以选择多种排序算法来完成。以下是几种常见的排序算法及其适用场景： #### 方法一：计数排序 如果数据范围较小且为整数，则可以考虑 **计数排序**。这是一种非基于比较的排序算法，时间复杂度为 O(n+k)，其中 k 是数据的最大值减去最小值[^1]。 然而需要注意的是，当数据范围极大时，计数数组会占用过多内存，因此在这种情况下不推荐使用此方法。 ```c void countingSort(int arr[], int size) { int max = arr[0], min = arr[0]; for (int i = 1; i < size; ++i) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } const int range = max - min + 1; int count[range] = {0}; for (int i = 0; i < size; ++i) { count[arr[i] - min]++; } int index = 0; for (int i = 0; i < range; ++i) { while (count[i]-- > 0) { arr[index++] = i + min; } } } ``` --- #### 方法二：插入排序 另一种简单易懂的方法是 **插入排序**。该算法通过逐步构建有序序列的方式工作，在每一步都将当前元素插入到已有的有序部分中[^2]。 尽管其最坏情况下的时间复杂度为 O(n²)，但对于几乎已经排好序的数据集来说表现良好。 ```c void insertionSort(int arr[], int size) { for (int i = 1; i < size; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } } ``` --- #### 方法三：快速排序 为了追求更高的性能，还可以采用更高效的分治策略——比如 **快速排序** 或者其他高级排序技术。这些通常具有平均时间为 O(n log n) 的特性，并广泛应用于实际编程环境中。 这里提供了一个经典的 C 风格实现版本供参考： ```c void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } int partition(int arr[], int low, int high) { 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]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } ``` --- ### 总结 以上展示了三种不同的排序方式以及它们各自的优缺点分析。具体选择哪一种取决于目标应用场景的具体需求，例如输入规模大小、数值分布特点等因素的影响。