152 lines
4.2 KiB
C++
152 lines
4.2 KiB
C++
#ifndef SORT_H
|
|
#define SORT_H
|
|
|
|
#include "Array.h"
|
|
#include "Object.h"
|
|
|
|
namespace Kylin {
|
|
|
|
class Sort : public Object {
|
|
public:
|
|
template <typename T>
|
|
static void select(T array[], size_t size) {
|
|
for (size_t i = 0; i < size; i++) {
|
|
size_t index = i;
|
|
for (size_t j = i + 1; j < size; j++) {
|
|
if (array[j] < array[index]) index = j;
|
|
}
|
|
if (index != i) swap(array[i], array[index]);
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
static void insert(T array[], int size) {
|
|
for (int i = 1; i < size; i++) {
|
|
T value = array[i];
|
|
int index = i;
|
|
for (int j = i - 1; j >= 0; j--) {
|
|
if (value < array[j]) {
|
|
array[j + 1] = array[j];
|
|
index = j;
|
|
} else
|
|
break;
|
|
}
|
|
if (index != i) array[index] = value;
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
static void bubble(T array[], int size) {
|
|
bool swaped = true;
|
|
for (int i = 0; (i < size) && swaped; i++) {
|
|
swaped = false;
|
|
for (int j = size - 1; j > i; j--) {
|
|
if (array[j] < array[j - 1]) {
|
|
swap(array[j], array[j - 1]);
|
|
swaped = true;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
static void shell(T array[], size_t size) {
|
|
size_t gap = size;
|
|
do {
|
|
gap = gap / 3 + 1;
|
|
for (size_t i = 0; i < size; i += gap) {
|
|
size_t index = i;
|
|
for (size_t j = i + gap; j < size; j++) {
|
|
if (array[j] < array[index]) {
|
|
index = j;
|
|
}
|
|
}
|
|
if (index != i) swap(array[index], array[i]);
|
|
}
|
|
|
|
} while (gap > 1);
|
|
}
|
|
|
|
template <typename T>
|
|
static void quick(T array[], size_t size) {
|
|
quick(array, 0, size - 1);
|
|
}
|
|
|
|
template <typename T>
|
|
static void merge(T array[], size_t size) {
|
|
T *helper = new T[size];
|
|
merge(array, helper, 0, size - 1);
|
|
delete[] helper;
|
|
}
|
|
|
|
protected:
|
|
template <typename T>
|
|
static void merge(T array[], T helper[], size_t begin, size_t end) {
|
|
if (begin >= end) return;
|
|
size_t middle = (begin + end) / 2;
|
|
merge(array, helper, begin, middle);
|
|
if (middle < end) merge(array, helper, middle + 1, end);
|
|
merge(array, helper, begin, middle, end);
|
|
}
|
|
|
|
template <typename T>
|
|
static void merge(T array[], T helper[], size_t begin, size_t middle, size_t end) {
|
|
size_t i = begin, j = middle + 1, k = begin;
|
|
while ((i <= middle) && (j <= end)) {
|
|
if (array[i] < array[j]) {
|
|
helper[k++] = array[i++];
|
|
} else {
|
|
helper[k++] = array[j++];
|
|
}
|
|
}
|
|
while (i <= middle) {
|
|
helper[k++] = array[i++];
|
|
}
|
|
while (j <= end) {
|
|
helper[k++] = array[j++];
|
|
}
|
|
|
|
for (size_t i = begin; i <= end; i++) {
|
|
array[i] = helper[i];
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
static void quick(T array[], size_t begin, size_t end) {
|
|
if (begin >= end) return;
|
|
auto pivot = partition(array, begin, end);
|
|
if (pivot > 0) quick(array, begin, pivot - 1);
|
|
quick(array, pivot + 1, end);
|
|
}
|
|
|
|
template <typename T>
|
|
static size_t partition(T array[], size_t begin, size_t end) {
|
|
T value = array[begin];
|
|
while (begin < end) {
|
|
while ((begin < end) && (array[end] > value)) {
|
|
end--;
|
|
}
|
|
swap(array[begin], array[end]);
|
|
while ((begin < end) && (array[begin] <= value)) {
|
|
begin++;
|
|
}
|
|
swap(array[begin], array[end]);
|
|
}
|
|
return begin;
|
|
}
|
|
|
|
template <typename T>
|
|
static void swap(T &a, T &b) {
|
|
T c(a);
|
|
a = b;
|
|
b = c;
|
|
}
|
|
|
|
Sort() = delete;
|
|
Sort(const Sort &) = delete;
|
|
Sort &operator=(const Sort &) = delete;
|
|
};
|
|
} // namespace Kylin
|
|
|
|
#endif // SORT_H
|