用C++给定一个长度为n的整数数列，使用排序算法将序列排序后输出

这里提供一个简单的冒泡排序的实现，时间复杂度为O(n^2)：

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for(int i=0; i<n-1; i++) {
        for(int j=0; j<n-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

int main() {
    int n;
    cout << "请输入整数数列的长度: ";
    cin >> n;
    int arr[n];
    cout << "请输入整数数列: ";
    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }
    bubbleSort(arr, n);
    cout << "排序后的数列为: ";
    for(int i=0; i<n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

输入示例：

请输入整数数列的长度: 5
请输入整数数列: 3 1 4 2 5

输出示例：

排序后的数列为: 1 2 3 4 5

相关问题

请用C++选择排序法排序：输入数据个数n(1<n<100）及n个整数构成的 整数数列，要求对该整数序列进行排序，使其按升序排列． 预期结果： 输入：12,23,9,34,7 输出：7,9,12,23,34

在C++中，选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据排完。以下是使用选择排序对给定整数数组进行升序排序的示例：

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) { // 遍历所有数组元素
        int minIndex = i; // 初始化最小元素索引为当前遍历的位置

        // 找到未排序部分中的最小元素
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 将找到的最小元素与当前位置交换
        swap(arr[i], arr[minIndex]);
    }
}

// 测试函数
int main() {
    int data[] = {12, 23, 9, 34, 7};
    int size = sizeof(data) / sizeof(data[0]);

    cout << "原始数据：";
    for (int i = 0; i < size; i++) {
        cout << data[i] << " ";
    }
    cout << endl;

    selectionSort(data, size);

    cout << "升序排序后的数据：";
    for (int i = 0; i < size; i++) {
        cout << data[i] << " ";
    }
    cout << endl;

    return 0;
}

当你运行这个程序，会得到预期的结果：
输入：12,23,9,34,7
输出：7 9 12 23 34

给定一个整数 n，以及 n 个整数 a1, a2, ..., an。定义一个数列为「连续上升数列」，当且仅当该数列中任意相邻两项差均为 1，例如：1, 2, 4 和 4, 3, 2, 1 都不是连续上升数列，但 1, 2, 3, 4 是连续上升数列。现在你需要将 a1, a2, ..., an 中所有连续上升的子序列全部删除，求最后剩余数列的长度。输入：第一行一个整数 n，表示输入数列的长度 (1 < n < 10^5)。 第二行 n 个整数 a1, a2, ..., an，表示输入数列 (1 < ai < 10^6)。 输出：输出一个整数，表示最后剩余数列的长度。队列方法，c或c++

以下是C++代码实现队列方法解决该问题：

#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 1e5+5;
int n, a[MAXN];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    queue<int> q; // 定义一个队列，存储当前连续上升子序列的起点
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(q.empty() || a[i] != a[q.back()] + 1) { // 当前数不连续上升
            q.push(i); // 将当前数作为新的连续上升子序列起点
        } else { // 当前数连续上升
            q.pop(); // 弹出当前连续上升子序列的起点
            if(q.empty() || a[i] != a[q.back()] + 1) { // 弹出起点后，当前数不连续上升
                q.push(i); // 将当前数作为新的连续上升子序列起点
            }
        }
    }
    ans = n - q.size(); // 剩余数列长度为n减去连续上升子序列的数的个数
    cout << ans << endl;
    return 0;
}

算法思路：

对于任意一个连续上升子序列，它的起点是唯一的，而终点可以是任意一个大于起点的数。因此，我们可以用一个队列来存储当前连续上升子序列的起点，遍历整个数列，如果当前数不连续上升，则将当前数作为新的连续上升子序列的起点；如果当前数连续上升，则弹出队列中的起点，如果弹出起点后，当前数不连续上升，则将当前数作为新的连续上升子序列的起点。

最后剩余数列的长度为n减去连续上升子序列的数的个数，即队列中剩余的元素个数。

时间复杂度为O(n)。