Реализации алгоритмов/Сортировка/Поразрядная: различия между версиями
Содержимое удалено Содержимое добавлено
→К переименованию: Использован шаблон. |
|||
Строка 1:
{{К переименованию | 2014-05-02 | Реализации алгоритмов/Сортировка/Поразрядная}}
{{wikipedia|Поразрядная сортировка}}
== C++ ==
Radix sort, MSD. Для char-строк. Ноль - конец строки. На основе рекурсии. Глубина рекурсии = длина строки + 1.
В каждой рекурсии требуется память для размещения двух массивов указателей: StringItem* front[256], т.е. 2Кб;
Строка 17 ⟶ 19 :
{
// количество вариантов значения одного разряда (char)
const int iRange = 256;
//массив bucket-ов (под-списков)
StringItem* front[iRange];
memset(front, 0, sizeof(front) );
StringItem** ppNextItem[iRange];
for (int i = 0; i < iRange; i++)
ppNextItem[i]=&front[i];
Строка 67 ⟶ 69 :
</source>
Программа для тестирования
<source lang = "cpp">
void TestAlgorithm()
{
// открываем, большой текстовый файл для теста
ifstream file("demo.txt");
if ( !file )
return;
Строка 81 ⟶ 83 :
vector<string> vecs(ii, eos);
// заполняем список
StringItem* pList = NULL;
StringItem** ppCurr = &pList;
Строка 89 ⟶ 91 :
(*ppCurr )->str = vecs[i].c_str();
(*ppCurr )->next = NULL;
ppCurr = &(*ppCurr)->next;
}
Строка 116 ⟶ 118 :
if (!bit)
return;
if (size < 2)
return;
| |||