Сортировка по радиусу на месте с последующим линейным сканированием
Алгоритм сортировки по месту
В зависимости от того, что вы на самом деле считаете сложностью по времени сортировки по радиксу, это решение O (N) время, хотя мое личное мнение не так.Я думаю, что если вы не сделаете предположение о линейном времени для целочисленной сортировки, то проблема неразрешима.
Из-за того, что сортировка на месте, есть только O (1) дополнительнотребуется хранилище.
Весь код C ++ 11
Шаг 1: Сортировка по радикалу на месте
template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
{
if (zerosEnd+1 >= onesBegin-1 || mask == 0)
return;
int zerosEnd2 = zerosEnd;
int onesBegin2 = onesBegin;
while(zerosEnd2+1 <= onesBegin2-1)
{
// swap ones to the right
if ((myArray[zerosEnd2+1] & mask) != 0)
{
std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
--onesBegin2;
}
else
++zerosEnd2;
}
mask >>= 1;
//recurse on lhs
RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);
//recurse on rhs
RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
}
template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void InPlaceRadixSort(std::vector<T>& myArray)
{
int zerosEnd = -1;
int onesBegin = static_cast<int>(myArray.size());
T mask = static_cast<T>(1) << sizeof(T)*8-1;
while(zerosEnd+1 <= onesBegin-1)
{
if ( (myArray[zerosEnd+1] & mask) != 0)
{
std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
--onesBegin;
}
else
++zerosEnd;
}
mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
//recurse on lhs
RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
//recurse on rhs
RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));
// swap negatives to the front
auto iterSmallest = std::min_element(myArray.begin(), myArray.end());
if (*iterSmallest < 0)
{
std::reverse(myArray.begin(), myArray.end());
iterSmallest = std::min_element(myArray.begin(), myArray.end());
std::reverse(myArray.begin(), iterSmallest+1);
std::reverse(iterSmallest+1, myArray.end());
}
}
Шаг 2: Линейное сканирование на наличие дублирующих элементов
for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
{
if (myArray[i] == myArray[j])
{
std::cout << "Found duplicate element " << myArray[i];
}
}
Полный код
#include <iostream>
#include <string>
#include <vector>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <type_traits>
using namespace std;
#define N 10
template <typename T>
void PrintArray(const std::vector<T>& myArray)
{
for (auto&& element : myArray)
{
std::cout << element << std::endl;
}
}
template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
{
if (zerosEnd+1 >= onesBegin-1 || mask == 0)
return;
int zerosEnd2 = zerosEnd;
int onesBegin2 = onesBegin;
while(zerosEnd2+1 <= onesBegin2-1)
{
// swap ones to the right
if ((myArray[zerosEnd2+1] & mask) != 0)
{
std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
--onesBegin2;
}
else
++zerosEnd2;
}
mask >>= 1;
//recurse on lhs
RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);
//recurse on rhs
RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
}
template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void InPlaceRadixSort(std::vector<T>& myArray)
{
int zerosEnd = -1;
int onesBegin = static_cast<int>(myArray.size());
T mask = static_cast<T>(1) << sizeof(T)*8-1;
while(zerosEnd+1 <= onesBegin-1)
{
if ( (myArray[zerosEnd+1] & mask) != 0)
{
std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
--onesBegin;
}
else
++zerosEnd;
}
mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
//recurse on lhs
RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
//recurse on rhs
RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));
// swap negatives to the front
auto iterSmallest = std::min_element(myArray.begin(), myArray.end());
if (*iterSmallest < 0)
{
std::reverse(myArray.begin(), myArray.end());
iterSmallest = std::min_element(myArray.begin(), myArray.end());
std::reverse(myArray.begin(), iterSmallest+1);
std::reverse(iterSmallest+1, myArray.end());
}
}
int main() {
srand(time(NULL));
std::vector<int> myArray(N);
for (size_t i=0;i<myArray.size();++i)
{
myArray[i] = rand() % 100 * (rand() % 2 == 1?-1:1);
}
std::cout << "Vector before radix sort: " << std::endl;
PrintArray(myArray);
InPlaceRadixSort(myArray);
std::cout << "Vector after radix sort: " << std::endl;
PrintArray(myArray);
for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
{
if (myArray[i] == myArray[j])
{
std::cout << "Found duplicate element " << myArray[i];
}
}
return 0;
}