经理说.net的人80%不会写算法

长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的swap，请设计并实
现排序（ 必须采用交换实现）。

不才，我就是属于那80%的人。

43 个解决方案

#1

基本上是吧，都是拿来用的成品。

#2

本帖最后由 bdmh 于 2013-04-03 16:30:08 编辑

先把0放到第一个，这样0就是最小的了，然后随便用一个交换排序原理的排序，从第一个元素向后比较，记录交换前元素，需要小修改一下

其实首先得找到0的位置，然后剩下的，如果你能理解一种交换排序的原理，就差不多可以做了，还可以向quicksort一样，从0的位置向两边找

#3

倒过来想.NET的长处就是,他们写一大堆代码实现的功能就是你拖了一下控件

#4

#5

你和经理说，你写算法吧，我Array.Sort一下就好了

#6

引用 5 楼 linrachel 的回复:

你和经理说，你写算法吧，我Array.Sort一下就好了

+10086

#7

站在巨人的肩膀上思考问题，嗯

#8

这个说的有些泛
例如你说的问题，首先要弄清问题，理清思路就好
不知自己是否理解对了。。。。
长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的swap

直接的想法：
1.先找到0的位置loc0
2.1 找1的位置loc1与loc0进行交换数据
2.2 数组的第一个位置的数据data1,与loc1(这时里面数据为0)交换
2.3 交换第一个位置与loc0(里面数据为0)，此时0回到loc0,完成loc1与数组第一个位置的数据交换
3. 循环处理直到n - 1

#9

广义的"算法",和狭义的"算法"。

不是会写个排序就是算法。
写程序，就是设计最优算法的过程。

#10

比如：要开车，你是从用零件组装开始，还是直接去买一辆？

#11

引用 5 楼 linrachel 的回复:

你和经理说，你写算法吧，我Array.Sort一下就好了

这回答，太牛了。
现在都什么年代了，还去纠结这些低级算法，这应该是刚学算法的时候要搞的。
（1）如果你做应用，运行效率已经不是主要问题了，现在关注的是开发效率。
（2）如果你做研究，还纠结于图像输入输出之类的问题吗？反正我做图像处理就用C#，也亏了微软给力，弄个Kinect SDK就是C#的。

#12

怎么说呢。。有时候 你需要哪种算法和数据结构的思维。。。

#13

就会一个Orderby asc desc=>哎。

#14

自己想吧，这到底是“九连环” 还是“汉诺塔”

ps：无论是九连环还是汉诺塔，这种东西你要用在常规排序里，那只能说坑滴就是你

#15

老板要的东西，是不是必须有算法才能交差呢？
不用算法，但是能达到老板的要求，老板和客户对这个会不满意吗？
现在编程已经不是电脑刚出现的时候的情况了，那个时候编程序的人是个科学家，至少是个科学研究者
但是现在不行，程序员就是一码农（网上很流行，代码猴，程序猿，呵呵）
我们只要知道怎么用，怎么能达到目的，就可以了
至于算法，那是逻辑思维强弱的问题
。。。

#16

yamade亚麻的

#17

.net只是封装了基础的，经常用的算法，没必要每写一个程序都去自己实现一遍这些基础算法，这纯属浪费时间

#18

一般工资都体现在算法上。

#19

大部分系统都是整天CRUD，哪里需要啥算法？又不是工程计算类的项目开发。

#20

这种题目毫无意义。就好比数学家未必非要会速算，买菜的时候不允许使用计算器一样。

#21

我不想说你出的题目不是算法。但是这是初级码农研究的算法，就好比小学奥数题，广义上来说也属于数学，但是和高等数学以及学术界的数学学科研究的东西毫无关系。这种使用几个变量，不使用什么操作的“算法”，充其量只是给新手练习的思维体操而已。

#22

该回复于2013-04-04 09:08:38被管理员删除

#23

把这个数组重新赋值一遍不就得了？

这个，还需要排序？数据和数组下标基本都一一对应的，有病啊设计个这玩意，难道是面试题？

#24

现在的硬件价值比算法价值要低很多

如果不是特别需要   那么我感觉还是  把弄算法的时间弄成钱  换几个硬件   还比较好

#25

你们经理这题目有问题吧,数组内的数是0- n-1,那就是连续的自然数了,还排个毛啊,直接输出1,2,3,4...n-1就行了

#26

一般大学学算法的目的是锻炼思维。现在开发用的工具已经是高级化和高效化的，底层的东西可以基本跳过，除非是搞底层的架构（操作系统或者接近的层次等等）。应用级的东西，不用错，做的东西满足要求就可以了。

#27

现在市场上所谓的面向算法开发的人员一般是改方法，哪有专门的研究新的高效的通用的算法？专攻那方面的人是小范围人群，当然搞出来新的东西是可以成为专利或是一种新的技术或新的发现。

#28

这个 时间复杂度是多少？n！？？

再说了 现在 多少项目能用的哦啊 算法呢.....

#29

应该还有更简单的吧。。

List<int> list = new List<int> { 1, 5, 4, 2, 3, 0 ,6};
for (int i = 0; i < list.Count; i++)
{
    int temp;
    temp = list[i];
    list[i] = list[temp];
    list[temp] = temp;
}
list.ForEach(x => { Console.Write(x.ToString() + " "); });

#30

引用 3 楼 qq520360 的回复:

倒过来想.NET的长处就是,他们写一大堆代码实现的功能就是你拖了一下控件

说的太夸张了吧。
mfc中写控件不就一个Create搞定吗
c#里面也是要new之后再设置属性么

#31

引用 楼主 wolf_410 的回复:

长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的swap，请设计并实
现排序（ 必须采用交换实现）。

不才，我就是属于那80%的人。

如果你找0~n-1位置上最大的一个数，（如果它不在0位置上就）把它与0进行swap，然后再把第n-1个与0进行swap，此时最大的数就已经放到n-1了。同理，可以再放置n-1，n-2，.....1。

#32

其实任何比较流行的编程语言的使用者，就会鱼龙混杂。但是问题在于人，而不在于这个工具。

引用 29 楼 linrachel 的回复:

应该还有更简单的吧。。
C# code?123456789List<int> list = new List<int> { 1, 5, 4, 2, 3, 0 ,6};for (int i = 0; i < list.Count; i++){    int temp;    temp = list[i];    list[i] = list[temp];    list[……

不是这样的。题目出的很明白，只能与0位置上的数交换，不是交换i与temp位置上的数。

如果题目都审不清楚，那么我们就不必讨厌lz的经理看不起.net程序员了。

#33

引用 9 楼 promaster 的回复:

广义的"算法",和狭义的"算法"。

不是会写个排序就是算法。
写程序，就是设计最优算法的过程。

除了最后一句，前边的我都同意。

但是最后一句就太偏颇了。算法是一个程序员的基本素质，并不是说会现学现卖一点皮毛就不必了解算法了，但是也不能反过来说什么都是算法。着就好像一个大厨要回基本功，算法在一个软件专业的教育中大概占了5%的教育时间，虽然它确实是一颗明珠，但是它不是一切。实际上如果你学过大学语文，那么你在逻辑、写作等方面也可以很好，我可以说那些连语言都说不明白、题目经常审错的人，对算法的理解往往是夸大和（其实）不扎实的。

#34

嗯，如果lz的问题不是指位置0，而是指每一次都要搜索0所在的新位置，那么这个程序则稍微复杂一点。说起来比较麻烦，直接写出来程序再说明：

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> list = new List<int> { 1, 5, 4, 2, 3, 0, 6 };
            for (int i = 1; i < list.Count; i++)
            {
                if (list[i] != i)
                    swap(list, i);
            }
            list.ForEach(x => { Console.Write("{0} ", x); });
            Console.WriteLine("................Press any key");
            Console.ReadKey();
        }

        private static void swap(List<int> list, int index)
        {
            var 数0的位置 = (from i in Enumerable.Range(0, list.Count)
                         where list[i] == 0
                         select i).First();
            var 数index的位置 = (from i in Enumerable.Range(0, list.Count)
                             where list[i] == index
                             select i).First();
            swap2(list, 数0的位置, index);  //此时数0交换到index位置
            swap2(list, index, 数index的位置);
        }

        private static void swap2(List<int> list, int i, int j)
        {
            if (i != j)
            {
                var tmp = list[i];
                list[i] = list[j];
                list[j] = tmp;
            }
        }
    }
}

如果每一次都需要搜索数0所在的新位置（而不是位置0）才能交换，那么就需要先搜索。从方法swap中可以看到两次调用swap2时其中一个位置中都必定有数0存在。

#35

这个问题你可以搜索下快速排序

#36

我感觉这个说法存在欺骗性啊,只能进行0与其他数的交换....如果是要实现排序,那0的位置只能在第一个...也就是说其实是对0所在的位置交换,而不应该是0本身,比如0在第6位,那么就要去把6找出来,然后6所在的位置如果是第10位,那就要去把10找出来,特码的跟0没屁点关系,你也可以说成是只能用5跟其他交换...

#37

不过确实,想想人类会不会有一天突然丢失了文明...也就是基础的算法啥的都没人知道了,只剩下一些封装好的东西....这是不是叫做史前文明了.....可以写本小说了

#38

就国内这样的环境，就没见过有什么牛B的软件，能用上什么深奥的算法？通常对于算要求较高的几乎都是图形处理运算。 数据库之类管理系统的开发就更不用说了。

#39

引用 33 楼 sp1234 的回复:

引用 9 楼 promaster 的回复:
广义的"算法",和狭义的"算法"。

不是会写个排序就是算法。
写程序，就是设计最优算法的过程。
除了最后一句，前边的我都同意。

但是最后一句就太偏颇了。算法是一个程序员的基本素质，并不是说会现学现卖一点皮毛就不必了解算法了，但是也不能反过来说什么都是算法。着就好像一个大厨要回基本功，算法在一个软件专业的教育中大概占了5%的教育时间，虽然……

见笑了。。确实没怎么看清楚题目。又重新用递归弄了下，这次能满足题目要求了。
每次将0的位置移到没有排序的元素最后，然后与前面最大的数值swap。。

static void SwapZero(List<int> list,int count) {
    // 0与数组末尾项交换            
    for (int i = 0; i < count; i++)
    {
        if (list[i] == 0)
        {
            list[i] = list[count - 1];                            
            list[count - 1] = 0;
            break;
        }
    }

    // 将最大值与0交换
    for (int i = 0; i < count; i++)
    {
        if (list[i] == count - 1) {
            list[count - 1] = list[i];
            list[i] = 0;
            break;
        }
    }
    if (count > 1)
    {
        SwapZero(list, count - 1);
    }
            
}

static void Main()
{

    List<int> list = new List<int> { 1, 5, 4, 2, 3, 0};

    SwapZero(list,list.Count);
    list.ForEach(x => { Console.Write(x.ToString() + " "); });           
    Console.Read();
}

#40

其实这题说难不难，说简单也不那么简单。这个算法的效率可以做到O(n)，涉及群论中的置换群的概念。简单理解就是，所有的乱序排列通过交换变为正序，都存在一些环。

以3 1 4 2为例，这个环的长度为4，
1 -> 3
3 -> 4
4 -> 2
 
所有元素都在1个环内，总共需要交换3次。 
2 1 4 3则存在两个环,1 2是一个，3 4是一个。总共需要交换2次。

每一个环内需要进行k - 1次交换，使得k个元素完成排序。k是环的长度，也是环内的元素数量。因此总的交换次数就是N - M。其中N是不在正确位置的元素数量。M是环的数量。

但本题要求只能同0进行交换，可以知道0只能存在于1个环，而剩下的环则需要先同0进行交换，然后再进行k - 1次交换，最后再将0换回去，多了2次操作。因此总的交换次数变为了N + M。可以知道M是小于N的，因此复杂度是O(n)的。

#41

机智的作业狗

#42

算法。。。。。。

#43

引用 35 楼 f345036107 的回复:

这个问题你可以搜索下快速排序

快速排序不行吧，人家不是说了只能0和其他的元素交换么