Задача: Поразрядная сортировка, общий принцип
Исходник: Поразрядная сортировка, оптимизированная версия на списках, язык: C++ [code #12, hits: 8860]
автор: - [добавлен: 21.01.2006]
  1. // Тип: элемент списка
  2. typedef struct slist_ {
  3. long val;
  4. struct slist_ *next;
  5. } slist;
  6.  
  7. slist *radix_list(slist *l) {
  8. // Вспомогательные переменные
  9. int i, j, d;
  10.  
  11. // Параметры сортировки
  12. int range = 10, width = 2;
  13. slist *temp, *out, *head[10], *tail[10];
  14.  
  15. // результирующий массив
  16. out=l;
  17.  
  18. int rangepow = 1;
  19. for (j = 0; j < width; j++) {
  20. for (i = 0; i < range; i++)
  21. head[i] = (tail[i] = NULL);
  22.  
  23. // РАСПРЕДЕЛЕНИЕ
  24. while ( l != NULL ) {
  25. // Значение текущего разряда
  26. d = ((int)(l->val / rangepow)) % range;
  27. temp = tail[d];
  28. if (head[d]==NULL) {
  29. head[d] = l;
  30. } else {
  31. temp->next = l;
  32. }
  33. temp = tail[d] = l;
  34. l = l->next;
  35. temp->next = NULL;
  36. }
  37.  
  38. // Находим первый непустой карман
  39. for (i=0; i < range; i++)
  40. if ( head[i] != NULL ) break;
  41.  
  42. // СБОРКА
  43. l = head[i];
  44. temp = tail[i];
  45. for (d = i+1; d < range; d++) {
  46. if ( head[d] != NULL) {
  47. temp->next = head[d];
  48. temp = tail[d];
  49. }
  50. }
  51. rangepow*=10;
  52. }
  53. return (out);
  54. }
Возвращает указатель на начало отсортированного списка.
slist - тип элемента списка. Может меняться, но главное конечно чтобы в нем присутствовали целочисленное val и ссылка next.

Производительность: ~ O(width*(n + range))
Расход памяти: ~ (n)
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию