C++自定义Array类实现插入删除后无法完成升序排序问题求助

现有代码核心问题修复 #

1. 插入逻辑错误 #

你的插入函数中比较的是变量的内存地址而非数值，这是插入逻辑失效的核心原因，将while (&num < &arr[index] && index < size)修改为while (index < size && num > arr[index])即可匹配升序插入的找位逻辑。

2. 移位辅助函数实现错误 #

当前的moveTowardEnd和moveTowardFront仅交换了指定位置和数组末尾元素，并未实现插入/删除需要的整体移位效果，正确实现如下：

// 把index及之后的元素全部往后挪一位，空出index位置给新元素
void Array::moveTowardEnd(int index)
{
    for (int i = size; i > index; --i) {
        arr[i] = arr[i-1];
    }
}

// 把index之后的元素全部往前挪一位，覆盖index位置的元素
void Array::moveTowardFront(int index)
{
    for (int i = index; i < size - 1; ++i) {
        arr[i] = arr[i+1];
    }
}

3. 升序排序实现 #

如果需要单独实现排序方法，直接给Array类加一个sort成员函数即可，arr指针本质就是堆上的int数组首地址，普通排序逻辑可以直接复用，不需要特殊指针操作，示例（冒泡排序）：
首先在类的public区域加声明：void sort();
实现：

void Array::sort()
{
    for (int i = 0; i < size - 1; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

如果想每次打印都输出有序结果，直接在print函数开头调用const_cast<Array*>(this)->sort()即可。

修复后完整可运行代码 #

#include <iostream>
using namespace std;
class Array //The array class
{
private:
     int capacity{};
     int size{};
     int* arr{};
     void moveTowardFront(int index);
     void moveTowardEnd(int index);
public:
     Array(int capacity);
     ~Array();
     void insert(int num);
     void print() const;
     void remove(int num);
     void sort(); // 新增排序方法声明
};

void Array::sort()
{
    for (int i = 0; i < size - 1; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void Array::insert(int num)
{
    if (size >= capacity) {
        cout << "数组已满，插入失败" << endl;
        return;
    }
    if (size == 0)
    {
        arr[0] = num;
        size++;
        return;
    }
    int index = 0;
    // 修正为比较数值，找第一个比num大的元素位置，保证升序
    while (index < size && num > arr[index])
    {
        index++;
    }
    moveTowardEnd(index);
    arr[index] = num;
    size++;
}

void Array::remove(int num)
{
    int index = 0;
    while (index < size && num != arr[index])
    {
        index++;
    }
    if (index == size)
    {
        cout << num << " is not in the list. ";
        cout << "No removal." << endl;
        return;
    }
    moveTowardFront(index);
    size--;
}

void Array::print() const
{
    // 如果你要每次打印都先排序，取消注释下一行即可
    // const_cast<Array*>(this)->sort();
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
}

void Array::moveTowardEnd(int index)
{
    for (int i = size; i > index; --i) {
        arr[i] = arr[i-1];
    }
}

void Array::moveTowardFront(int index)
{
    for (int i = index; i < size - 1; ++i) {
        arr[i] = arr[i+1];
    }
}

Array::~Array()
{
    delete[]arr;
}

Array::Array(int cap)
    :capacity(cap)
{
    arr = new int[capacity] {};
    size = 0;
}

int main()
{
    Array array(20);
    array.insert(15);
    array.insert(13);
    array.insert(10);
    array.insert(14);
    array.insert(11);
    array.insert(17);
    array.insert(14);
    cout << "Printing array after insertions: " << endl;
    array.sort(); // 调用排序
    array.print();
    cout << endl;
    array.remove(13);
    array.remove(11);
    cout << "Printing array after removals: " << endl;
    array.sort();
    array.print();
    cout << endl;
    array.insert(8);
    array.insert(22);
    cout << "Printing array after more insertion" << endl;
    array.sort();
    array.print();
    cout << endl;
    array.remove(31);
    return 0;
}

内容的提问来源于stack exchange，提问作者Angel Armendariz