Сушествует множество алгоритмов сортировки. От простого пузырька и до быстрых способов сортировки. Для больших массивов в основном используют встроенную сортировку QuikSort. Довольно быстрый алгоритм. Но в свое время я столкнулся с тем, что при определенном объеме массива, я получал вылет программы из-за переполнения стека. Пришлось искать другие пути. В книге Д.Кнута "Исскуство программирования" Том 3 упоменается малоприменяемый алгоритм Бинарная сортировка. Он считается самым быстрым алгоритмом сортировки. Его время выполнение растет практически линейно от объема массива. Но есть и недостатки. Алгорит каждый раз нужно подстраивать под данные.
Сушность алгоритма очень проста. Сначало сортируем массив по самому старшему биту. Все числа, у которых самый старший бит равен 1 откидываем в один хвост массива, 0 во второй хвост
У нас получилось два подмасива. Соответственно их сортируем также как и раньше, только уже по второму по старшенству биту. И так далее.
Вот моя реализация для массива безнакового 32 разрядного числа.
binsort.h#ifndef BINSORT_H
#define BINSORT_H
/******************************************************************************
// Author: Finch
// Subject: Binary Sort Function of unsigned integer array
// Version 1.0
// Date 24/02/2007
-------------------------------------------------------------------------------
Function of Binary Sort big array
void Binsort(unsigned int *buffer, int size, SortDirection dir);
buffer - array of unsigned int
size - size of buffer
dir - Direction of sort (up, down)
*//////////////////////////////////////////////////////////////////////////////
enum SortDirection {up, down};
void Binsort(unsigned int *buffer, int size, SortDirection dir);
#endif //BINSORT_H
binsort.cpp#include "binsort.h"
inline void change(unsigned int *a, unsigned int *b) {(*a)^=(*b); (*b)^=(*a); (*a)^=(*b);}
void BinsortUp(int left, int right, int level, unsigned int *buffer)
{
if (level<32)
{
int begLeft=left;
int begRight=right;
unsigned ms=0x80000000>>level;
int flag=0;
while (begLeft<begRight)
{
switch (flag)
{
case 0:
if (buffer[begLeft] & ms) begLeft++;
else flag |= 1;
if (!(buffer[begRight] & ms)) begRight--;
else flag |=2;
break;
case 1:
if (!(buffer[begRight] & ms)) begRight--;
else flag |=2;
break;
case 2:
if (buffer[begLeft] & ms) begLeft++;
else flag |= 1;
break;
case 3:
change(&buffer[begLeft], &buffer[begRight]);
flag=0;
break;
}
}
while ((left<begLeft) && (!(buffer[begLeft] & ms))) begLeft--;
while ((begRight <right) && (buffer[begRight] & ms)) begRight++;
if (left != begLeft)
{
if ((begLeft-left)> 1) BinsortUp(left,begLeft,level+1,buffer);
else
{
if (buffer[begLeft] > buffer[left]) change(&buffer[begLeft], &buffer[left]);
}
}
if (begRight != right)
{
if ((right-begRight)>1) BinsortUp(begRight, right, level+1, buffer);
else
{
if (buffer[begRight] < buffer[right]) change(&buffer[right],&buffer[begRight]);
}
}
}
}
void BinsortDown(int left, int right, int level, unsigned int *buffer)
{
if (level<32)
{
int begLeft=left;
int begRight=right;
unsigned ms=0x80000000>>level;
int flag=0;
while (begLeft<begRight)
{
switch (flag)
{
case 0:
if (!(buffer[begLeft] & ms)) begLeft++;
else flag |= 1;
if (buffer[begRight] & ms) begRight--;
else flag |=2;
break;
case 1:
if (buffer[begRight] & ms) begRight--;
else flag |=2;
break;
case 2:
if (!(buffer[begLeft] & ms)) begLeft++;
else flag |= 1;
break;
case 3:
change(&buffer[begLeft], &buffer[begRight]);
flag=0;
break;
}
}
while ((left<begLeft) && (buffer[begLeft] & ms)) begLeft--;
while ((begRight <right) && (!(buffer[begRight] & ms))) begRight++;
if (left != begLeft)
{
if ((begLeft-left)> 1) BinsortDown(left,begLeft,level+1,buffer);
else
{
if (buffer[begLeft] < buffer[left]) change(&buffer[begLeft], &buffer[left]);
}
}
if (begRight != right)
{
if ((right-begRight)>1) BinsortDown(begRight, right, level+1, buffer);
else
{
if (buffer[begRight] > buffer[right]) change(&buffer[right],&buffer[begRight]);
}
}
}
}
void Binsort(unsigned int *buffer, int size, SortDirection dir)
{
if (dir==up) BinsortUp(0, size-1, 0, buffer);
else BinsortDown(0, size-1, 0, buffer);
}
Насчет скорости. Тестовая программа
#include <stdio.h>
#include <stdlib.h>
#include "binsort.h"
#define max 10000000 // Это 10 миллионов знаков в массиве :)
unsigned int buffer[max];
int main()
{
int i;
for(i=0; i<max; i++) buffer[i]=rand()*rand();
Binsort(buffer,max,up);
return 0;
}
Используемое время на моей машине
real 0m11.038s
user 0m8.529s
sys 0m0.124s
Увеличиваем массив до 50 миллионов
real 0m59.668s
user 0m46.147s
sys 0m0.596s
