define _CRT_SECURE_NO_WARNINGS 1

include"mySort.h"

void mySort::printArr(vector& vec) {
for (const auto& i : vec) {
cout << i<<" ";
}

}

void mySort::BubbleSort(vector &vec) {
for (int j = vec.size() - 1; j >= 1; j--) {
bool flag = true;
for (int i = 0; i < j; i++) {
if (vec[i] > vec[i + 1]) {
swap(vec[i], vec[i + 1]);
flag = false;
}
}
if (flag) break;
}
}

void mySort::SelectSort(vector& vec) {
for(int i=0;i<vec.size()-1;i++)
for (int j = i + 1; j < vec.size(); j++) {
if (vec[i]>vec[j]) {
swap(vec[j], vec[i]);
}
}

}

void mySort::InsertSort(vector& vec) {
for (int j = 1; j < vec.size(); j++) {
for (int i = 0; i < j; i++) {
if (vec[j] < vec[i]) {
int tmp = vec[j];
for (int k = j - 1; k >= i; k--) {
vec[k + 1] = vec[k];
}
vec[i] = tmp;
break;
}
}
}
}
void mySort::ShellInsert(vector& vec, int start, int gap) {
for (int j = start+gap; j < vec.size(); j+=gap) {
for (int i = start; i < j; i+=gap) {
if (vec[j] < vec[i]) {
int tmp = vec[j];
for (int k = j - gap; k >= i; k-=gap) {
vec[k + gap] = vec[k];
}
vec[i] = tmp;
break;
}
}
}
}

void mySort::ShellSort(vector& vec) {
for (int gap = vec.size() / 2; gap >= 1; gap /= 2) {
for (int i = 0; i < gap; i++) {
ShellInsert(vec, i, gap);
}
}
}

void mySort::CountSort(vector& vec) {
//1.先找最大值
//直接用algorithm库中的函数 int max = max_element(vec.begin(), vec.end());
int max = vec[0];
for (int i = 0; i < vec.size(); i++) {
if (vec[i] > max) {
max = vec[i];
}
}
//2.根据最大值开辟数组
int p = new int[max + 1];
memset(p, 0, sizeof(int)*(max+1));
//3.将源数据放入数组中并计数
for (int i = 0; i < vec.size(); i++) {
p[vec[i]]++;//统计vec[i]出现的次数
}
vec.clear();
//4.安照下标依次取计数数组中的元素
for (int i = 0; i < max + 1; i++) {
while (p[i]) {
vec.push_back(i);
p[i]--;
}
}
delete[] p;
}

void mySort::BucketSort(vector& vec) {
int min = *min_element(vec.begin(), vec.end());
int max = *max_element(vec.begin(), vec.end());
int bucketNum = (max - min + 1) / vec.size()+1;
vector<vector> Buckets(bucketNum);
for (int i = 0; i < vec.size(); i++) {
int index = (vec[i] - min + 1) / vec.size();
Buckets[index].push_back(vec[i]);
}
for (int i = 0; i < Buckets.size(); i++) {
sort(Buckets[i].begin(), Buckets[i].end());
}
vec.clear();
for (int i = 0; i < Buckets.size(); i++) {
for (int j = 0; j < Buckets[i].size();j++) {
vec.push_back(Buckets[i][j]);
}
}
}

void mySort::Build_max_heap(vector& vec, int start, int end) {
int cur = start;//从当前节点开始构建大根堆
int l = 2 * cur + 1;//左孩子
for (; l <= end;cur=l,l=2*cur+1) {
if (l<end && vec[l] < vec[l + 1])l++;//l左右孩子里最大的
if (vec[l] >vec[cur]) swap(vec[l], vec[cur]);
else break;
}
}

void mySort::HeapSort(vector& vec) {
for (int i = vec.size() / 2 - 1; i >= 0; i--) {
Build_max_heap(vec, i, vec.size() - 1);
}
for (int i = vec.size() - 1; i > 0; i--) {
swap(vec[0], vec[i]);
Build_max_heap(vec, 0, i-1);
}
}

void mySort::QuickSort(vector& vec, int l, int r) {
if (l >= r) return;
//默认最左侧位基准
int tmp = vec[l];
int i = l, j = r;
while (i < j) {
while (i<j && vec[j] > tmp)j--;//j--后i=j就不用执行下部了
if (i < j) {
vec[i++] = vec[j];
}
while (i < j && vec[i] < tmp) i++;
if (i < j) vec[j--] = vec[i];
}
vec[i] = tmp;
QuickSort(vec, l, i - 1);
QuickSort(vec, i + 1, r);
}

void mySort::Merge_up2down(vector& vec, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
Merge_up2down(vec, l, mid);
Merge_up2down(vec, mid + 1, r);
MergeSort(vec, l, mid, r);
}

void mySort::MergeSort(vector& vec, int l, int mid, int r) {
int* p = new int[r - l + 1];
int i = l, j = mid + 1, index = 0;
while (i <= mid && j <= r) {
if (vec[i] < vec[j]) {
p[index++] = vec[i++];
}
else p[index++] = vec[j++];
}
while (i <= mid) p[index++] = vec[i++];
while (j <= r) p[index++] = vec[j++];
for (int i = 0; i < index; i++) {
vec[l + i] = p[i];
}
delete[] p;
}