Задача: Поразрядная сортировка массива подсчетом
Исходник: неоптимизированная версия, язык: C++ [code #10, hits: 9248]
автор: this [добавлен: 21.01.2006]
  1. // глобальные константы (значения заданы для примера)
  2. const int n = 10;
  3. const int width = 2;
  4. const int range = 10;
  5.  
  6. void RadixEnumSort(int x[]) {
  7. int source[n] = {0};
  8.  
  9. for (int step = 0, rangepow = 1; step < width; step++, rangepow *= range) {
  10.  
  11. int count[range] = {0};
  12. memcpy(source, x, sizeof(source));
  13.  
  14. for (int i = 0; i < n; i++) {
  15. int d = (source[i] / rangepow) % range;
  16. count[ d ]++;
  17. }
  18.  
  19. int summNum = 0;
  20. for (int i = 0; i < range; i++) {
  21. int tmp = count[i];
  22. count[i] = summNum;
  23. summNum += tmp;
  24. }
  25.  
  26. for (int i = 0; i < n; i++) {
  27. int d = (source[i] / rangepow) % range;
  28. x[ count[d] ] = source[i];
  29. count[d]++;
  30. }
  31. }
  32. }
Производительность: ~ О(width*(2n + range))
Расход памяти: ~ (2n + range)
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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