求教一下,关于分类的排序算法

wdwwtzy 2010-03-10 06:54:15
我想弄一个无级分类,可是输出时要排序的嘛,有一个字段来表示如何排序.不过这个排序的算法我写的总是效率很差,所以请教一下大大,有没有好的方法.我自己写的很烂的方法就不发出来了,误导大大.

下面这个是测试用的数据
最终正确输出的排序是//2 3 5 8 4 9 1 7 6 10
多谢了


public static class TestData

{

	public static List<TestInfo> List = new List<TestInfo>()

	{

		new TestInfo() { Id = 1, ParentId = null, OrderId = 2 },

		new TestInfo() { Id = 2, ParentId = null, OrderId = 1 },

		new TestInfo() { Id = 3, ParentId = 2, OrderId = 1 },

		new TestInfo() { Id = 4, ParentId = 2, OrderId = 3 },

		new TestInfo() { Id = 5, ParentId = 2, OrderId = 2 },

		new TestInfo() { Id = 6, ParentId = 1, OrderId = 2 },

		new TestInfo() { Id = 7, ParentId = 1, OrderId = 1 },

		new TestInfo() { Id = 8, ParentId = 5, OrderId = 1 },

		new TestInfo() { Id = 9, ParentId = 2, OrderId = 4 },

		new TestInfo() { Id = 10, ParentId = null, OrderId = 3 }

	};

}



public class TestInfo

{

	public int Id { get; set; }

	public int? ParentId { get; set; }

	public int OrderId { get; set; }

}
...全文
220 18 打赏 收藏 转发到动态 举报
写回复
用AI写文章
18 条回复
切换为时间正序
请发表友善的回复…
发表回复
wdwwtzy 2010-03-26
  • 打赏
  • 举报
 回复
实在抱歉,结贴有点晚
两位大大写的非常棒啊,尤其后面lambda写的这个,好棒
哎,我是太笨了,根本一个都写不出来啊...
万分感谢

顺便测试了一下效率,似乎lambda这个版本要高一点
各10000次
aimeast 295ms
litaoye 705ms
aimeast 2010-03-12
  • 打赏
  • 举报
 回复
[Quote=引用 13 楼 wdwwtzy 的回复:]

引用 9 楼 aimeast 的回复:
引用 8 楼 wdwwtzy 的回复:呃 是我说的不清楚吗?我解释一下最终正确输出的排序是//2 3 5 8 4 9 1 7 6 10 2 --根节点 order为1 3 --父节点为2 order为1 5 --父节点为2 order为2 8 --父节点为5 order为1 4 --父节点为2 order为3 9 --父节点为2 ……
[/Quote]
i see 有空帮你写一个
aimeast 2010-03-12
  • 打赏
  • 举报
 回复
给lz一个完全用lambda写的排序方法。虽然效率不算高，但是代码长度绝对够短。
        static void Main(string[] args)

        {

            var data = TestData.List;



            Func<List<int>, int, List<int>> add =

            (x, id) =>

            {

                x.Insert(0, id);

                return x;

            };



            Func<List<TestInfo>, int?, List<int>> sort = null;

            sort = (x, id) =>

            {

                List<int> r = new List<int>();

                var q = from i in x where i.ParentId == id orderby i.OrderId select add(sort(x, i.Id), i.Id);

                foreach (var item in q.ToList())

                {

                    r.AddRange(item);

                }

                return r;

            };



            var result = sort(data, null);

            foreach (var item in result)

            {

                Console.Write(item + " ");

            }

            /*2 3 5 8 4 9 1 7 6 10*/

        }
绿色夹克衫 2010-03-12
  • 打赏
  • 举报
 回复
程序有点长，给个排版好的吧。



using System.Collections.Generic;



namespace csdnTest

{

    public class TestInfo

    {

        public int Id { get; set; }

        public int? ParentId { get; set; }

        public int OrderId { get; set; }

    }



    class Program

    {

        public static List<TestInfo> TestList = new List<TestInfo>()    

        {

            new TestInfo() { Id = 1, ParentId = null, OrderId = 2 },

            new TestInfo() { Id = 2, ParentId = null, OrderId = 1 },

            new TestInfo() { Id = 3, ParentId = 2, OrderId = 1 },

            new TestInfo() { Id = 4, ParentId = 2, OrderId = 3 },

            new TestInfo() { Id = 5, ParentId = 2, OrderId = 2 },

            new TestInfo() { Id = 6, ParentId = 1, OrderId = 2 },

            new TestInfo() { Id = 7, ParentId = 1, OrderId = 1 },

            new TestInfo() { Id = 8, ParentId = 5, OrderId = 1 },

            new TestInfo() { Id = 9, ParentId = 2, OrderId = 4 },

            new TestInfo() { Id = 10, ParentId = null, OrderId = 3 }

        };



        public static Dictionary<int?, TestInfo> TestDict = new Dictionary<int?, TestInfo>();

        public static Stack<TestInfo> StackA = new Stack<TestInfo>();

        public static Stack<TestInfo> StackB = new Stack<TestInfo>();



        static void Main(string[] args)

        {

            foreach (TestInfo item in TestList)

                TestDict.Add(item.Id, item);



            TestList.Sort(CompareTestInfo);

        }



        static int CompareTestInfo(TestInfo infoA, TestInfo infoB)

        {

            StackA.Clear();



            while (infoA.ParentId != null)

            {

                StackA.Push(infoA);

                infoA = TestDict[infoA.ParentId];

            }



            StackB.Clear();



            while (infoB.ParentId != null)

            {

                StackB.Push(infoB);

                infoB = TestDict[infoB.ParentId];

            }



            while (infoA.Equals(infoB))

            {

                if (StackA.Count > 0)

                    infoA = StackA.Pop();

                else

                    return -1;



                if (StackB.Count > 0)

                    infoB = StackB.Pop();

                else

                    return 1;

            }

                

            return infoA.OrderId.CompareTo(infoB.OrderId);

        }

    }

}
绿色夹克衫 2010-03-12
  • 打赏
  • 举报
 回复
效率比较低的一个版本

using System.Collections.Generic;

namespace csdnTest
{
public class TestInfo
{
public int Id { get; set; }
public int? ParentId { get; set; }
public int OrderId { get; set; }
}

class Program
{
public static List<TestInfo> TestList = new List<TestInfo>()
{
new TestInfo() { Id = 1, ParentId = null, OrderId = 2 },
new TestInfo() { Id = 2, ParentId = null, OrderId = 1 },
new TestInfo() { Id = 3, ParentId = 2, OrderId = 1 },
new TestInfo() { Id = 4, ParentId = 2, OrderId = 3 },
new TestInfo() { Id = 5, ParentId = 2, OrderId = 2 },
new TestInfo() { Id = 6, ParentId = 1, OrderId = 2 },
new TestInfo() { Id = 7, ParentId = 1, OrderId = 1 },
new TestInfo() { Id = 8, ParentId = 5, OrderId = 1 },
new TestInfo() { Id = 9, ParentId = 2, OrderId = 4 },
new TestInfo() { Id = 10, ParentId = null, OrderId = 3 }
};

public static Dictionary<int?, TestInfo> TestDict = new Dictionary<int?, TestInfo>();
public static Stack<TestInfo> StackA = new Stack<TestInfo>();
public static Stack<TestInfo> StackB = new Stack<TestInfo>();

static void Main(string[] args)
{
foreach (TestInfo item in TestList)
TestDict.Add(item.Id, item);

TestList.Sort(CompareTestInfo);
}

static int CompareTestInfo(TestInfo infoA, TestInfo infoB)
{
StackA.Clear();

while (infoA.ParentId != null)
{
StackA.Push(infoA);
infoA = TestDict[infoA.ParentId];
}

StackB.Clear();

while (infoB.ParentId != null)
{
StackB.Push(infoB);
infoB = TestDict[infoB.ParentId];
}

while (infoA.Equals(infoB))
{
if (StackA.Count > 0)
infoA = StackA.Pop();
else
return -1;

if (StackB.Count > 0)
infoB = StackB.Pop();
else
return 1;
}

return infoA.OrderId.CompareTo(infoB.OrderId);
}
}
}
cyhf00808 2010-03-11
  • 打赏
  • 举报
 回复
轻轻的飘过，不留一丝痕迹
ipipga 2010-03-11
  • 打赏
  • 举报
 回复
大家要努力呀^^^^^^^^^^^
aimeast 2010-03-11
  • 打赏
  • 举报
 回复
lz只有举例，却没有说按照什么方式排序。

这样看来只是像构造一个树，但是构造和遍历方法是什么？
aimeast 2010-03-11
  • 打赏
  • 举报
 回复
引用 8 楼 wdwwtzy 的回复:
呃 是我说的不清楚吗?我解释一下
最终正确输出的排序是//2 3 5 8 4 9 1 7 6 10
2 --根节点 order为1
  3 --父节点为2 order为1
  5 --父节点为2 order为2
    8 --父节点为5 order为1
  4 --父节点为2 order为3
  9 --父节点为2 order为4
1 --根节点 order为2
  7 --父节点为1 order为1
  6 --父节点为1 order为2
10 --根节点 order为3


2 --根节点 order为1
3 --父节点为2 order为1
5 --父节点为2 order为2
8 --父节点为5 order为1 为什么这个不是在9后面？
4 --父节点为2 order为3
9 --父节点为2 order为4
1 --根节点 order为2
7 --父节点为1 order为1
6 --父节点为1 order为2
10 --根节点 order为3
wdwwtzy 2010-03-11
  • 打赏
  • 举报
 回复
呃 是我说的不清楚吗?我解释一下
最终正确输出的排序是//2 3 5 8 4 9 1 7 6 10
2 --根节点 order为1
3 --父节点为2 order为1
5 --父节点为2 order为2
8 --父节点为5 order为1
4 --父节点为2 order为3
9 --父节点为2 order为4
1 --根节点 order为2
7 --父节点为1 order为1
6 --父节点为1 order为2
10 --根节点 order为3
wdwwtzy 2010-03-11
  • 打赏
  • 举报
 回复
[Quote=引用 9 楼 aimeast 的回复:]
引用 8 楼 wdwwtzy 的回复:呃 是我说的不清楚吗?我解释一下最终正确输出的排序是//2 3 5 8 4 9 1 7 6 10 2 --根节点 order为1   3 --父节点为2 order为1   5 --父节点为2 order为2     8 --父节点为5 order为1   4 --父节点为2 order为3   9 --父节点为2 order为4 1 --根节点 order为2   7 --父节点为1 order为1   6 --父节点为1 order为2 10 --根节点 order为3

2 --根节点 order为1
  3 --父节点为2 order为1
  5 --父节点为2 order为2
   8 --父节点为5 order为1为什么这个不是在9后面？
  4 --父节点为2 order为3
  9 --父节点为2 order为4
1 --根节点 order为2
  7 --父节点为1 order为1
  6 --父节点为1 order为2
10 --根节点 order为3
[/Quote]

因为它是5的子节点嘛....
绿色夹克衫 2010-03-10
  • 打赏
  • 举报
 回复
想完美解决这个问题的话，不是一个排序方法能直接做到的，需要老老实实的先建立树，然后利用先根遍历来获取集合。（也叫先序遍历）

public class TestInfo : IComparable<TestInfo>
{
public int Id { get; set; }
public int? ParentId { get; set; }
public SortedDictionary<int, TestInfo> Childs { get; set; }
public int OrderId { get; set; }

public int CompareTo(TestInfo other)
{
return OrderId.CompareTo(other.OrderId);
}
}
aimeast 2010-03-10
  • 打赏
  • 举报
 回复 
        static void Main()

        {

            var q = from i in TestData.List orderby i.OrderId, i.Id select i.Id;

            var result = q.ToArray();

        }


至于lz说的那个结果，实在是不知道应该怎么操作。
鸭梨山大帝 2010-03-10
  • 打赏
  • 举报
 回复
这句多余的,呵呵 var Results = ListTestInfo.OrderBy(t => t.OrderId);
鸭梨山大帝 2010-03-10
  • 打赏
  • 举报
 回复
这个是你需要的吗?



using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;



namespace ConsoleApplication

{

    class Program

    {

        static void Main(string[] args)

        {

            //最终正确输出的排序是//2 3 5 8 4 9 1 7 6 10 

            List<TestInfo> ListTestInfo = InitData();

            List<TestInfo> ResultList = new List<TestInfo>();

            var Results =  ListTestInfo.OrderBy(t => t.OrderId);

            ResultList.AddRange(ListTestInfo.OrderBy(t => t.OrderId));

            Console.ReadKey();

        }



        static List<TestInfo> InitData()

        {

            List<TestInfo> ret = new List<TestInfo>()

                {

                    new TestInfo() { Id = 1, ParentId = null, OrderId = 7 },

                    new TestInfo() { Id = 2, ParentId = null, OrderId = 1 },

                    new TestInfo() { Id = 3, ParentId = 2, OrderId = 2 },

                    new TestInfo() { Id = 4, ParentId = 2, OrderId = 5},

                    new TestInfo() { Id = 5, ParentId = 2, OrderId = 3 },

                    new TestInfo() { Id = 6, ParentId = 1, OrderId = 9 },

                    new TestInfo() { Id = 7, ParentId = 1, OrderId = 8 },

                    new TestInfo() { Id = 8, ParentId = 5, OrderId = 4 },

                    new TestInfo() { Id = 9, ParentId = 2, OrderId = 6 },

                    new TestInfo() { Id = 10, ParentId = null, OrderId = 10 }

                };

            return ret;

        }

    }



    public class TestInfo

    {

        public int Id { get; set; }

        public int? ParentId { get; set; }

        public int OrderId { get; set; }

    }



}
鸭梨山大帝 2010-03-10
  • 打赏
  • 举报
 回复
最终正确输出的排序是//2 3 5 8 4 9 1 7 6 10

这个好像跟你给出的那些栏位怎么都无法匹配上.

你到底需要什么排序方式,还是说你就是要输出排序为" 最终正确输出的排序是//2 3 5 8 4 9 1 7 6 10 "
tanbin_0521 2010-03-10
  • 打赏
  • 举报
 回复
数据处理救星降世Power Query
0/ Excel数据处理新利器来了，准备好了吗？ 1/ 比网红函数VLOOKUP还全面的功能。——查（查询） 2/ 取其精华，去其糟粕。...——聚（聚合） 9/ 我自己的难题自己造函数，不求教别人。——技法（自定义函数）
论各种排序算法
初学算法，这里发表一下自己对排序的见解，顺便向大家求教如何找一本或者怎么能够学好算法，不会忘记，现在好多书只教如何理解发明者发明的代码，代码我们可以看懂，这不难，如何学到这里面的思想呢？学到了思想才能...
两个有序单链表的合并排序算法
设计两个有序单链表的合并排序算法 ListList MergeList(LiskList La, LinkList Lb){ Lnode *pa = La->next; Lnode *pb = Lb->next; if(Lb->next == null) return La; if(La->next == null) ...
排序算法复习——交换类排序
在交换类排序算法中，有冒泡排序和快速排序。冒泡排序：这个算法大家估计很熟悉了，不做介绍了。这里有一个算法优化的地方，那就是设置标志位，如果在上一趟的比较当中，没有进行交换的话，就说明已经排好序了，不...
排序算法之冒泡排序：一种优化的冒泡排序算法
 一种改进的方法，就是在每次中间排序之后，比较一下数据是否已经按照顺序排列完成。如果排列完成，则退出排序过程，否则继续进行冒泡排序。这样，对于数据比较有规则的，可以加速算法的执行过程。  下面给出该...
C#

110,546

社区成员

642,561

社区内容

发帖
与我相关
我的任务
社区描述
.NET技术 C#
社区管理员
  • C#
  • Web++
  • by_封爱
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告

让您成为最强悍的C#开发者

试试用AI创作助手写篇文章吧

+ 用AI写文章