#include "Sort.h"
void PrintArray(int* a, int n) {
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
void Swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustDown(int* a, int parent, int n) {
int maxChild = (parent << 1) + 1;
while (maxChild < n)
{
if (maxChild + 1 < n && a[maxChild + 1] > a[maxChild]) {
maxChild = maxChild + 1;
}
if (a[parent] >= a[maxChild])
return;
else {
Swap(&a[parent], &a[maxChild]);
parent = maxChild;
maxChild = (parent << 1) + 1;
}
}
}
int GetMid(int* a, int left, int right) {
int mid = (left + right) >> 1;
if (a[left] < a[mid]) {
if (a[right] < a[left]) {
return left;
} else if (a[right] > a[mid]) {
return mid;
} else
return right;
}
else {
if (a[right] > a[left]) {
return left;
} else if (a[right] < a[mid]) {
return mid;
} else
return right;
}
}
void InsertSort(int* a, int n) {
for (int i = 0; i <= n - 2; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (a[end] > tmp) {
a[end + 1] = a[end];
end--;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1;
for (int i = 0; i <= n - gap - 1; i++) {
int end = i;
int tmp = a[end + gap];
while (end >= 0) {
if (a[end] > tmp) {
a[end + gap] = a[end];
end -= gap;
} else {
break;
}
}
a[end + gap] = tmp;
}
}
}
void SelectSort(int* a, int n) {
int begin = 0, end = n - 1;
int minn, maxx;
while (begin < end) {
minn = begin, maxx = begin;
for (int i = begin + 1; i <= end; i++) {
if (a[i] < a[minn]) {
minn = i;
}
if (a[i] > a[maxx]) {
maxx = i;
}
}
Swap(&a[minn], &a[begin]);
if (maxx == begin) {
maxx = minn;
}
Swap(&a[maxx], &a[end]);
begin++;
end--;
}
}
void HeapSort(int* a, int n) {
for (int i = (n - 1 - 1) >> 1; i >= 0; i--) {
AdjustDown(a, i, n);
}
int end = n - 1;
while (end > 0) {
Swap(&a[0], &a[end]);
end--;
AdjustDown(a, 0, end + 1);
}
}
void BubbleSort(int* a, int n) {
for (int i = 1; i <= n - 1; i++) {
int flag = 1;
for (int j = 1; j <= n - i; j++) {
if (a[j - 1] > a[j]) {
Swap(&a[j - 1], &a[j]);
flag = 0;
}
}
if (flag)
break;
}
}
int PartSort1(int* a, int left, int right) {
int key = left;
int begin = left, end = right;
while (begin < end) {
while (begin < end && a[end] >= a[key]) {
end--;
}
while (begin < end && a[begin] <= a[key]) {
begin++;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[key], &a[begin]);
return begin;
}
int PartSort2(int* a, int left, int right) {
int mid = GetMid(a, left, right);
Swap(&a[left], &a[mid]);
int key = left;
int slow = left;
int fast = slow + 1;
while (fast <= right) {
if (a[fast] < a[key] && ++slow != fast) {
Swap(&a[fast], &a[slow]);
}
fast++;
}
Swap(&a[key], &a[slow]);
return slow;
}
int PartSort3(int* a, int left, int right) {
int mid = GetMid(a, left, right);
Swap(&a[left], &a[mid]);
int key = a[left];
int hole = left;
int begin = left, end = right;
while (begin < end) {
while (begin < end && a[end] >= key) {
end--;
}
while (begin < end && a[begin] <= key) {
begin++;
}
}
a[hole] = key;
return hole;
}
void QuickSort(int* a, int left, int right) {
if (left >= right)
return;
int key = PartSort3(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
void QuickSortNonR(int* a, int left, int right) {
STK stk;
STKInit(&stk);
STKPush(&stk, right);
STKPush(&stk, left);
while (!STKEmpty(&stk)) {
int begin = STKTop(&stk);
STKPop(&stk);
int end = STKTop(&stk);
STKPop(&stk);
int key = PartSort3(a, begin, end);
if (key + 1 < end) {
STKPush(&stk, end);
STKPush(&stk, key + 1);
}
if (begin < key - 1) {
STKPush(&stk, key - 1);
STKPush(&stk, begin);
}
}
STKDestroy(&stk);
}
void _MergeSort(int* a, int* tmp, int begin, int end) {
if (begin >= end)
return;
int mid = begin + end >> 1;
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int pos = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[pos++] = a[begin1++];
} else
tmp[pos++] = a[begin2++];
}
while (begin1 <= end1) {
tmp[pos++] = a[begin1++];
}
while (begin2 <= end2) {
tmp[pos++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n) {
int* tmp = (int*)malloc(n * sizeof(int));
if (tmp == NULL) {
perror("malloc fail");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}
void MergeSortNonR(int* a, int n) {
int* tmp = (int*)malloc(n * sizeof(int));
if (tmp == NULL) {
perror("malloc fail");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap) {
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (begin2 >= n) {
break;
}
if (end2 >= n) {
end2 = n - 1;
}
int pos = i;
while (begin1 <= end1 && begin2 <= end2) {
if (a[begin1] <= a[begin2])
{
tmp[pos++] = a[begin1++];
} else {
tmp[pos++] = a[begin2++];
}
}
while (begin1 <= end1) {
tmp[pos++] = a[begin1++];
}
while (begin2 <= end2) {
tmp[pos++] = a[begin2++];
}
memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
void CountSort(int* a, int n) {
int minn = a[0], maxx = a[0];
for (int i = 0; i < n; i++) {
if (a[i] < minn) {
minn = a[i];
}
if (a[i] > maxx) {
maxx = a[i];
}
}
int range = maxx - minn + 1;
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL) {
perror("calloc fail");
return;
}
for (int i = 0; i < n; i++)
{
count[a[i] - minn]++;
}
int pos = 0;
for (int i = 0; i < range; i++) {
while (count[i]--) {
a[pos++] = i + minn;
}
}
free(count);
count = NULL;
}