写出一个反转输出数组(n个数)的c++程序

以下为反转输出数组的C程序：

#include <stdio.h>

int main() {
    int n;
    printf("请输入数组中元素的个数：");
    scanf("%d", &n);
    int arr[n];
    printf("请输入数组元素：");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("原数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n反转后的数组：");
    for (int i = n - 1; i >= 0; i--) {
        printf("%d ", arr[i]);
    }
    return 0;
}

在该程序中，首先要求用户输入数组中元素的个数n，然后根据n动态创建数组arr。接着，程序要求用户输入数组元素，并使用for循环将其存入arr中。然后，程序使用for循环依次输出原数组中的元素。最后，程序使用for循环逆序输出数组arr中的元素，实现反转输出数组的功能。

相关问题

C++写数组的反转计数指示, 数组排序的距离。如果数组已经排序，则反转计数为0，但是如果数组以相反顺序排序，则反转计数为最大值。 如果a [i]> a [j]且i <j，则两个元素a [i]和a [j]构成一个倒置

可以使用归并排序来计算数组的反转计数和排序距离。在归并排序的过程中，每当从右子数组中复制一个元素时（右子数组中的元素比左子数组中的元素小），就可以计算出对应的反转计数。在归并排序结束时，左子数组和右子数组都是已排序的，可以计算出排序距离。

以下是C++代码示例：

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

int merge(vector<int>& arr, int left, int mid, int right, vector<int>& temp) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    int count = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += mid - i + 1; // 统计反转计数
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
    return count;
}

int mergeSort(vector<int>& arr, int left, int right, vector<int>& temp) {
    int count = 0;
    if (left < right) {
        int mid = (left + right) / 2;
        count += mergeSort(arr, left, mid, temp);
        count += mergeSort(arr, mid + 1, right, temp);
        count += merge(arr, left, mid, right, temp);
    }
    return count;
}

int reverseCount(vector<int>& arr) {
    vector<int> temp(arr.size());
    return mergeSort(arr, 0, arr.size() - 1, temp);
}

int sortDistance(vector<int>& arr) {
    vector<int> sortedArr(arr.begin(), arr.end());
    sort(sortedArr.begin(), sortedArr.end());
    int distance = 0;
    for (int i = 0; i < arr.size(); i++) {
        distance += abs(lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]) - sortedArr.begin() - i);
    }
    return distance / 2; // 因为每个元素都被计算了两次
}

int main() {
    vector<int> arr{3, 1, 2, 4, 5};
    cout << "Reverse count: " << reverseCount(arr) << endl;
    cout << "Sort distance: " << sortDistance(arr) << endl;
    return 0;
}

上述代码中，merge函数用于将两个已排序的子数组合并，并计算反转计数。mergeSort函数使用归并排序算法，计算数组的反转计数并返回已排序的数组。reverseCount函数调用mergeSort函数并返回反转计数。sortDistance函数计算排序距离。注意，sortDistance函数使用lower_bound函数查找元素在已排序数组中的位置，并使用abs函数计算位置之差的绝对值。由于每个元素都被计算了两次，因此需要将结果除以2。

给定一个数字序列a，设计一个计算逆序次数的算法，其中逆序是i < j和ai > aj的一对(ai,aj)。 ，设计一个O(n log n)时间算法，计算a中的反转次数。并用C++写出该算法

### 回答1：

答：可以使用归并排序算法来计算反转次数。归并排序的过程分为两个步骤，其中第一步是将数组分解成若干个独立的小数组，然后在第二步中归并它们。在归并的过程中，可以记录反转的次数，它的复杂度为O(n log n)。具体的实现可以参考下面的C代码： int merge_sort(int arr[], int l, int r)
{
int count = 0;
if (l < r)
{
int m = l+(r-l)/2;
count += merge_sort(arr, l, m);
count += merge_sort(arr, m+1, r);
count += merge(arr, l, m, r);
}
return count;
} int merge(int arr[], int l, int m, int r)
{
int count = 0;
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, j = 0;
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
// 如果右边的数小于左边的数，则计数器加上右边剩余数的个数
count = count + (n1 - i);
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
return count;
}

### 回答2：
给定一个数字序列a，计算逆序次数的算法可以通过归并排序的方式实现，其时间复杂度为O(n log n)。

算法步骤如下：
1. 将数字序列a拆分成两个子序列，分别为左子序列和右子序列。
2. 对左子序列和右子序列分别进行递归调用，直到子序列中只有一个数字。
3. 对两个子序列进行合并操作，合并排序后的结果存储在一个临时数组中。
4. 在合并的过程中，如果左子序列中的数字大于右子序列中的数字，则计算逆序次数。
5. 将合并排序后的结果复制回原始数组a中。

以下是使用C语言实现该算法的代码示例：

#include <stdio.h>

int merge(int arr[], int temp[], int left, int mid, int right){
    int i = left, j = mid, k = left, count = 0;
    
    while(i <= mid-1 && j <= right){
        if(arr[i] <= arr[j]){
            temp[k++] = arr[i++];
        }
        else{
            temp[k++] = arr[j++];
            count += mid - i;
        }
    }
    
    while(i <= mid - 1){
        temp[k++] = arr[i++];
    }
    
    while(j <= right){
        temp[k++] = arr[j++];
    }
    
    for(i = left; i <= right; i++){
        arr[i] = temp[i];
    }
    
    return count;
}

int mergeSort(int arr[], int temp[], int left, int right){
    int mid, count = 0;
    
    if(right > left){
        mid = (left + right) / 2;
        count += mergeSort(arr, temp, left, mid);
        count += mergeSort(arr, temp, mid+1, right);
        count += merge(arr, temp, left, mid+1, right);
    }
    
    return count;
}

int getInverseCount(int arr[], int n){
    int temp[n];
    return mergeSort(arr, temp, 0, n-1);
}

int main(){
    int arr[] = {3, 1, 2, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    int inverseCount = getInverseCount(arr, n);
    
    printf("逆序次数: %d\n", inverseCount);
    
    return 0;
}

该算法通过归并排序的方式将数组进行排序，并在排序的过程中计算逆序次数。在主函数中，给定一个数组arr并调用getInverseCount函数，可以得到该数组中的逆序次数。以上代码输出的结果为：逆序次数: 3。

### 回答3：
逆序次数的算法可以用分治算法来设计。具体步骤如下：
1. 首先将原始序列a分成两个子序列a1和a2，分别计算出a1和a2中的逆序次数，递归地调用该算法。
2. 然后将a1和a2归并排序得到有序的序列b。在归并排序的过程中，可以计算出a1和a2之间的逆序对数目。
3. 将b重新合并成原始序列a。

这个算法的时间复杂度为O(n log n)。具体的C代码如下：

#include <stdio.h>

// 合并两个有序序列并计算逆序次数
int merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    int count = 0;

    while (i <= mid && j <= right) {
        if (arr[i] > arr[j]) {
            temp[k++] = arr[j++];
            // 如果arr[i] > arr[j]，说明存在逆序对，逆序次数加上 j-mid
            count += mid - i + 1;
        } else {
            temp[k++] = arr[i++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (int m = left; m <= right; m++) {
        arr[m] = temp[m];
    }

    return count;
}

// 归并排序并计算逆序次数
int mergeSort(int arr[], int temp[], int left, int right) {
    int count = 0;

    if (left < right) {
        int mid = (left + right) / 2;
        count += mergeSort(arr, temp, left, mid);
        count += mergeSort(arr, temp, mid + 1, right);
        count += merge(arr, temp, left, mid, right);
    }

    return count;
}

int main() {
    int arr[] = {5, 2, 6, 1, 3, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int temp[n];

    int count = mergeSort(arr, temp, 0, n - 1);

    printf("逆序次数：%d\n", count);

    return 0;
}