c++ - 接受数组 A 和索引 i 并重新排列它的函数

Question

问题是:编写一个函数，将长度为 n 的数组 A 和索引 i 放入 A 中，并重新排列元素，使所有小于 A[i] 的元素首先出现，然后是等于 A 的元素[i]，后跟大于 A[i] 的元素。

我的代码说明:

向用户询问 n 个数字，即 11。并询问他想要重新排列元素的索引是什么。它将它带到 function1，并创建一个 for 循环并执行一个 if else 语句。如果 A[i] < A{index} ，则将其放在开头，否则如果较小，则将其放在末尾，或将其放在中间:

这是我的代码

#include <iostream>
using namespace std;

void function1(int a[], int ind);
int main()

{
    int a[11];
    int index;
    cout << " enter the numbers: " << endl;
    for(int i=0; i < 11; i++)
        cin >> a[i];

    cout << "what is the index ? " << endl;
    cin >> index;

    function1(a,index);
}

void function1(int a[], int ind)
{
    int x = a[ind];
    int newArray[11];
    for(int i=0; i < 11; i++)
    {
        if(a[i] < x)
        {
            newArray[i] = a[i];
        }
        else if(a[i] > x)
        {
            newArray[10-i] = a[i];
        }
        else
        {
            newArray[10/2] = a[i];
        }
    }

    for(int i=0; i<11; i++)
        cout << newArray[i] << " ";
}

我期望得到的输出是新数组的重新排列，它可能看起来类似于:

a[0....x....n-1]，其中x是代表a[i]的索引但是我得到的输出不正确，数字随机散布在

我的逻辑有什么问题？

Answer 1

问题在于(如 Olaf Dietsche 所指出的)在需要两个索引的地方您只使用一个索引。此外你无法知道是否要在中间插入既不小于也不大于a[ind](等于a[ind])的元素的新阵列。 (想象一下 3 2 1 和索引 3 结果为 2 1 3 但 3 不在中间!)

更新版本(允许多个元素与枢轴元素具有相同的值)

void rearange(int* data, int size, int pivot)
{
    int* temp_data = new int[size];
    int start_index = 0, end_index = size - 1;

    for (int i = 0; i < size; i++)
    {
        if (data[i] < data[pivot]) // -> insert 'before' pivot element
        {
            temp_data[start_index] = data[i];
            start_index++;
        }
        else if (data[i] > data[pivot]) // -> insert 'behind' pivot element
        {
            temp_data[end_index] = data[i];
            endIndex--;
        }
        // else: skip pivot(s)
    }

    // insert pivot element(s)
    for (int i = start_index; i <= end_index; i++)
    {
        temp_data[i] = data[pivot];
    }

    for (int i = 0; i < size; i++)
    {
        std::cout << temp_data[i] << " ";
    }
    delete[] temp_data;
}

输入:

11 10 9 8 7 7 7 6 5 4 3
5

输出

6 5 4 3 7 7 7 8 9 10 11

如您所见，所有小于元素 5(值为 7)的元素都在主元素之前，所有大于元素的元素都在主元素之后。与 pivot 具有相同值的所有其他元素都环绕在位置 5 周围，只要有空闲空间。然而，重新排列的元素尚未排序(除了相对于枢轴元素定位)!