根据另一个数组定义的顺序对一个数组进行排序

使用案列

arr1[] = { 2,1,2,5,1,3,6,8,8 }

arr2[] = { 2,1,8,3}
2 2 1 1 8 8 3 5 6

A1根据A2排序。

根据另一个数组定义的顺序对数组进行排序的算法

1. Sort the array using the qsort method or comparator interface.
2. Search the value in arr2[] and find its index value.
3. Check if
1. Both of the returned value is -1 if true then return the difference between the returned value.
2. If one of the first returned values is -1 if true then return the -1.
3. If the second returned value is -1, then return 1.
4. Else return the value of the difference of the input value.
5. Print the sorted array.

代码

C ++代码根据另一个数组定义的顺序对数组进行排序

#include <stdio.h>
#include<iostream>

using namespace std;

int Arr2[4];

int size = 4;

int searchElement(int key)
{
int i;
for (i = 0; i < size; i++)
if (Arr2[i] == key)
return i;
return -1;
}

int compareValuesFromArray(const void* a, const void* b)
{
int eleIndex1 = searchElement(*(int*)a);
int eleIndex2 = searchElement(*(int*)b);
if (eleIndex1 != -1 && eleIndex2 != -1)
return eleIndex1 - eleIndex2;
else if (eleIndex1 != -1)
return -1;
else if (eleIndex2 != -1)
return 1;
else
return (*(int*)a - *(int*)b);
}

void sortAccAnotherArray(int A1[], int size1)
{
qsort(A1, size1, sizeof(int), compareValuesFromArray);
}

int main()
{
int Arr1[] = {1,4,2,4,6,4,7,2,2,3 };
int Arr2[]= {1,2,3,4};
int n = sizeof(Arr1) / sizeof(Arr1[0]);

sortAccAnotherArray(Arr1, n);

for (int i = 0; i <n; i++)
printf("%d ", Arr1[i]);
return 0;
}
1 2 2 2 3 4 4 4 6 7

Java代码根据另一个数组定义的顺序对数组进行排序

import java.util.*;
import java.util.Arrays;

class SortAnArray
{
private static int Arr1[] = { 1,4,2,4,6,4,7,2,2,3};
private static int Arr2[]= {1,2,3,4};

private static int size = Arr2.length;

public static int searchElement(int key)
{
int i;
for (i = 0; i < size; i++)
if (Arr2[i] == key)
return i;
return -1;
}

public static void sortAccAnotherArray(int A1[], int size1)
{
Integer[]sortedArr = Arrays.stream(A1).boxed().toArray(Integer[]::new);

Arrays.sort(sortedArr, new Comparator<Integer>()
{
public int compare(Integer o1, Integer o2)
{

int a = o1.intValue();
int b = o2.intValue();

int eleIndex1 = searchElement(a);
int eleIndex2 = searchElement(b);

if (eleIndex1 != -1 && eleIndex2 != -1)
return eleIndex1 - eleIndex2;
else if (eleIndex1 != -1)
return -1;
else if (eleIndex2 != -1)
return 1;
else
return (a - b);
}
});
int[] finalArr = Arrays.stream(sortedArr).mapToInt(Integer::intValue).toArray();
System.out.println(Arrays.toString(finalArr));
}

public static void main(String [] args)
{

int n = Arr1.length;

sortAccAnotherArray(Arr1, n);
}

}

[1, 2, 2, 2, 3, 4, 4, 4, 6, 7]

复杂度分析

时间复杂度

O（mn Logm） 哪里 “m”个 是arr1的长度＆ “ n” 是arr2的长度。 由于我们使用了qsort（排序算法）。 我们已经实现了 O（n log n） 因素。 在这里，搜索是使用线性搜索完成的。 而不是这样做，我们可以轻松地使用HashMap，这将进一步降低时间复杂度。

空间复杂度

O（log n）， 哪里 “m”个“ n” 是Arr1和Arr2的长度。 因为我们已经使用快速排序完成了排序，所以空间复杂度就是因为这个原因。 但是整个程序需要 O（N + M）。