有1，2...一直到n的无序数组，求排序算法，时间复杂度为O(n)，空间复杂度为O(1)

空间复杂度为O(n)意味着算法在最坏的情况下需要额外的空间与输入数据的数量成线性关系。对于给定一组无序的整数数组，我们想要找到排序后的数组中相邻两项之间的最大差值，一种简单而空间效率高的方法是使用原地排序算法，如快速排序、堆排序或者冒泡排序的改进版本。 这里我们可以考虑使用插入排序的一个变体，同时记录每次插入过程中新元素与前一个元素的差值，这个差值就是当前的最大差值候选。因为插入排序的时间复杂度为O(n^2)，但它不需要额外的存储空间，所以空间复杂度为O(1)，这满足了题目要求的O(n)条件。 以下是插入排序并记录最大差值的伪代码： ```c void find_max_difference(int arr[], int n) { int max_diff = INT_MIN; // 初始化为负无穷大 for (int i = 1; i < n; i++) { int current_val = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > current_val) { // 插入过程 arr[j + 1] = arr[j]; max_diff = max(max_diff, arr[j + 1] - current_val); // 更新最大差值 j--; } arr[j + 1] = current_val; // 插入当前值 } printf("最大差值: %d", max_diff); } ``` 在这个实现中，`find_max_difference`函数会直接修改输入数组，并返回最大差值。如果对原始数组保持不变的需求很明确，那么可以先复制一份再操作，但这将增加一次O(n)的临时空间消耗。

### 各种排序算法的时间复杂度分析 #### 归并排序 归并排序的核心思想是将待排序序列分为若干个子序列，每个子序列是有序的；然后逐步合并这些有序子序列直到形成完整的有序序列。其时间复杂度对于最好、最坏和平均情况均为 \(O(n \log n)\)[^1]。 ```python def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left_half = merge_sort(arr[:mid]) right_half = merge_sort(arr[mid:]) return merge(left_half, right_half) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result ``` #### 快速排序 快速排序是一种基于分治法的高效排序方法。它的性能取决于划分过程产生的子数组大小分布。在最坏情况下（如已完全逆序），时间复杂度为 \(O(n^2)\); 而在理想条件下（每次均勻分割数组），时间复杂度则达到最优状态 \(O(n \log n)\)[^3]。 平均时间复杂度同样为 \(O(n \log n)\)[^2]。 #### 插入排序 直接插入排序的基本操作是在已经排好的数据序列中找到合适的位置并将新元素插入进去。该算法简单易懂，但对于大规模无序列表效率较低。最佳情形下的时间复杂度为 \(O(n)\), 当输入几乎已经是正向顺序时表现良好；然而，在最差状况下需执行约 \(n*(n-1)/2\) 次比较动作，因此具有较高的二次方级运算负担——即 \(O(n^2)\)[^4]。 #### 希尔排序 作为改进版的插入排序形式之一，希尔排序通过设定间隔参数来减少不必要的局部调整工作量，从而提升整体运行速度。尽管如此，由于具体实现细节差异较大，确切的大 O 表达式难以统一给出，但通常认为优于传统单纯线性平方级别处理方式 [^2]. #### 计数排序 适用于一定条件的数据集上的非比较型整数排序方案。假设 k 是所有可能出现的最大数值加一，则此技术仅需遍历原始集合两次即可完成任务，故理论上可达成接近线性的效能指标 —— 大致等于 \(O(k+n)\). 不过需要注意的是，这种方法的空间消耗也相应较高，并且适用场景有限制 [^5]: ```python def counting_sort(arr, max_val): m = max_val + 1 count = [0] * m for a in arr: count[a] += 1 i = 0 for a in range(m): for c in range(count[a]): arr[i] = a i += 1 return arr ```