用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

相关问题

现有一n 个数的序列，给定一个定值k.每次我们可以选择数列中一个下标为 2 的次幂的元素将其删除出数列（删除后，其后的所有元素会自动前移一格）。 问最少进行多少次操作，能将序列中所有值为k 的元素删除？ 输入描述 第一行 两个整数n,k 第二行 n 个整数 输出描述 第一行一个整数，为最少操作次数。 样例输入 5 2 1 2 4 2 5 c++实现

题目分析：

题目明确要求删除所有值为k的元素，那么我们可以考虑先记录下所有值为k的元素的下标，然后再从后往前删。因为每次删掉一个元素会导致后面的元素整体前移，所以从后往前删能够保证元素的相对位置不变。

另外，若要删除下标为 i 的元素，则需要将下标为 2i 的元素加入待删除的序列中。这是因为，下标为 2i 的元素在删除下标为 i 的元素后，会自动前移一格，变成下标为 2i-1 的元素。

算法流程：

- 遍历序列，记录下所有值为k的元素的下标；
- 从后往前遍历序列，依次删除所有值为k的元素，并将它们对应的下标的2倍加入待删除的序列中；
- 若待删除的序列不为空，则继续从后往前遍历序列，删除所有待删除元素，并将它们对应的下标的2倍加入待删除的序列中；
- 重复步骤3，直到待删除的序列为空。

代码实现：

给定一个整数 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)。