#pragma once
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
//void swap(int* a, int* b)
//{
// int temp = *a;
// *a = *b;
// *b = temp;
//
//}
void Bubble_Sort(int *a, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size - i - 1; j++)
{
if (a[j] > a[j + 1])
{
swap(a[j], a[j + 1]);
}
}
}
}
void Insert_Sort(int* a, int size)
{
for (int i = 0; i < size - 1; i++)
{
int end = i;
int x = a[end + 1];
while (end >= 0)
{
if (a[end] > x)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = x;
}
}
void Shell_Sort(int* a, int size)
{
int gap = 3;
while (gap>=1)
{
for (int i = gap; i < size-gap; i += gap)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end = end - gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
gap--;
}
}
void Select_Sort(int a[], int size)
{
int begin = 0;
int end = size - 1;
while (begin < end)
{
int minx = begin;
int maxx = begin;
for (int i = begin; i < end; i++)
{
if (a[i] < a[minx])
{
minx = i;
}
if (a[i] > a[maxx])
{
maxx = i;
}
}
swap(a[minx], a[begin]);
if (maxx == begin)
{
maxx = minx;
}
swap(a[maxx], a[end]);
begin++;
end--;
}
}
int Quick_Sort_First(int* a, int left, int right)
{
int key = a[left];
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[left] = a[right];
while (left < right && a[left] <= key)
{
left++;
}
a[right] = a[left];
//swap(a[left], a[right]);
}
a[left] = key;
return left;
}
int Quick_Sort_second(int* a, int left, int right)
{
//首先选择一个坑位 如
int piovit = left;
int key = a[piovit];//记录坑值
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[piovit] = a[right];
piovit = right;
while (left < right && a[left] <= key)
{
left++;
}
a[piovit] = a[left];
piovit = left;
}
a[piovit] = key;
return piovit;
}
int Quick_Sort_third(int* a, int left, int right)
{
int cur = left + 1;
int prev = left;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur) {
swap(a[cur], a[prev]);
}
++cur;
}
swap(a[prev], a[key]);
return prev;
}
void Quick_Sort(int* a, int left,int right)
{
while (left >= right)
{
return;
}
int mid = Quick_Sort_third(a, left, right);
Quick_Sort(a, left, mid-1 );
Quick_Sort(a, mid + 1, right);
}
void merge_sort(int* a, int* tmp, int left, int right)
{
if (left >= right)
{
return;
}
int mid = left + (right - left) / 2;
merge_sort(a, tmp, left, mid);
merge_sort(a, tmp,mid + 1, right);
int begin1 = left;
int end1 = mid;
int begin2 = mid + 1;
int end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1];
begin1++;
}
else
{
tmp[index++] = a[begin2];
begin2++;
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2<= end2)
{
tmp[index++] = a[begin2++];
}
for (int i = left; i <=right; i++)
{
a[i] = tmp[i];
}
}
void Merge_Sort(int* a, int sz)
{
int* tmp = new int[sz];
merge_sort(a, tmp, 0, sz - 1);
//delete[]tmp;
}
void Adjust_Down(int* a, int root, int n)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
if (a[child] > a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void Heap_Sort(int* a, int n)
{
for (int i = (n - 2) / 2; i >= 0; i--)
{
Adjust_Down(a, i, n);
}
int end = n - 1;
while (end > 0)
{
swap(a[0], a[end]);
Adjust_Down(a, 0, end);//(精髓是end)
end--;
}
}
void Non_Qucik_Sort(int* a, int n)
{
int left = 0;
int right = n - 1;
stack<int> st;
st.push(left);
st.push(right);
while (!st.empty())
{
int Right = st.top();
st.pop();
int Left = st.top();
st.pop();
int mid = Quick_Sort_third(a, Left, Right);
if (Left + 1 < mid)
{
st.push(Left);
st.push(mid);
}
if (mid + 1 < Right)
{
st.push(mid + 1);
st.push(Right);
}
}
}
void merge_sort(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
int i = begin1;
int j = begin1;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
for (; j <= end2; j++)
{
a[j] = tmp[j];
}
}
void Non_Merge_Sort(int* a, int n)
{
int* tmp = new int[n];
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
if (begin2 >=n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
merge_sort(a, tmp, begin1, end1, begin2, end2);
}
gap = gap*2;
}
}
// 计数排序
void Count_Sort(int* a, int n)
{
int min = INT_MAX;
int max = INT_MIN;
for (int i = 0; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min + 1;
int* tmp = new int[range];
for (int k = 0; k < range; k++)
{
tmp[k] = 0;
}
//统计次数
for (int i = 0; i < n; i++)
{
tmp[a[i]-min]++;
}
int index = 0;
for (int j = 0; j < range; j++)
{
while (tmp[j]--)
{
a[index++] = j + min;
}
}
}
|
