首页 > 试题广场 >

0交换排序

[编程题]0交换排序
  • 热度指数：5791 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换，完成以下函数
算法知识视频讲解
添加回答
推荐
二货磁铁头像 二货磁铁 
for (int i = len-1; i>=0; i--){
 if (array[i] == i){
 //i--;
 continue;
 }
 int k = array[i];
 while (array[k] != k&&array[k] != i)
 {
 k = array[k];
 }
 
 swap_with_zero(array, len, i);
 swap_with_zero(array, len, k);
 }
验证通过

编辑于 2015-06-19 17:51:08 回复(6)
flyingsheep头像 flyingsheep
算法图解：

for(int i = 1;i<len;i++)
        {
            if(array[i]==i)
                continue;
            else
            {
                swap_with_zero(array,len,array[i]);
                swap_with_zero(array,len,i);
            }
        }

发表于 2018-07-23 22:15:00 回复(0)
牛客8331271号头像 牛客8331271号
为什么不能直接赋值， 

     for(int i = 0; i < len; i++){
        array[i]=i;
    }

发表于 2017-03-31 16:45:15 回复(8)
Java
牛客4357287号头像 牛客4357287号
没看懂题目，随便测试竟然试对了。有些网上的测试题目及编译器让人醉了，仅供参考。
public class Solution {
/**
* 交换数组里n和0的位置
*
* @param array
*            数组
* @param len
*            数组长度
* @param n
*            和0交换的数
*/
// 不要修改以下函数内容
public void swapWithZero(int[] array, int len, int n) {
Main.SwapWithZero(array, len, n);
}
// 不要修改以上函数内容


/**
* 通过调用swapWithZero方法来排
*
* @param array
*            存储有[0,n)的数组
* @param len
*            数组长度
*/
public void sort(int[] array, int len) {
// 完成这个函数
for(int i=0;i<len;i++){
swapWithZero(array, len, array[i]);
swapWithZero(array, len, i);
}
}
}
编辑于 2017-02-26 18:35:25 回复(1)
海小星头像 海小星 
/*
因为数组为[0, n-1]，是连续的，只是乱序的。
从始至终只能交换0和其中某个数。
最终排好的数组，下标和该位置上的数相同，即array[i] == i。
--------------------------------
所以，代码思路：
1、要使数组array[i]为i,又因只能与0交换，所以要先让0在这个位置上，即swapWithZero(array, len, array[i]);
2、然后将i与0交换：swapWithZero(array, len, i); 即可使数组array[i]==i
*/
 public void sort(int[] array, int len) {
        // 完成这个函数
        for(int i=0;i<len;i++){
            //可加个判断：array[i] == i则跳下一个数， 可减少执行次数
            swapWithZero(array, len, array[i]);//将0换到i的位置
            swapWithZero(array, len, i);//将i与0交换，i放到array[i]的位置
        }
    }

发表于 2019-09-12 21:39:46 回复(0)
JackBurd头像 JackBurd
很笨的方法。 
public void sort(int[] array, int len) {
        int min, index;
        
        for(int n = 1; n < len; n ++){
            swapWithZero(array, len, array[n]);
            
            min = array[0];
            index = 0;
            
            for(int j = n+1; j < len; j ++){
                if(array[j] < min){
                    min = array[j];
                    index = j;
                }
            }
            
            swapWithZero(array, len, array[index]);
        }
    }

编辑于 2015-05-01 21:28:45 回复(0)
Java
工大月头像 工大月 
 /*
 * 
测试用例:[3,8,2,4,5,0,1,7,9,6]
对应输出应该为:[0,1,2,3,4,5,6,7,8,9]
 * */
public class Solution {

    /**
     * 交换数组里n和0的位置
     * 
     * @param array
     *            数组
     * @param len
     *            数组长度
     * @param n
     *            和0交换的数
     */
    // 不要修改以下函数内容
    public void swapWithZero(int[] array, int len, int n) {
        
        Main.SwapWithZero(array, len, n);//备注：这个SwapWithZero()方法是牛客网已经实现好的，作用：交换数组里n和0的位置
    }
    // 不要修改以上函数内容


    /**
     * 通过调用swapWithZero方法来排
     * 
     * @param array
     *            存储有[0,n)的数组
     * @param len
     *            数组长度
     */
    public void sort(int[] array, int len) {
        // 完成这个函数
        for(int i = 0; i < len; i++){
            if(array[i] == i){
                continue;
            }
            swapWithZero(array, len, array[i]);//因只能与0交换，所以要先让0在array[i]这个位置上
            swapWithZero(array, len, i);//然后将i与0交换，即可使数组array[i]==i
        }
    }
    
}

编辑于 2020-07-23 23:46:47 回复(1)
YBee丶头像 YBee丶 


extern void swap_with_zero(int* array, int len, int n);
class Solution {
public:
void sort(int* array, int len) {
     for(int i=len-1;i>0;i--)
     {
         if (array[i]==i)
             continue;
         swap_with_zero(array,len,array[i]);
         swap_with_zero(array,len,i);//array[i]==i,game over!
     }
}
};


编辑于 2018-03-21 18:28:02 回复(0)
itlegend2头像 itlegend2 
    public void sort(int[] array, int len) {
        // 完成这个函数
         if(len <= 1){  
             return;  
         }  
         for(int i = len - 1; i > 0; --i){       //从最后一位开始，将最大的数放到最大位置上，然后依次找次大的放  
             if(array[i] == i) continue;        //已经相等，则不交换,避免不必要的重复交换  
             swapWithZero(array,len, array[i]);  //现将0和最后一位交换，以便将第n最大值换到第n大位置上    
             int curMax = array[i];  
             for(int j = i; j >= 0; --j){       //找出第n大的数  
                  if(array[j] > curMax){  
                      curMax = array[j];  
                  }  
             }
             swapWithZero(array,len, curMax); 
    }
    }

发表于 2018-03-21 09:57:52 回复(0)
九城城主头像 九城城主
思路：循环交换--对数字i来说，先将0与i位置的数字交换，即swap_with_zero(array, len, array[i]);
此时0在i位置，然后交换0与i即可。代码如下： 
/**
 * 交换数组里n和0的位置
 * array: 存储[0-n)的数组
 * len: 数组长度
 * n: 数组里要和0交换的数
 */
extern void swap_with_zero(int* array, int len, int n);

class Solution {
public:
    /**
     * 调用方法swap_with_zero来对array进行排序
     */
    void sort(int* array, int len) {
        for(int i = len - 1; i > 0; i --)
            {
            if(array[i] == i)                        //判断是否在正确位置
                continue;
            swap_with_zero(array, len, array[i]);    //交换0与i位置的数字  
            swap_with_zero(array, len, i);           //交换0与i
        }
    }
};

编辑于 2016-01-06 09:29:42 回复(2)
smileZh头像 smileZh
发表于 2015-09-08 11:32:39 回复(0)
牛客627487021号头像 牛客627487021号 
/**
 * 交换数组里n和0的位置
 * array: 存储[0-n)的数组
 * len: 数组长度
 * n: 数组里要和0交换的数
 */
extern void swap_with_zero(int* array, int len, int n);

class Solution {
public:
    /**
     * 调用方法swap_with_zero来对array进行排序
     */
    void sort(int* array, int len) {
        // 使得0位置为0
        swap_with_zero(array, len, 0);

        for (int i = 1; i < len; ++i) {
            if (array[i] == i) {
                continue;
            }
            // 将正确的值先保存到0位置
            swap_with_zero(array, len, i);
            // 将乱序位置的值和0随机交换，以免被覆盖
            swap_with_zero(array, len, array[i]);
            // 将保存在0位置的正确值交换到合适的位置
            swap_with_zero(array, len, array[0]);
        }
    }
};
发表于 2021-02-08 09:52:49 回复(0)
牛客983924334号头像 牛客983924334号
for (int i = len-1; i>=0; i--){ if (array[i] == i){ //i--; continue; } int k = array[i]; while (array[k] != k&&array[k] != i) { k = array[k]; } swap_with_zero(array, len, i); swap_with_zero(array, len, k); }
发表于 2020-08-13 14:49:25 回复(0)
Java
嘘～头像 嘘～ 

 public void sort(int[] array, int len) {
        int[] a = new int[len];
        for(int i= 0; i< len; i++){
            a[i] = i;
        }
        array = a;
    }
java 引用替换为什么是错的
发表于 2020-01-21 15:35:17 回复(0)
Java
俊子头像 俊子
public class Solution {
    /**
     * 交换数组里n和0的位置
     * 
     * @param array
     *            数组
     * @param len
     *            数组长度
     * @param n
     *            和0交换的数
     */
    // 不要修改以下函数内容
    public void swapWithZero(int[] array, int len, int n) {
        Main.SwapWithZero(array, len, n);
    }
    // 不要修改以上函数内容


    /**
     * 通过调用swapWithZero方法来排
     * 
     * @param array
     *            存储有[0,n)的数组
     * @param len
     *            数组长度
     */
    public void sort(int[] array, int len) {
        // 完成这个函数
        for(int i = len - 1; i>= 0;i--){
            int a = array[i];
            swapWithZero(array, len, a);
            swapWithZero(array, len, i);
        }
    }
}
发表于 2019-12-05 01:06:26 回复(0)
dwtfukgv头像 dwtfukgv 
/**
 * 交换数组里n和0的位置
 * array: 存储[0-n)的数组
 * len: 数组长度
 * n: 数组里要和0交换的数
 */
extern void swap_with_zero(int* array, int len, int n);
 
class Solution {
public:
    /**
     * 调用方法swap_with_zero来对array进行排序
     */
    void sort(int* array, int len) {
        int *a = array;
        int i = 1;
        while(i < len){
          if(a[i] == i){ ++i;  continue; }
          if(a[i] != 0)
            swap_with_zero(a, len, a[i]);
          swap_with_zero(a, len, i);
          ++i;
        }
    }
};

发表于 2019-08-11 19:34:13 回复(0)
YaphetSPis头像 YaphetSPis 
/**
 * 交换数组里n和0的位置
 * array: 存储[0-n)的数组
 * len: 数组长度
 * n: 数组里要和0交换的数
 */
extern void swap_with_zero(int* array, int len, int n);

class Solution {
public:
    /**
     * 调用方法swap_with_zero来对array进行排序
     */
    void sort(int* array, int len) {
        int tmp = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (array[i] == i) continue;
            if (0 != array[i])
                swap_with_zero(array, i + 1, array[i]);
            swap_with_zero(array, i + 1, i);
        }
    }
};

发表于 2019-05-09 00:37:00 回复(0)
snailClimbZG头像 snailClimbZG
这个题是什么意思，交换函数交换的到底是两个位置上的值还是什么，没明白题意啊。。。
发表于 2019-04-24 11:04:02 回复(0)
Java
llab头像 llab 
  本地运行出来没问题，提交就报错，哪位大神能帮忙解答下？？？？
发表于 2019-04-09 20:40:40 回复(0)
C/C++
花花是我女鹅头像 花花是我女鹅 
    void sort(int* array, int len) {
        swap_with_zero(array,len,array[0]);
        for(int i=1;i<len;i++)
        {   
             swap_with_zero(array,len,array[i]);
             swap_with_zero(array,len,i);
             swap_with_zero(array,len,array[0]);
        }   
    };  
发表于 2019-02-28 21:48:48 回复(0)
C/C++
时间童话头像 时间童话
假设当前序列为0，1，2，3，5，4
由于0，1，2，3都排好了序，为了把4排到正确的位置，可以把5先排到正确的位置
即：
1、5和0交换 5，1，2，3，0，4
2、4和0交换 5，1，2，3，4，0
3、5和0交换 0，1，2，3，4，5
第一次循环后5排到了正确的位置
如果4还没有排到正确的位置，重复上面的步骤

void sort(int* array, int len) {
    for(int i=0;i<len;++i)
    {
        while(array[i]!=i)
        {
            if(array[array[i]]==0)
            swap_with_zero(array,len,array[i]);
            else
            {
                int x=array[i];
                swap_with_zero(array,len,array[i]);
                swap_with_zero(array,len,array[x]);
                swap_with_zero(array,len,x); 
            }
        }
    }    
}

编辑于 2019-01-05 17:21:18 回复(0)
提交观点

问题信息

谷歌 复杂度 C++ Java 排序
来自：程序员智力算法笔试卷
难度：
47条回答 43385浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号