首页 > 代码库 > 一道关于排序的面试题
一道关于排序的面试题
以前群里有个同事发了道面试题：
两个已排好序数组，A和B,现要求对他们重新联合排序，合以的小数放入A数组中，大的数放入B中。
这题的关键是两个数组已经排好序，如果按传统的方法，进行排序当然没问题，但就没有充分利用现有的条件。
或许你可以想到插入排序，这样就可以利用a数组已排好序的优势对其进行排序了。但传统的插入排序确没有考虑到B数组也已排好序，我试过用插入序序的方式解决这个问题，但在连写了两个if,else之后，我放弃了。（我最讨厌写if,else,而且我也意识到插入排序不能很好地利用现有条件）。除了插入排序之外，我脑海中已出了几种算了，但所想到的所有算法中都要涉及数组移位问题（而且还要写if,else）。有没有人种算法，只要交换两个数组中数据就可以了呢？
如果将a中的所有元素与b中的无素进行比较，且如果a[i]>b[i]，就将a[i]与b[i]互换位置，这样a[0],中的元素将是两个数组中最小的元素，而b[b.length-1]将是两个集合中最大的元素。接着我们们从两个数组中去除掉a[0]与b[b.length-1]，再重复上面的操作。(这里是假设两个数组的长度是一样的)
@Override
public void sort(Integer[] arrayA, Integer[] arrayB) {
int tmp;
for(int j =0; j<arrayA.length;j++){
for(int i=0;i<arrayA.length-j;i++){
if(arrayB[i]<arrayA[i+j]){
tmp = arrayA[i+j];
arrayA[i+j] = arrayB[i];
arrayB[i] = tmp;
}
}
}
}
这是我所有想到解决这个问题算法中，代码量最少的一种方法了。但比较次数，以及数据交换次数不见得最少。
如果数组长度为n,那个整个比较及数据交换次数为（n+1）n/2，
下面一种方案，是利用插入排序的思想，对数组进行排序：
这种排序的思想直接来源插入排序,步骤是将a数组中的最后一个元素（也就是最大的元素）取出,插入到B数组中,并将B数组的元素向后移,将B数组的第一个元素取出,插入到A数组合适的位置,并将数组的元素前移。
当你真正去写一段代码时，才发现没那么复杂，没必要写那么多令人头皮发麻的if-else,
public class InsertArraySort implements TwoArraySortStrategy { @Override public void sort(Integer[] arrayA, Integer[] arrayB) { int cur ; while (arrayB[0] < (cur = arrayA[arrayA.length-1])){ insert2A(arrayA,arrayB[0]); insert2B(arrayB, cur); } } private void insert2B(Integer[] arrayB, int cur) { int i; for(i=1; i<arrayB.length && arrayB[i] <= cur ; i++){ arrayB[i-1] = arrayB[i]; } arrayB[i-1] = cur; } private void insert2A(Integer[] array,Integer number){ int i; for(i=array.length-2; i >= 0 && array[i] >= number ; i--){ array[i+1] = array[i]; } array[i+1] = number; } }
我写的第一种排序算法，应该有点类似于冒泡排序。显然利用插入排序的思想在很多场合效率更高，而且后一一种可改善的地方有很多，比如可以利用二分查找法，来快速定位要插入数据的位置。然后进行移位插作。
（待继）
很早就有了要写些东西的打算，但脑袋里面稀奇古怪的思想太多，不知道从什么地方落笔好，而且我容易走神。很难在写东西时集中注意力。
一道关于排序的面试题