如果输入数组定义为 const，我该如何对它进行排序？

Question

我正在尝试按升序对输入数组 pAddrSourceArray 进行排序，但输入数组被定义为 const，如下面 header 所示，这不可能自实施以来发生了变化。

到目前为止，我已经知道如何对数组进行排序，但是我正在努力克服输入数组被定义为常量的事实。我不能（或者我不知道）如何用输入数组的内容创建一个辅助数组，这样我就可以对这个辅助数组进行排序，然后分配给输出数组 pAddrResultArray

关于如何解决这个问题的任何提示？

void sortArray(uint32_t samplesCount, const int16_t *pAddrSourceArray, int16_t *pAddrResultArray)
{
    int16_t *pInputArray = pAddrSourceArray; // This is wrong, I know it should be const  int16_t *pInputArray = pAddrSourceArray;

    int16_t min_idx;

    // One by one move boundary of unsorted subarray
    for (uint32_t indxUnsort = 0; indxUnsort < samplesCount - 1; indxUnsort++ )
    {

        // Find the minimum element in unsorted array
        min_idx = indxUnsort;
        for (uint32_t k = indxUnsort + 1; k < samplesCount; k++)
        {
            if (pInputArray[k] < pInputArray[min_idx])
            {
                min_idx = k;
            }
        }

        // Store actual local min value
        int16_t localMin = pInputArray[min_idx];
        // Update new min at current indxUsort position
        pInputArray[min_idx] = pInputArray[indxUnsort];
        // Append the new local min found
        pInputArray[indxUnsort] = localMin;
    }

    // Assign sorted array to output array
    pAddrResultArray = pInputArray;
}

Answer 1

这是一种方法。它依次从输入数组中取出每个输入值，并将其插入输出数组中大于输入数组的输出数组的第一个元素的位置（如果有），否则在输出数组的末尾，洗牌输出数组的剩余元素加一。这确保到目前为止填充的输出数组始终按升序排列。

由于到目前为止的输出数组内容已经按升序排序，因此可以使用二进制搜索来确定插入输入值的位置。

O(N^2) 的总体平均时间复杂度主要是将元素插入到输出数组中，尽管到目前为止找到插入位置的二分查找有点帮助，为 O(log n)与线性搜索的 O(n) 相比。

void sortArray(uint32_t samplesCount, const int16_t* pAddrSourceArray, int16_t* pAddrResultArray)
{
    uint32_t s;

    for (s = 0; s < samplesCount; s++)
    {
        /* Get next value from input. */
        int16_t xs = pAddrSourceArray[s];
        uint32_t a, b;

        /* Find position where next value belongs in the output so far by a binary search. */
        a = 0;
        b = s;
        while (a < b)
        {
            uint32_t m = (a + b) / 2;

            if (xs < pAddrResultArray[m])
            {
                b = m;
            }
            else
            {
                a = m + 1;
            }
        }
        /* Insert value at position in output array, shuffling up remaining elements. */
        while (a < s)
        {
            int16_t xa = pAddrResultArray[a];

            pAddrResultArray[a] = xs;
            xs = xa;
            a++;
        }
        pAddrResultArray[a] = xs;
    }
}

Answer 2

您不应该就地对源数组进行排序，但您可以简单地将其复制到目标数组并使用您选择的方法对该数组进行就地排序：

#include <string.h>
#include <stdlib.h>

int cmp_int16_t(const void *p1, const void *p2) {
    const int16_t *s1 = p1;
    const int16_t *s2 = p2;
    return (*s1 > *s2) - (*s1 < *s2);
}

void sortArray(uint32_t samplesCount, const int16_t *pAddrSourceArray, int16_t *pAddrResultArray) {
    memmove(pAddrResultArray, pAddrSourceArray, samplesCount * sizeof(*pAddrResultArray));
    qsort(pAddrResultArray, samplesCount, sizeof(*pAddrResultArray), cmp_int16_t);
}

Answer 3

如果您知道它应该是 const，则将其声明为：

const int16_t *pInputArray

但是当您使用 const int16_t * 初始化 non-const 指针时，您应该至少收到来自编译器的警告（告诉类似于 initializer discards 'const' qualifier）。

如

void f(const int *a)
{
        int *b = a;
}

编译时给出：

pru58405.c:4:7: warning: initializing 'int *' with an expression of type 'const int *' discards qualifiers
      [-Wincompatible-pointer-types-discards-qualifiers]
        int *b = a;
             ^   ~
1 warning generated.

您在程序中管理的 objects 的 const 性在很大程度上取决于您用于变量的类型。一旦声明为非const，您就可以毫无问题地访问和修改它（除非它位于真正的只读段中，在这种情况下，如果您尝试修改值，您可能会得到一个异常)

由于您发布了一个不完整、无法验证的示例（请阅读标题为 How to create a Minimal, Reproducible Example 的页面），我们无法为您提供更多帮助。对此我深表歉意。

如果输入数组定义为 const，我该如何对它进行排序？

How can I sort my input array if it is defined as const?

c

arrays

sorting

constants