[Все сортировки]
Теория: Wikipedia
Практика: acmp.ru
Реализация:
Условимся, что мы обрабатываем только массив неотрицательных целых чисел.
Первая реализация обрабатывает разряды десятичного числа начиная с младших. Количество разрядов в числе задается в константе RADIX_AMOUNT.
- typedef unsigned int UINT;
- . . .
- void radix_sort10(UINT* &a, int size) {
- UINT* b = new UINT[size];
- UINT* title = new UINT[10];
- UINT* count = new UINT[10];
- UINT* prev = new UINT[size];
-
- memset(count,0,sizeof(UINT) * 10);
- char curDig;
- int osn = 10;
- int del = 1;
- for (int r=0;r<RADIX_AMOUNT;r++) {
- for (int i=0;i<size;i++) {
- curDig = (a[i] % osn) / del;
- prev[i] = title[curDig];
- title[curDig] = i;
- count[curDig]++;
- }
- int bPos = size;
- for (int i=9;i>=0;i--) {
- while (count[i]) {
- b[--bPos] = a[title[i]];
- title[i] = prev[title[i]];
- count[i]--;
- }
- }
- osn *= 10; del *= 10;
- swap(a,b);
- }
- delete[] b;
- delete[] title;
- delete[] count;
- delete[] prev;
- }
* This source code was highlighted with Source Code Highlighter.Вторая реализация обрабатывает цифру, состоящую из 8 байт. Т.е. исходное число обрабатывается в системе счисления с основанием 256 и содержит не более 4 цифр.
- void radix_sort256(UINT* &a, int size) {
- UINT* b = new UINT[size];
- UINT* title = new UINT[256];
- UINT* count = new UINT[256];
- UINT* prev = new UINT[size];
- UINT mask[4] = {0x000000FF,
- 0x0000FF00,
- 0x00FF0000,
- 0xFF000000};
-
- memset(count,0,sizeof(UINT) * 256);
- unsigned char curDig;
- for (int r=0;r<1;r++) {
- for (int i=0;i<size;i++) {
- curDig = a[i] & mask[r];
- prev[i] = title[curDig];
- title[curDig] = i;
- count[curDig]++;
- }
- int bPos = size;
- for (int i=255;i>=0;i--) {
- while (count[i]) {
- b[--bPos] = a[title[i]];
- title[i] = prev[title[i]];
- count[i]--;
- }
- }
- swap(a,b);
- }
- delete[] b;
- delete[] title;
- delete[] count;
- delete[] prev;
- }
* This source code was highlighted with Source Code Highlighter.
