排序链表的最佳方法（在我的情况下）？ [英] Best method to sort a linked list (in my case)?

问题描述

嗨！


我想将数据（游戏中的敌人）存储为链接列表，每个节点都会显示如下内容： ：


struct node

{

double x，y; // x和y位置坐标

struct enemy * enemydata; //保存有关敌人的信息（在游戏中）

//它是一个双链表节点

struct node * prev;


struct node * next;

};


链接列表中每个节点的x和y坐标都会因每一帧而变化。

在将enemys绘制到游戏屏幕（图形内存）之前，我希望

根据y坐标（最低的第一个）对整个列表进行排序。


我的问题是，你推荐哪种排序算法？由于它是一个链接的

列表，我认为插入排序可以作为链接列表插入

sort的最佳情况。但我想从更有经验的

程序员那里得到一些意见。请大概我的英语不好，这不是我的母语

语言。


祝你好运，

肯特

Hi!

I want to store data (of enemys in a game) as a linked list, each node will
look something like the following:

struct node
{
double x,y; // x and y position coordinates
struct enemy *enemydata; // Holds information about an enemy (in a game)
// Its a double linked list node
struct node *prev;

struct node *next;
};

Each node′s x and y coordinates in the linked list changes for every frame.
Before drawing the enemys to the game screen (graphic memory) i would like
to sort the entire list based on the y coordinate (lowest first).

My question is, wich sort algorithm do you recommend? As it is a linked
list, i thought that insertion sort would work as a linked list is insertion
sort′s "best case". But i would like some opinions from more experienced
programmers about this. Please excouse my poor english, it is not my native
language.

Best regards,
Kent

推荐答案

Kent写道：

嗨！

我想存储数据一个游戏）作为一个链表，每个节点将看起来如下：

struct node
{x /> double x，y; // x和y位置坐标
struct enemy * enemydata; //保存有关敌人的信息（在游戏中）
//它是一个双链表节点
struct node * prev;

struct node * next;
链接列表中的每个节点的x和y坐标都会针对每个帧进行更改。
在将enemys绘制到游戏屏幕（图形内存）之前，我想要
根据y坐标（最低的第一个）对整个列表进行排序。

我的问题是，您推荐哪种排序算法？由于它是一个链接的列表，我认为插入排序可以作为链接列表插入
排序的最佳情况。但我想从更有经验的程序员那里得到一些意见。请求我的英语不好，这不是我的母语。

Hi!

I want to store data (of enemys in a game) as a linked list, each node will
look something like the following:

struct node
{
double x,y; // x and y position coordinates
struct enemy *enemydata; // Holds information about an enemy (in a game)
// Its a double linked list node
struct node *prev;

struct node *next;
};

Each node′s x and y coordinates in the linked list changes for every frame.
Before drawing the enemys to the game screen (graphic memory) i would like
to sort the entire list based on the y coordinate (lowest first).

My question is, wich sort algorithm do you recommend? As it is a linked
list, i thought that insertion sort would work as a linked list is insertion
sort′s "best case". But i would like some opinions from more experienced
programmers about this. Please excouse my poor english, it is not my native
language.

这似乎不是关于C的问题，而是关于

选择算法。 comp.graphics.algorithms对你的问题来说是一个更好的论坛。您可能希望

使用一种算法，该算法利用您的

列表几乎已排序的事实。首先，即使该方法

对随机特别有用。列表。


-
Er ****** ***@sun.com

>这似乎不是关于C的问题，而是关于

> This does not seem to be a question about C, but about

选择算法。 comp.graphics.algorithms对你的问题来说是一个更好的论坛。您可能希望使用一种算法，该算法利用您的
列表几乎已排序的事实。首先，即使该方法对于随机不是特别有用。列表。

choosing an algorithm. comp.graphics.algorithms would be a
better forum for your question. You will probably want to
use an algorithm that takes advantage of the fact that your
list is "almost sorted" to begin with, even if that method
is not especially good for "random" lists.

它也不是图形算法。如果其他人有一个实际的

答案，我会非常感激。

It isn′t about a graphical algorithm either. If someone else has an actual
answer i would appreciate it much.

在文章< 3F ********* ****** @ sun.com>，

Eric Sosman< Er ********* @ sun.com>写道：

In article <3F***************@sun.com>,
Eric Sosman <Er*********@sun.com> wrote:

Kent写道：

嗨！

我想存储数据（游戏中的敌人） ）作为一个链表，每个节点将看起来如下：

struct node
{x /> double x，y; // x和y位置坐标
struct enemy * enemydata; //保存有关敌人的信息（在游戏中）
//它是一个双链表节点
struct node * prev;

struct node * next;
链接列表中的每个节点的x和y坐标都会针对每个帧进行更改。
在将enemys绘制到游戏屏幕（图形内存）之前，我想要
根据y坐标（最低的第一个）对整个列表进行排序。

我的问题是，您推荐哪种排序算法？由于它是一个链接的列表，我认为插入排序可以作为链接列表插入
排序的最佳情况。但我想从更有经验的程序员那里得到一些意见。请求我的英语不好，这不是我的母语。

Hi!

I want to store data (of enemys in a game) as a linked list, each node will
look something like the following:

struct node
{
double x,y; // x and y position coordinates
struct enemy *enemydata; // Holds information about an enemy (in a game)
// Its a double linked list node
struct node *prev;

struct node *next;
};

Each node′s x and y coordinates in the linked list changes for every frame.
Before drawing the enemys to the game screen (graphic memory) i would like
to sort the entire list based on the y coordinate (lowest first).

My question is, wich sort algorithm do you recommend? As it is a linked
list, i thought that insertion sort would work as a linked list is insertion
sort′s "best case". But i would like some opinions from more experienced
programmers about this. Please excouse my poor english, it is not my native
language.

这似乎不是关于C的问题，而是关于
选择算法。 comp.graphics.algorithms对你的问题来说是一个更好的论坛。您可能希望使用一种算法，该算法利用您的
列表几乎已排序的事实。首先，即使该方法对于随机不是特别有用。列表。

This does not seem to be a question about C, but about
choosing an algorithm. comp.graphics.algorithms would be a
better forum for your question. You will probably want to
use an algorithm that takes advantage of the fact that your
list is "almost sorted" to begin with, even if that method
is not especially good for "random" lists.

shakersort（交替方向的bubblesort）对于这个

的情况非常好，并且对于双向链表很有效。

shakersort (bubblesort in alternating directions) is quite good for this
situation, and works quite well with a doubly linked list.

这篇关于排序链表的最佳方法（在我的情况下）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！