Posts Tagged ‘算法’

排序算法是大家刚学编程的时候一定要学的算法，冒泡算法(bubble sort)，快速排序(quick sort)等等相信大家耳熟能详。我下面要介绍的bucket sort其实大家应该也学过，不过最近刚刚帮别人交了一份作业，勾起了不少回忆，所以顺便在这里发出来。下面的算法有几个限制：所排序的一定要是正整数，至于整数的大小和个数都是可以修改的。

[code:c#]

#include
#include 

#define MAX_INT 65536
#define MAX_NO_INPUT 1000

struct bucket{
 int data;
 bucket* next;
};

void addToBucket(struct bucket *head[],int value)
{
 bucket* current;

 if (head[value] == NULL)
 {
  head[value] = (bucket*)malloc(sizeof(bucket));
  head[value]->data = value;
  head[value]->next = NULL;
 }
 else
 {
  current = head[value];
  while (current->next != NULL)
   current = current->next;
  current->next = (bucket*)malloc(sizeof(bucket));
  current->next->data = value;
  current->next->next = NULL;
 }
}
void printOut(bucket* head[],int size)
{
 int i=0;
 bucket *current;
 FILE *fp;

 fp = fopen("output.txt","w");

 for (i=size-1;i>=0;i--)
 {
  if (head[i] == NULL)
   continue;
  current = head[i];
  while(current != NULL)
  {
   fprintf(fp,"%d\n",current->data);
   current = current->next;
  }
 }
 fclose(fp);
}
int main()
{
 bucket* head[MAX_INT] = {NULL};
 int unsorted[MAX_NO_INPUT];
 FILE *fp;
 int i=0;

 //read in a file
 if ((fp = fopen("input.txt","r"))==NULL)
 {
  printf("Cannot open file");
  exit(0);
 }

 i=0;
 while (fscanf(fp,"%i\n",&unsorted[i])!=EOF && i< MAX_NO_INPUT)
  i++;
 fclose(fp);

 int length = i;
 i = 0;
 for (i=0;i

[/code]

以上的算法时间复杂度是O(n)。算是比较快速的排序算法，不过就跟所有算法一样，其实都是时间和空间上的取舍。它的空间复杂度相当大，尤其是在整数上限很大的情况下，更是占用了不少内存。所以，大家还是要按情况使用。

C#是一种高级语言，他其中一个特性就是Managed code的概念。整个C#的程序都是在.NET runtime里运行的，这个设计能够有效防止程序员一些错误的编程，有效提高了程序的稳定性。但如果我们有时候真的需要直接操作内存，或者想写一些高效的代码，是不是就没办法了呢？实际上，C#并没有完全去掉对指针和底层memory操作的支持。可是如果要想使用指针的话，就必须使用unsafe这个关键字。unsafe可以使用在一个方法上：

[code:c#]

unsafe int GetSomeNumber()
{
  //code that can use pointers
}

[/code]

当然，你也可以使用unsafe将真个类包起来：

[code:c#]

unsafe class MyClass
{
}

[/code]

同样的，也可以将类中的某个属性标记为unsafe

[code:c#]

class MyClass
{
  unsafe int* pX;
}

[/code]

或者你可以只将代码中的某一段包起来

[code:c#]

void MyMethod()
{
  //code that doesn't use pointers
  unsafe
  {
  }
}

[/code]

可是对于方法内部的本地变量，是不可以标识为unsafe的：

[code:c#]

int MyMethod()
{
  unsafe int *pX;   //WRONG
}

[/code]

如果想在方法内部使用一个指针性的本地变量的话，就要将该方法标识为unsafe或者在unsafe block内部声明该变量。最后，你只要在project properties里面的Build页面把allow unsafe code选项勾上就可以了。C#中关于指针的语法和C/C++差不多，在这里就不再详述了。唯一区别是在声明指针变量上面，C++是int *px, *py;而C#是int* px,py;在C#中*是跟随类型而不是跟随变量名的。

类成员的指针

在C#中，指向类的指针是不允许的。因为C#的garbage collector并没有维护指针的信息，指针指向的内存有可能在程序运行的时候被回收，造成意想不到的后果。可是我们有没有办法将指针指向类中的变量呢？比如我们有一个如下的类：

[code:c#]

class MyClass
{
  public long x;
  public float F;
}
MyClass myObject = new MyClass();
long* p: = &(myObject.X);
float* pF = &(myObject.F);

[/code]

如果你尝试编译以上代码的话你就会发现编译器会返回一个编译错误。原因就是因为在C#中，类是放在heap上的，garbage collector有可能随时将一个类移到新的地方，使得本来的指针指向了一个错误的位置。要解决这个问题，就要使用fixed关键字。将以上代码做以下的修改：

[code:c#]

MyClass myObject = new MyClass();
fixed(long* pL = &(myObject.X))
{
  //do something
}

[/code]

使用了fixed关键字，garbage collector就不会将该类移动到别处。fixed关键字还可以有以下用法：

[code:c#]

fixed(long *pL = &(myObject.X))
fixed(float *pF = &(myObject.F))
{
}

[/code]

或者

[code:c#]

fixed(long * pX=&(myObject.X), px2=&(myObject2.X))
{
}

[/code]