Java-如何通过一个数组的已知字母顺序 对另外一个数组的字母进行排序

Question

如何通过一个数组的已知字母顺序 对另外一个数组的字母进行排序，比如a = [q,w,e,a,s] 现在有数组b=[w,a,q] 要求排序变成[q,w,a] 谢谢大家的指点。

Answer 1

根据楼主最新的更新：
题目可以理解成是：“已知两个数组a和b，所含元素没有排序；求数组c，c是a和b的交集，且c中的元素要保持原先在a或b的顺序。”

考虑到是无序数组，目前，还没想到把时间复杂度做到O(n)；方法2-1和2-2都是O(n*logn)的时间复杂度。

方法一、此问题最简单的方法是：蛮力法，定为顺序标杆的那个数组的元素在外围，二重循环，得到新的数组c；

 //代码示例，假定a是标杆数组
type[] intersection(type[] a, type[] b, type[] c) {
int k = 0;
for (int i=0; i<len_a; ++i)
for (int j=0; i<len_b; ++j)
if (a[i] == b[j])
c[k++] = a[i];
return c;
}

此方法时间复杂度O（len_a * len_b），如果它们的数量级都是n，则为O(n^2).

方法二、增加辅助空间，降低时间复杂度，特别是数据量大的时候。
根据标杆数组和len_a和len_b的大小关系可以进一步分为 方法2-1和方法2-2；

方法2-1，此方法适用于标杆数组和长度较大的数组不是同一个数组的情况；

 // 示例代码，依然假定a是标杆数组
type[] intersection(type[] a, type[] b, type[] c) {
set<type> set_b = set<type>(b.begin(), b.end());

int k = 0;
for (int i=0; i<len_a; ++i)
if (set_b.find(a[i]))
c[k++] = a[i];
return c;
}

此方法时间复杂度O(len_a * log(len_b))，如果它们的数量级都是n，则为O(n*logn).
此方法空间复杂度O(len_b)，如果它们的数量级都是n，则为O(n).

方法2-2，此方法适用于标杆数组和长度较大的数组是同一个数组的情况；

 // 示例代码，a既是标杆数组，又是数量较大的数组
type[] intersection(type[] a, type[] b, type[] c) {
map<type> map_a = map<type>(a.begin(), a.end());
set<type> set_c = set<type>();

for (int j=0; j<len_b; ++j)
if (map_a.find(b[j]))
set_c.add(map_a[b[j]]);

j = 0;
set::iterator pos;
for (pos=set_c.begin(); pos!=set_c.end(); ++pos)
c[j] = *pos;
return c;
}

此方法时间复杂度O(len_b * log(len_a))，如果它们的数量级都是n，则为O(n*logn).
此方法空间复杂度O(len_a)，如果它们的数量级都是n，则为O(n).

Answer 2

具体实现 如@谢昌磊 所说, 对第一个数组做一个 map表 {字符 ->　下标},　要比较第二个数组　两个元素的大小,　去查表　比较下标即可.

其实具体排序部分可以直接用库函数.　这里有一个pattern.
如c中的qsort(): http://www.cplusplus.com/reference/cstdlib/qsort/

void qsort (void* base, size_t num, size_t size,
int (*compar)(const void*,const void*));

或者java的Arrays.sort(),

public static <T> void sort(T[] a, Comparator<? super T> c)

都只需给出 需排序的数组, 和 比较 数组元素大小的 回调函数即可.

compar(a, b) 和 Comparator.compare(a, b) 的 原理都是约定俗成的.
返回负数 表示 a排在b前, 0 表示相等, 正数 表示 a排在b后.

这里也是体现了程序设计的原则. 分离 不变的 和 变化的逻辑. 排序算法是固定的, 由库函数处理, 需排序的数组由用户提供, 数组元素的排序原则也由用户提供.

Answer 3

排序算法不说了，冒泡，选择，快速排序很多很多，你这重点是比较大小，给你一个idea就是取前一个数组中该字母的下标进行比较

Answer 4

char order[5] = { 'q', 'w', 'e', 'a', 's' };
char target[3] = { 's', 'a', 'q' };
char temp;
int i, j;
int index = 0;

for (i = 0; i < 5; i++)
{
for (j=index; j < 3; j++)
{
if (order[i] == target[j])
{
temp = target[index];
target[index] = target[j];
target[j] = temp;
index++;
}
}
}
for (i = 0; i < 3; i++)
printf("%c ", target[i]);

简单实现了一个，效率不高。等高手回答

补：另一个很是不同的思路。如果规模不大的话可以试试。
把a中的不属于b的字符去掉，剩下的就是排好序的