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

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