Поразрядная сортировка MSD

@Innsa · Регистрация: 17.10.2021

Студворк — интернет-сервис помощи студентам

Добрый день.
Сравнение производится поразрядно: сначала сравниваются значения одного крайнего разряда, и элементы группируются по результатам этого сравнения, затем сравниваются значения следующего разряда, соседнего, и элементы либо упорядочиваются по результатам сравнения значений этого разряда внутри образованных на предыдущем проходе групп, либо переупорядочиваются в целом, но сохраняя относительный порядок, достигнутый при предыдущей сортировке. Затем аналогично делается для следующего разряда, и так до конца.

Это такая сортировка:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void SortMSD1 (int* mas, int low, int high, unsigned int mask){
     
     int i = low;
     int j = high;
     
    
     if (mask <=0 || low >= high)
        return;
     while (j != i){
 
           while ((!(mask & (unsigned int)mas[i])) && i < j)
                 i++;
           while ((mask & (unsigned int)mas[j]) && i < j)
                 j--;
           swap (mas[i], mas[j]);
     }
     if ((! (mask & (unsigned int)mas[i])))
        j++;
     SortMSD1 (mas, low, j-1, mask >> 1);
     SortMSD1 (mas, j, high, mask >> 1);   
}
 
void MSD1 (int* mas, int n){
     
    int i;
    unsigned int mask = 0;
    for (i = 0; i < n; i++)
        mask |= (unsigned int)mas[i];
    for (i = 0x80000000; i & mask; i >>= 1);
    SortMSD1 (mas, 0, n - 1, i);
}

Поразрядная сортировка (MSD) (Разряд: 1, 2, 4, 8 двоичных разрядов).

Что такая, за сортировка MSD - 2, MSD - 4 и MSD - 8?

Код их есть, но не могу понять, как это работает.

MSD - 2:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int *AH = NULL;
#define digit2(A,R) (((int)A >> (R*2)) & 0x3)
void SortMSD2 (int mas[], int low, int high, int R){
 
    int i = 0;
    int Cnt[5] = {0};
    if (R < 0)
        return;
    if (high - low <= 10){
        Sort1 (mas + low, high - low + 1);
        return;
    }
    for (i = low; i <= high; i++) {
        Cnt[digit2(mas[i],R)+1]++;
    }
    for (i = 1; i < 5; i++) {
        Cnt[i] += Cnt [i-1];
    }        
    for (i = low; i <= high; i++) {
        AH[Cnt[digit2(mas[i],R)]++] = mas[i];
    }
    for (i = low; i <= high; i++) {
        mas[i] = AH[i-low];
    }
    SortMSD2(mas, low, low + Cnt[0] - 1, R-1);   
    for (i = 0; i <= 4; i++) {
    SortMSD2(mas, low + Cnt[i], low + Cnt[i+1] - 1, R-1);
    }
}
 
void MSD2 (int mas[], int n){
     
    AH = (int*)malloc(sizeof(int)*n);
    SortMSD2(mas, 0, n-1, 3);
    free (AH); 
}

MSD - 4:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define digit4(A,R) (((int)A >> (R*4)) & 0xF)
void SortMSD4 (int mas[], int low, int high, int R){
 
    int i = 0;
    int Cnt[17] = {0};
    if (R < 0)
        return;
    if (high - low <= 10){
        Sort1 (mas + low, high - low + 1);
        return;
    }
    for (i = low; i <= high; i++) {
        Cnt[digit4(mas[i],R)+1]++;
    }
    for (i = 1; i < 17; i++) {
        Cnt[i] += Cnt [i-1];
    }        
    for (i = low; i <= high; i++) {
        AH[Cnt[digit4(mas[i],R)]++] = mas[i];
    }
    for (i = low; i <= high; i++) {
        mas[i] = AH[i-low];
    }
    SortMSD4(mas, low, low + Cnt[0] - 1, R-1);   
    for (i = 0; i < 16; i++) {
    SortMSD4(mas, low + Cnt[i], low + Cnt[i+1] - 1, R-1);
    }
}
 
void MSD4 (int mas[], int n){
     
    AH = (int*)malloc(sizeof(int)*n);
    SortMSD4(mas, 0, n-1, 3);
    free (AH); 
}

MSD - 8:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define digit8(A,R) (((int)A >> (R*8)) & 0xFF)
void SortMSD8 (int mas[], int low, int high, int R){
 
    int i = 0;
    int Cnt[257] = {0};
    if (R < 0)
        return;
    if (high - low <= 10){
        Sort1 (mas + low, high - low + 1);
        return;
    }
    for (i = low; i <= high; i++) {
        Cnt[digit8(mas[i],R)+1]++;
    }
    for (i = 1; i < 257; i++) {
        Cnt[i] += Cnt [i-1];
    }        
    for (i = low; i <= high; i++) {
        AH[Cnt[digit8(mas[i],R)]++] = mas[i];
    }
    for (i = low; i <= high; i++) {
        mas[i] = AH[i-low];
    }
    SortMSD8(mas, low, low + Cnt[0] - 1, R-1);   
    for (i = 0; i < 256; i++) {
    SortMSD8(mas, low + Cnt[i], low + Cnt[i+1] - 1, R-1);
    }
}
 
void MSD8 (int mas[], int n){
     
    AH = (int*)malloc(sizeof(int)*n);
    SortMSD8(mas, 0, n-1, 3);
    free (AH); 
}

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .