n个数从小到大排序

### 关于N个数从小到大排序的算法 对于N个数从小到大排序的问题，可以采用多种经典的排序算法来实现。以下是几种常见的排序算法及其具体实现方式。 #### 冒泡排序 冒泡排序是一种简单的排序算法，其基本思想是比较相邻的元素并交换顺序错误的元素位置。通过多次遍历数组，每次都将当前未排序部分的最大值移动到最后的位置。完成整个过程需要 $ N-1 $ 趟操作[^1]。 下面是基于C语言的冒泡排序实现： ```c void bubble_sort(int arr[], int sz) { for (int i = 0; i < sz - 1; i++) { // 控制趟数 for (int j = 0; j < sz - 1 - i; j++) { // 每一趟比较次数逐渐减少 if (arr[j] > arr[j + 1]) { // 如果前一个大于后一个，则交换 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } ``` 调用该函数即可对任意大小为 `sz` 的整型数组进行升序排列。 --- #### 插入排序 插入排序的核心思想是将待排序的数据逐个插入已排好序的部分中，从而逐步扩展有序序列直到全部数据都处理完毕。这种方法适合少量数据或者接近有序的情况。 下面是一个典型的插入排序代码示例： ```c void insertion_sort(int arr[], int sz) { for (int i = 1; i < sz; 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; // 将key放到正确的地方 } } ``` 此版本的时间复杂度平均情况下为 $ O(N^2) $ ，但在几乎有序的情况下表现更优。 --- #### 快速排序 快速排序是一种分治策略的应用实例之一，它选取一个基准值（pivot），然后按照这个基准划分数组成两半——左边小于等于基准而右边大于基准；接着递归地应用相同逻辑至子区间直至完全有序为止。 这里给出一种标准形式的快速排序程序如下所示: ```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); } } ``` 这种排序方法通常具有较好的性能，在理想条件下时间复杂度可达 $ O(N \log N) $ 。然而最坏情况下的效率会退化到 $ O(N^2) $ [^2]。 --- #### 归并排序 最后介绍的是归并排序，这是一种稳定的排序技术，也是运用了分治的思想。先分别独立地把每一段各自排好序后再合并起来形成整体有序状态的过程称为“归并”。 其实现流程大致分为三步： 1. 把原始列表拆分成若干个小片段； 2. 对这些小片单独做内部调整使其局部达到次序关系； 3. 合并各个单元使之成为全局满足条件的整体结构。 对应的伪码描述如下： ```c void merge(int arr[], int l, int m, int r) { 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; int j = 0; int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } ``` 这种方式同样具备较高的稳定性以及良好的渐近运行速度特性即 $ O(N\ log\ N)$ 时间消耗水平下运作良好[^2]。 --- ### 总结 以上介绍了四种常用的排序算法：冒泡排序、插入排序、快速排序和归并排序。它们各有特点适用于不同场景需求之中。当面对较大规模输入集时建议优先考虑后者两类高效能方案以获得更快执行效果。