一个函数，它接受数组A和索引I并重新排列它

Question

问题是:将长度为n的数组A和索引I写入A中，并重新排列小于Ai的元素，使所有小于Ai的元素首先出现，然后是等于Ai的元素，然后是大于Ai的元素。

对我的代码的解释：

向用户询问n个数字，即11，然后问他要用什么索引来重新排列元素。它将它带到function1中，并创建一个for循环并执行一个if else语句。如果Ai < 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] << " ";
}

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

A0.x.n-1，其中x是代表ai的索引，但是我得到了不正确的输出，数字随机分布在各处。

我的逻辑怎么了？

Answer 1

问题是(就像Olaf指出的那样)，在需要两个索引的情况下，只取一个索引。此外，您无法知道是否要在新数组的中间插入既不小于a[ind]也不大于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，只要有空闲空间。然而，重新排列的元素还没有排序(除了相对于枢轴元素的位置)！

Answer 2

对于越来越小的值使用相同的索引i。这意味着，如果仅最后一个值a[10]大于x，那么您将在第一个位置newArray[10 - 10]中写入它，即使您已经填充了所有位置，直到第10个位置。另一个问题是，当您有多个middle值时。它们都将存储在newArray[5]中。

您想要实现的是分区，正如在快速排序算法中使用的那样。

您需要维护两个索引(指针)，一个用于较小的(左)，一个用于较大的(右)值。

Answer 3

您必须在开始时确定数组的大小，并将数组的固定大小作为参数传递给函数。