c++ - 如何在C++中使用sort()函数一起做某事？

This question already has answers here:

Sorting two corresponding arrays
                                
                                    （4个答案）
                                
                        
                                4年前关闭。
            
                    
我有两个数组

(i) arrStart[]={0 1 3 5 6 8 10 12 15};
(ii) arrEnd[]={4 2 7 11 16 9 14 13 17};

我想对arrEnd[]进行排序，以使arrStart[]中的相应整数也可以与arrEnd[]的整数交换匹配，例如

输出：

(i) arrStart[]={1 0 3 8 5 12 10 6 15};
(ii) arrEnd[]={2 4 7 9 11 13 14 16 17};

我在用

sort(arrEnd,arrEnd+8);

有没有什么逻辑可以超过输出，这样我就可以摆脱写作
完整的排序算法？

最佳答案

方法1：创建一个索引数组0到n-1；使用带有lambda比较的sort来比较arrEnd []元素。然后，使用排序后的索引根据排序后的索引数组对两个数组重新排序。

方法2：创建指向arrEnd []元素的指针数组，然后使用比较函数对指针数组进行排序。比较功能只需要知道元素的类型。然后根据排序的指针数组对两个数组重新排序。

方法2的示例。就地重新排序时间复杂度是线性的O（n）。

bool compare(const int *p0, const int *p1)
{
    return *p0 < *p1;
}

int main()
{
int a[8] = {7,5,0,6,4,2,3,1};
char b[8] = {'h','f','a','g','e','c','d','b'};
int *pa[8];
size_t i, j, k;
int ta;
char tb;
    // create array of pointers to a[]
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        pa[i] = &a[i];
    // sort array of pointers to a[]
    std::sort(pa, pa+sizeof(a)/sizeof(a[0]), compare);
    // reorder a[] and b[] according to the array of pointers to a[]
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
        if(i != pa[i]-a){
            ta = a[i];
            tb = b[i];
            k = i;
            while(i != (j = pa[k]-a)){
                a[k] = a[j];
                b[k] = b[j];
                pa[k] = &a[k];
                k = j;
            }
            a[k] = ta;
            b[k] = tb;
            pa[k] = &a[k];
        }
    }
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        std::cout << a[i] << ' ';
    std::cout << std::endl;
    for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
        std::cout << b[i] << ' ';
    std::cout << std::endl;
    return 0;
}