学步园

  <<AtA>>上的一道思考题.昨天开始琢磨,今天又琢磨到现在.我承认我脑袋比较迷糊,但也有点慢得让我接受不了了."不急跬步,无以至千里;不积小流,无以成江海",只能如此安慰自己了.呵呵.

  问题本身就是,给定 N 个数的集合S, S {X | X ∈ S, 0 <= X <= k).恩.书上是1,我这里出现的是0.多了个数罢了.要求是,修改计数排序,以完成在 O (N + K) 时间完成排序的任务,并且只能使用 O (K) 的存储空间.

  昨天刚看到的时候,比较迷糊.后来,搜了一下,便发现了方法.我想说的是,一旦我想照着别人去做,我往往做不好.并非就是如此给自己定义了,而确实是这回事呢.呵呵.自己知道方法后,安心地去写,其实还是可以的.老想着现成的东西是怎么做的,很难做好.还好,最终写出来了.不然心就堵死了,一晚上得憋气死...

  核心的思想就是,把元素放在正确的位置上,放置完一种值,就将该值的计数 -1 , 当该值计数为 0 时,也就是,所有的此种值都已在正确的位置上,再次遇到无需处理,直接越过.直到,处理完所有数据.

  我说得比较乱,呵呵.代码要来了,看代码吧.

/* 8-2-e-2011-04-26-21.49.c -- 第八章第二题e */<br /> /* N 个 0 ~ K 范围之间的关键字 O (N + K) 时间排序(不稳定) */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <time.h></p> <p>typedef int Item ;</p> <p>#define SIZE (30)<br /> #define K (50)</p> <p>int main (void) ;<br /> void initializeArray (Item * const array, const int size, const Item k) ;<br /> void countingSort (Item * const array, const int size, const Item k) ;<br /> void swap (Item * const pFV, Item * const pSV) ;<br /> void printArray (const Item * const array, const int size) ;</p> <p>int main (void)<br /> {<br /> Item array[SIZE] ;<br /> Item k = K ;<br /> int size = SIZE ;</p> <p> initializeArray (array, size, k) ;<br /> printArray (array, size) ;<br /> countingSort (array, size, k) ;<br /> printArray (array, size) ;</p> <p> return 0 ;<br /> }</p> <p>void initializeArray (Item * const array, const int size, const Item k)<br /> {<br /> int i ;</p> <p> srand ((unsigned int) time (NULL)) ;<br /> for (i = 0; i < size; i++)<br /> array[i] = rand () % k + 1 ;<br /> }</p> <p>void countingSort (Item * const array, const int size, const Item k)<br /> {<br /> Item * count, * position ;<br /> int i, index ;</p> <p> count = (Item *) malloc (sizeof (Item) * (k + 1)) ;<br /> if (NULL == count)<br /> return ;<br /> position = (Item *) malloc (sizeof (Item) * (k + 1)) ;<br /> if (NULL == position)<br /> {<br /> free (count) ;<br /> return ;<br /> }<br /> for (i = 0; i <= k; i++)<br /> count[i] = 0 ;<br /> for (i = 0; i < size; i++)<br /> count[array[i]]++ ;<br /> position[0] = count[0] ;<br /> for (i = 1; i <= k; i++)<br /> position[i] = position[i - 1] + count[i] ;<br /> index = 0 ;<br /> while (index < size)<br /> {<br /> while (index < size && 0 == count[array[index]])<br /> index++ ;<br /> if (size == index)<br /> break ;<br /> count[array[index]]-- ;<br /> if (array[index] != array[--position[array[index]]])<br /> swap (array + index, array + position[array[index]]) ;<br /> }<br /> free (count) ;<br /> free (position) ;<br /> }</p> <p>void swap (Item * const pFV, Item * const pSV)<br /> {<br /> Item temp ;</p> <p> temp = *pFV ;<br /> *pFV = *pSV ;<br /> *pSV = temp ;<br /> }</p> <p>void printArray (const Item * const array, const int size)<br /> {<br /> int i ;</p> <p> for (i = 0; i < size; i++)<br /> printf ("%d/n", array[i]) ;<br /> putchar ('/n') ;<br /> }