c++ - 对一系列数字进行排序 - 就地

Question

我正在尝试解决以下问题:

We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 1 to ‘n’ based on their creation sequence. This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’.

Write a function to sort the objects in-place on their creation sequence number in O(n)O(n) and without any extra space. For simplicity, let’s assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.

例如:输入:[2, 6, 4, 3, 1, 5]输出:[1, 2, 3, 4, 5, 6]

我的方法:

void sortInPlace(int *arr,int n){

    for(int i=0;i<n;i++){

        if(arr[i] != arr[arr[i]-1]){
            swap(arr[i],arr[arr[i]-1]);
        }
    }


}

int main(){

    int n;
    cout<<"\n Enter number of elements:";
    cin>>n;

    int arr[n];
    cout<<"\n Enter the elements :";
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    sortInPlace(arr,n);

    cout<<"\n Sorted Array :";
    for(int i = 0; i < n ; i++){

        cout<<arr[i];
    }

}

但是，这不会产生正确的结果。

实际解决方案:

我能找到的唯一区别是他们使用的 While 循环。

解决方案中的 while 循环有一个额外的迭代来递增“i”，而我的解决方案是在 for 循环中完成的，不需要额外的迭代。

例子:我的方法

Input : [1,5,6,4,3,2]
Output : [1,3,2,4,5,6]
Expected output : [1,2,3,4,5,6]

但是，为什么它不起作用？如果我遗漏了什么，有人可以告诉我吗？

Answer 1

在 for (int i=0; i < n; i++) 的每次迭代中, i递增。

while循环只递增 i如果没有进行交换。

要获得相同的行为，for版本不得增加 i进行交换时。