函数题:数组排序

给定一个长度为?n的数组?a以及两个整数?l?和?r，请你编写一个函数，void sort(int a[], int l, int r)，将?a[l]～a[r] 从小到大排序。

输出排好序的数组?a。

输入格式

第一行包含三个整数?n，l，r。

第二行包含?n?个整数，表示数组?a。

输出格式

共一行，包含?n个整数，表示排序完成后的数组?a。

数据范围

0≤l≤r<n≤10000

输入样例：

5 2 4
4 5 1 3 2

输出样例：

4 5 1 2 3

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;

void sort(int a[], int l, int r)
{
    for (int i = l; i <= r; i++)
    {
        for (int j = i + 1; j <= r; j++)
        {
            if (a[i] > a[j])
                swap(a[i], a[j]);
        }
    }
}

int main()
{
    int n, l, r;
    int a[N];
    cin >> n >> l >> r;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, l, r);

    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';

    return 0;
}

从题目中给的示例可以很明白的看出，这是一道选择排序的题，虽然选择排序是最基础的排序，但是理解他也是必要的，这里只需要陈述一下选择排序的原理和画过程图就行了。?

?

选择排序是一种简单直观的排序算法，其原理是通过不断选择最小（或最大）的元素，并将其放置在已排序的序列末尾。具体操作过程如下：

1. 遍历数组，从第一个元素开始。
2. 在未排序部分中，找到最小（或最大）的元素，并记录其索引。
3. 将找到的最小（或最大）元素与当前遍历的元素交换位置，将最小（或最大）的元素放置在已排序序列的末尾。
4. 重复步骤2和3，直到所有元素都被排序。

我们从上面的过程图中可以看出，都是一个位置上排好了，确定了是最小的以后再轮到下一个位置排?。这其实说实话也是一种双指针算法的应用，先让i循环，表示有几个位置，循环几次。再设一个变量j，来依次来判断。举个例子，当i=0时，j=1，j从1开始，依次往后走，直到走到r结束为止。

当我们已经找到最小的值了，发现后面不用找的时候，这个循环还是会继续往后走，直到走到r为止，这就是这个的缺点，不灵活，找到了也要去做那些无用功，所以这个的时间复杂度高，不是没有原因的。

?所以总结看来，就是a[i]和a[j]在比较，进行不断的循环交换，最终得到排序后的数组。

选择排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。它是一种简单但效率较低的排序算法，在处理小规模数据或部分有序的情况下可能会有一定的应用。但对于大规模数据，更高效的排序算法如快速排序或归并排序更加适用。

常见的排序算法包括但不限于：

1. 冒泡排序（Bubble Sort）：通过依次比较相邻的元素，并交换顺序，使得每一轮循环结束时最大（或最小）的元素移动到最后。时间复杂度为O(n^2)。

2. 选择排序（Selection Sort）：每次在未排序部分中选择最小（或最大）的元素，放置到已排序部分的末尾。时间复杂度为O(n^2)。

3. 插入排序（Insertion Sort）：逐步构建有序序列，对于未排序部分的每个元素，在已排序部分找到合适的位置插入。时间复杂度为O(n^2)。

4. 快速排序（Quick Sort）：通过选择一个基准值，将数组分割成左右两部分，然后对左右部分分别进行快速排序。时间复杂度为O(nlogn)，是一种高效的排序算法。

5. 归并排序（Merge Sort）：将数组分割成若干子序列，然后将子序列两两合并并排序，直到整个数组有序。时间复杂度为O(nlogn)，同样是一种高效的排序算法。

6. 堆排序（Heap Sort）：利用堆这种数据结构进行排序，时间复杂度为O(nlogn)，且具有原地排序和稳定性。

7. 计数排序（Counting Sort）：适用于整数排序，时间复杂度为O(n+k)，其中k为待排序数组中的最大值。

8. 桶排序（Bucket Sort）：将待排序数组分割成若干个桶，对每个桶进行排序，然后按照顺序合并各个桶。时间复杂度取决于桶的数量和每个桶内使用的排序算法。

除了上述排序算法之外，还有许多其他的排序算法，每种算法都有其特点和适用场景。根据实际问题的特点和数据规模的大小，可以选择合适的排序算法来提高排序效率。

这些排序有兴趣的可以自己下去了解，这里我就不多赘述了。