给定一个按非递增顺序排序的整数数组A，用c语言设计一个算法，返回一个新数组，该数组包含原数组中每个整数的立方，并且这个新数组需要按非递减顺序排序。

要实现这个算法，我们可以利用C语言进行以下步骤的操作：

1. 创建一个新的数组B，用于存放原数组A中每个整数的立方。
2. 对数组B进行排序，因为原数组A是非递增排序的，立方操作可能会改变数值的大小关系，因此需要对立方后的数组B进行排序，使其变为非递减顺序。
3. 返回排序后的数组B。

这里可以使用快速排序或者插入排序等排序算法，由于我们只需要对一个数组进行操作，并且该数组是随机的，因此这里提供了一个基于插入排序的示例代码：

#include <stdio.h>

// 插入排序函数，用于对立方后的数组进行排序
void insertionsort(int *arr, int n) {
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 主函数，返回新数组
int* getCubeSortedArray(int* A, int n, int* returnSize) {
    // 分配新数组的空间，大小为原数组长度n
    int *B = (int *)malloc(n * sizeof(int));
    // 对原数组每个元素求立方，并存入新数组B
    for (int i = 0; i < n; ++i) {
        B[i] = A[i] * A[i] * A[i];
    }
    // 对新数组B进行插入排序
    insertionsort(B, n);
    // 由于排序后的数组是局部变量，返回时需要分配动态内存
    int *sortedCubes = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        sortedCubes[i] = B[i];
    }
    // 释放原数组B的空间
    free(B);
    // 返回排序后的立方数组
    *returnSize = n;
    return sortedCubes;
}

int main() {
    int A[] = { -1, -10, -2, -5, -9 };
    int returnSize;
    int* result = getCubeSortedArray(A, sizeof(A) / sizeof(A[0]), &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    // 释放结果数组的空间
    free(result);
    return 0;
}

需要注意的是，因为排序后的数组B需要作为函数的返回值返回给调用者，而函数返回的局部变量的地址在函数返回后将不再有效，所以需要动态分配内存给排序后的数组，并在使用完毕后由调用者负责释放。