C++U3-第2课-基础排序(二)

【题意分析】
1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到该位置后;

【思路分析】
从当前a[i]的位置从后往前开始找，使用while循环，从当前的位置向前找，如果前面的数大于现在选择要插入的数，那么将前面的数往后移动一位最后用for循环输出这一趟排序的结果。

输入n一个数组

从第二位开始进行插入排序

当前需要插入的数为当前的第i个数，从后往前比较

如果j不小于1，并且前面的数比当前需要插入的数大，那么将前一位的数后移

插入当前的数，并且把这一趟插入后的数组输出


【参考代码】
#include <iostream>
using namespace std;
int a[110];
int main() {
    //输入n一个数组
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //从第二位开始进行插入排序
    for (int i = 2; i <= n; i++) {
        //当前需要插入的数为当前的第i个数，从后往前比较
        int key = a[i], j = i - 1;
        //如果j不小于1，并且前面的数比当前需要插入的数大，那么将前一位的数后移
        while (j >= 1 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        //插入当前的数，并且把这一趟插入后的数组输出
        a[j + 1] = key;
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

桶排序这段代码是使用桶排序算法对输入的数组进行排序。下面是对代码的详细思路解释：

cpp
#include <iostream>
using namespace std;

int a[110]; // 定义一个大小为110的整数数组a

int main() {
    int n;
    cin >> n; // 输入n，表示数组中元素的个数

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x; // 输入数组中的元素x

        a[x]++; // 将出现的数字x用桶标记，即在数组a中对应位置上加1
    }

    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= a[i]; j++) {
            // 遍历数组a，输出i出现a[i]次，即输出a[i]个i
            cout << i << " ";
        }
    }

    return 0;
}
代码的具体思路如下：

1声明一个大小为110的整数数组 a，用于存储待排序数组中每个数字的出现次数。数组下标代表数字，数组值代表该数字的出现次数。
2读取输入的整数 n，表示待排序数组中元素的个数。
3使用 for 循环遍历 n 次，每次读取一个元素 x。
4在数组 a 中将元素 x 对应的位置 a[x] 的值加1，表示数字 x 出现了一次。
5使用两层嵌套的 for 循环，外层循环从1到100，内层循环根据数组 a 的值逐个输出数字。
6外层循环变量 i 代表数字，内层循环变量 j 遍历该数字出现的次数 a[i]。
7在内层循环中，每次输出数字 i，即将该数字按照出现次数逐个输出。
8完成排序后，返回0表示程序正常结束。
9桶排序算法利用了一个辅助的桶数组，将待排序的元素根据其值放置到对应的桶中，然后按照桶的顺序依次输出元素，实现排序。在这段代码中，通过数组 a 来作为桶，记录每个数字在输入数组中出现的次数，并按照顺序输出相应的数字。

【题意分析】
需要将每一个数放入到桶，然后从小到大遍历桶，如果桶不为0，那么有多少个就输出多少次

【思路分析】
设计一定数值范围的 "桶"，将属于这个范围的数值按下标，以计数的方式记录到 "桶" 中，然后根据记录的数量，输出多少次即可。

输入n和数组，并且将出现的数用桶标记

遍历数组cnt，注意遍历的范围是数字的范围（1~100）

i出现的次数是 a[i],则输出 a[i]个i

【参考代码】
#include <iostream>
using namespace std;
int a[110];
int main() {
    //输入n和数组，并且将出现的数用桶标记
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x; 
        a[x]++;
    }
    //遍历数组cnt，注意遍历的范围是数字的范围（1~100）
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= a[i]; j++) {
            //i出现的次数是 a[i],则输出 a[i]个i
            cout << i << " ";
        }
    }
    return 0;
}

【题意分析】
将当前数组放入到sort中直接排序一遍就可以得出答案了

【思路分析】
sort函数没有第三个参数，默认为升序

输入n并且输入n的数组

用sort排序完毕后直接输出

【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
int main() {
    //输入n并且输入n的数组
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //用sort排序完毕后直接输出
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}