当前位置：首页 → 问答吧 → 一道面试题，关于数组排序

一道面试题，关于数组排序

时间：2011-12-12

来源：互联网

题目：

现有两个int型数组a[N]，b[N]。
a[N]无序，现在依次找出a[N]中最大的数，并把其在a[N]中的下标保存到b[N]中。
例如：b[0] = 30，表示a[30]的数据最大，b[1] = 10表示a[10]的数据仅小于a[30]。

要求：最多只用一个中间变量，根据b[N]将a[N]从大到小排列，注意不能再进行任何排序相关的动作。

作者: danxuezx 发布时间: 2011-12-12

插入排序，但在b中保存a的序号

作者: ouyh12345 发布时间: 2011-12-12

引用 1 楼 ouyh12345 的回复:
插入排序，但在b中保存a的序号

没明白。
其实a[N]从大到小的顺序已经在b[N]中了，现在就是要交换一下a[N]中的数据。
但怎么才能只通过一个temp量来达到目的呢？出题者应该不希望再看到比较之类的东西。

作者: danxuezx 发布时间: 2011-12-12

有几点不明，(1)数组b【N】初始化就存储的是乱序状态下数组a【N】的下标么？

作者: zhaoquanbin007 发布时间: 2011-12-12

注意不能再进行任何排序相关的动作?

作者: xing376688 发布时间: 2011-12-12

public class Test {
public static void main(String[] argString) {
int[] a = { 5, 3, 4, 9, 2, 1 };
int[] b = { 3, 0, 2, 1, 4, 5 };

int[] c = new int[a.length];
for (int i = 0; i < a.length; i++) {
c[i] = a[b[i]];
}
for(int d:c){
System.out.println("d="+d);
}
}
}

作者: xing376688 发布时间: 2011-12-12

d=9
d=5
d=4
d=3
d=2
d=1

作者: xing376688 发布时间: 2011-12-12

可以比较的话，冒泡是不错的选择，只需要一个临时空间，每次将数组a中最大的数放入b
关注~

作者: yfkiss 发布时间: 2011-12-12

引用 3 楼 zhaoquanbin007 的回复:
有几点不明，(1)数组b【N】初始化就存储的是乱序状态下数组a【N】的下标么？

b[N]初始化值是怎样没关系，关键是最后它里面保存的是a[N]中从大到小的数据在a[N]中的下标。

作者: danxuezx 发布时间: 2011-12-12

引用 5 楼 xing376688 的回复:
public class Test {
public static void main(String[] argString) {
int[] a = { 5, 3, 4, 9, 2, 1 };
int[] b = { 3, 0, 2, 1, 4, 5 };

int[] c = new int[a.length];
for (int i = 0; i < a.length; i++)……

明显不行，您这里用到了另外一个数组，这样的话很多人都会，就选不到“高”人啦~~

作者: danxuezx 发布时间: 2011-12-12

可以先看看静态链表的排序。
可以把数组b作为a的指针号。

作者: woweiwokuang0000 发布时间: 2011-12-12

引用 7 楼 yfkiss 的回复:
可以比较的话，冒泡是不错的选择，只需要一个临时空间，每次将数组a中最大的数放入b
关注~

出题的人应该是想看到紧紧是通过简单的交换来完成。因为a[N]中从大到小的顺序已经知道了，现在就是调整一下。

作者: danxuezx 发布时间: 2011-12-12

第一步就不说了，在b[N]已经记录好了a[N]的顺序之后。
C/C++ code


int temp; //只用一个中间变量
for(i=0; i < N; i++)
{
    temp = a[b[i]];
    a[b[i]] = a[i];
    a[i] = temp;
}

作者: wshjldaxiong 发布时间: 2011-12-12

复杂度要求呢？不要求复杂度有什么意思》

作者: mingliang1212 发布时间: 2011-12-12

引用楼主 danxuezx 的回复:
题目：

现有两个int型数组a[N]，b[N]。
a[N]无序，现在依次找出a[N]中最大的数，并把其在a[N]中的下标保存到b[N]中。
例如：b[0] = 30，表示a[30]的数据最大，b[1] = 10表示a[10]的数据仅小于a[30]。

要求：最多只用一个中间变量，根据b[N]将a[N]从大到小排列，注意不能再进行任何排序相关的动作。

要求：最多只用一个中间变量，根据b[N]将a[N]从大到小排列，注意不能再进行任何排序相关的动作。
这个出题人说的不太明白，到底什么才是进行排序中相关的动作呢？
我的理解是比较应该算吧，那赋值应该不算吧.
如果赋值不算的话可以这样：还是比较简单的，因为目前b[N]已经排序了，而已b[N]中记录的a[N]中的数值大小的索引。
首先把a[0]保存到临时变量temp中，然后把a[b[0]]直接赋值到a[0],接着把temp塞到a[b[0]],接了到a[1],同样把a[1]保存到临时变量temp中，然后把a[b[1]]直接赋值到a[1],接着把temp保存到a[b[1]]中,如此反复下去就可以对a[N]进行排序.

但是这里有一个问题，因为要变量a[0]，a[1]....这里势必要借用一个变量，这个变量算不算呀？

如果赋值也算是限制的条件的话，那没有办法能解决.
这个出题人没有把题目出的更清楚一点，考虑不全.

作者: yuucyf 发布时间: 2011-12-12

同意#12楼wshjldaxiong，将其代码做一点小小改进
C/C++ code


int temp; //只用一个中间变量
for(i=0; i < N-1; i++)
{
    if(i != b[i])
    {
        temp = a[i];
        a[i] = a[b[i]];
        a[b[i]] = temp;
    }
}

另，出题者的意思是不是要根据a数组而仅凭额外的一个变量就做出b数组出来？似乎这个还有点难度。

作者: lwouyang 发布时间: 2011-12-12

一道面试题，关于数组排序

热门阅读

热门下载