// TenSortAlgorithms.h : 此文件包含 "TenSortAlgotrthms" 类。十个常用排序算法 C++ 14
// 2023年4月5日 涂聚文 Geovin Du edit.
#ifndef TENSORTALGORITHMS_H
#define TENSORTALGORITHMS_H
#include <vector> // #include directive
#include <string>
#include <iostream>
#include <string.h>
#include <algorithm>
#include "PigInfo.h"
#include "PigNameInfo.h"
using namespace std;
/**
* @brief 类库空间名
* geovindu edit
* edit date: 20230405
* https://github.com/TheAlgorithms/C-Plus-Plus
* https://learn.microsoft.com/en-us/cpp/standard-library/list-class?view=msvc-170
*/
namespace geovindu
{
/**
*@brief 十个常用排序算法
* edit: geovindu
*/
class TenSortAlgotrthms
{
private:
public:
/**
*@brief
*1.冒泡排序（Bubble Sort） 方法（函数）
* @param [int] 输入参数名称 数组
* 冒泡排序要对一个数组多次重复遍历。它要比较相邻的两项，并且交换顺序排错的项。每对数组进行一次遍历，就会有一个最大项排在了正确的位置。大体上讲，数组的每一个数据项都会在其相应的位置“冒泡”。若数组有n项，则需要遍历n-1次。
*eidit: geovindu
*/
void bubbleSort(vector<int>& query);
/**
*@brief
*2.选择排序（Selection Sort）
* @param [int] 输入参数名称 数组
* 选择排序提高了冒泡排序的性能，它每一次遍历一次数组只会进行一次交换，即在遍历过程中记录最大项的索引，完成遍历后，再把它换到正确的位置，同样若数组有n项，它也需要遍历n-1次。
* edit: geovindu Geovin Du 涂聚文
*/
void selectSort(vector<int>& query);
/**
*@brief
*3.插入排序（Insertion Sort）
* @param [int] 输入参数名称 数组
* 插入排序总是保持一个位置靠前的已经排好的数组，然后每一个新的数据项被“插入”到前边的子表里。共需进行n-1次插入，每进行一次插入，排好的数组增加一项。
* edit: geovindu Geovin Du 涂聚文
*/
void insertSort(vector<int>& query);
/**
*@brief
* 4.归并排序（Merge Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
*归并排序是一种递归算法，持续地将一个数组分成两半。如果数组是空的或者只有一个元素，那么根据定义，它就被排序好了。如果数组里的元素超过一个，我们就把数组拆分，然后分别对两个部分调用递归排序，一旦这两个部分被排序好了，就对这两个部分进行归并。
*eidit: geovindu
*/
void merge(vector<int>& query, int left, int mid, int right);
/**
*@brief
* 归并排序（Merge Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
*归并排序是一种递归算法，持续地将一个数组分成两半。如果数组是空的或者只有一个元素，那么根据定义，它就被排序好了。如果数组里的元素超过一个，我们就把数组拆分，然后分别对两个部分调用递归排序，一旦这两个部分被排序好了，就对这两个部分进行归并。
*eidit: geovindu
*/
void merge_Sort(vector<int>& queryq, int left, int right);
/**
*@brief
* 归并排序（Merge Sort）
* @param [int] 输入参数名称 数组
*归并排序是一种递归算法，持续地将一个数组分成两半。如果数组是空的或者只有一个元素，那么根据定义，它就被排序好了。如果数组里的元素超过一个，我们就把数组拆分，然后分别对两个部分调用递归排序，一旦这两个部分被排序好了，就对这两个部分进行归并。
*eidit: geovindu
*/
void mergeSort(vector<int>& query);
/**
*@brief
* 5.快速排序（Quick Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
*eidit: geovindu
*/
void quick_Sort(vector<int>& query, int left, int right);
/**
*@brief
* 快速排序（Quick Sort）
* @param [int] 输入参数名称 数组
*
*eidit: geovindu
*/
void quickSort(vector<int>& query);
/**
*@brief
* 6.希尔排序（Shell Sort）
* @param [int] 输入参数名称 数组
*
* eidit: geovindu
*/
void shellSort(vector<int>& query);
/**
*@brief
* 7.计数排序（Heap Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void countingSort(vector<int>& query, int n);
/**
*@brief
* 堆排序（Heap Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void push_down(vector<int>& heap, int size, int u);
/**
*@brief
* 堆排序（Heap Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void push_up(vector<int>& heap, int u);
/**
*@brief
*8. 堆排序（Heap Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void heapSort(vector<int>& query, int n);
/**
*@brief
* 基数排序（Radix Sort）
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
int getRadix(int x, int i);
/**
*@brief
* 9.基数排序（Radix Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void radixSort(vector<int>& query, int n);
/**
*@brief
* 10.桶排序（Bucket Sort)
* @param [int] 输入参数名称 数组
*
* eidit: geovindu
*/
void bucketSort(vector<int>& query);
};
/**
*@brief
*冒泡排序（Bubble Sort） 方法（函数）
*@param [int] 输入参数名称 数组
* 冒泡排序要对一个数组多次重复遍历。它要比较相邻的两项，并且交换顺序排错的项。每对数组进行一次遍历，就会有一个最大项排在了正确的位置。大体上讲，数组的每一个数据项都会在其相应的位置“冒泡”。若数组有n项，则需要遍历n-1次。
*eidit: geovindu
*/
void TenSortAlgotrthms::bubbleSort(vector<int>& query) {
int n = query.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (query[j] > query[j + 1]) {
swap(query[j], query[j + 1]);
}
}
}
}
/**
*@brief 选择排序（Selection Sort）
* @param [int] 输入参数名称 数组
* 选择排序提高了冒泡排序的性能，它每一次遍历一次数组只会进行一次交换，即在遍历过程中记录最大项的索引，完成遍历后，再把它换到正确的位置，同样若数组有n项，它也需要遍历n-1次。
* edit: geovindu Geovin Du 涂聚文
*/
void TenSortAlgotrthms::selectSort(vector<int>& query) {
int n = query.size();
for (int i = 0; i < n - 1; i++) {
int index = 0;
for (int j = 1; j < n - i; j++) {
if (query[j] > query[index]) {
index = j;
}
}
swap(query[index], query[n - 1 - i]);
}
}
/**
*@brief 插入排序（Insertion Sort）
* @param [int] 输入参数名称 数组
* 插入排序总是保持一个位置靠前的已经排好的数组，然后每一个新的数据项被“插入”到前边的子表里。共需进行n-1次插入，每进行一次插入，排好的数组增加一项。
* edit: geovindu Geovin Du 涂聚文
*/
void TenSortAlgotrthms::insertSort(vector<int>& query) {
int n = query.size();
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (query[j] < query[j - 1]) {
swap(query[j], query[j - 1]);
}
else {
break;
}
}
}
}
/**
*@brief
* 归并排序（Merge Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
*@param [int] 输入参数名称 数
*归并排序是一种递归算法，持续地将一个数组分成两半。如果数组是空的或者只有一个元素，那么根据定义，它就被排序好了。如果数组里的元素超过一个，我们就把数组拆分，然后分别对两个部分调用递归排序，一旦这两个部分被排序好了，就对这两个部分进行归并。
*eidit: geovindu
*/
void TenSortAlgotrthms::merge(vector<int>& query, int left, int mid, int right) {
vector<int> temp = query;
int i = left, j = mid + 1;
int index = left;
while (i <= mid || j <= right) {
if (i > mid) {
query[index++] = temp[j];
j++;
}
else if (j > right) {
query[index++] = temp[i];
i++;
}
else if (temp[i] < temp[j]) {
query[index++] = temp[i];
i++;
}
else {
query[index++] = temp[j];
j++;
}
}
}
/**
*@brief
* 归并排序（Merge Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
*归并排序是一种递归算法，持续地将一个数组分成两半。如果数组是空的或者只有一个元素，那么根据定义，它就被排序好了。如果数组里的元素超过一个，我们就把数组拆分，然后分别对两个部分调用递归排序，一旦这两个部分被排序好了，就对这两个部分进行归并。
*eidit: geovindu
*/
void TenSortAlgotrthms::merge_Sort(vector<int>& query, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
merge_Sort(query, left, mid);
merge_Sort(query, mid + 1, right);
if (query[mid] > query[mid + 1]) {
merge(query, left, mid, right);
}
}
/**
*@brief
* 归并排序（Merge Sort）
* @param [int] 输入参数名称 数组
*归并排序是一种递归算法，持续地将一个数组分成两半。如果数组是空的或者只有一个元素，那么根据定义，它就被排序好了。如果数组里的元素超过一个，我们就把数组拆分，然后分别对两个部分调用递归排序，一旦这两个部分被排序好了，就对这两个部分进行归并。
*eidit: geovindu
*/
void TenSortAlgotrthms::mergeSort(vector<int>& query) {
int n = query.size();
merge_Sort(query, 0, n - 1);
}
/**
*@brief
* 快速排序（Quick Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void TenSortAlgotrthms::quick_Sort(vector<int>& query, int left, int right) {
if (left >= right) return;
int i = left, j = right, base = query[left]; //取最左边的数为基数
while (i < j) {
while (query[j] >= base && i < j) {
j--;
}
while (query[i] <= base && i < j) {
i++;
}
if (i < j) {
swap(query[i], query[j]);
}
}
query[left] = query[i];
query[i] = base;
quick_Sort(query, left, i - 1);
quick_Sort(query, i + 1, right);
}
/**
*@brief
* 快速排序（Quick Sort）
* @param [int] 输入参数名称 数组
*
* eidit: geovindu
*/
void TenSortAlgotrthms::quickSort(vector<int>& query) {
int n = query.size();
quick_Sort(query, 0, n - 1);
}
/**
*@brief
* 希尔排序（Shell Sort）
* @param [int] 输入参数名称 数组
*
* eidit: geovindu
*/
void TenSortAlgotrthms::shellSort(vector<int>& query) {
int gap = query.size() / 2;
while (gap) {
for (int i = gap; i < query.size(); i += gap) {
int t = query[i], j;
for (j = i - gap; j >= 0; j -= gap) {
if (query[j] > t)
query[j + gap] = query[j];
else
break;
}
query[j + gap] = t;
}
gap /= 2;
}
}
/**
*@brief
* 计数排序（Heap Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void TenSortAlgotrthms::countingSort(vector<int>& query, int n) {
vector<int> cnt(101, 0);
for (int i = 0; i < n; i++)
cnt[query[i]]++;
for (int i = 0, k = 0; i <= 100; i++) {
while (cnt[i]) {
query[k++] = i;
cnt[i]--;
}
}
}
/**
*@brief
* 堆排序（Heap Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void TenSortAlgotrthms::push_down(vector<int>& heap, int size, int u)
{
int t = u, left = u * 2, right = u * 2 + 1;
if (left <= size && heap[left] > heap[t])
t = left;
if (right <= size && heap[right] > heap[t])
t = right;
if (u != t) {
swap(heap[u], heap[t]);
push_down(heap, size, t);
}
}
/**
*@brief
* 堆排序（Heap Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void TenSortAlgotrthms::push_up(vector<int>& heap, int u) {
while (u / 2 && heap[u / 2] < heap[u]) {
swap(heap[u / 2], heap[u]);
u /= 2;
}
}
/**
*@brief
* 堆排序（Heap Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void TenSortAlgotrthms::heapSort(vector<int>& query, int n)
{
int size = n;
for (int i = 1; i <= n; i++)
push_up(query, i);
for (int i = 1; i <= n; i++) {
swap(query[1], query[size]);
size--;
push_down(query, size, 1);
}
}
/**
*@brief
* 基数排序（Radix Sort）
* @param [int] 输入参数名称 数
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
int TenSortAlgotrthms::getRadix(int x, int i)
{
while (i--)
x /= 10;
return x % 10;
}
/**
*@brief
* 基数排序（Radix Sort）
* @param [int] 输入参数名称 数组
* @param [int] 输入参数名称 数
* eidit: geovindu
*/
void TenSortAlgotrthms::radixSort(vector<int>& query, int n)
{
vector<vector<int>> cnt(10);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 10; j++)
cnt[j].clear();
for (int j = 0; j < n; j++)
cnt[getRadix(query[j], i)].push_back(query[j]);
for (int j = 0, k = 0; j < 10; j++) {
for (int x : cnt[j])
query[k++] = x;
}
}
}
/**
*@brief
* 桶排序（Bucket Sort)
* @param [int] 输入参数名称 数组
* eidit: geovindu
*/
void TenSortAlgotrthms::bucketSort(vector<int>& query)
{
//求最大最小值
int max = query[0];
int min = query[0];
for (int i = 1; i < query.size(); ++i)
{
if (query[i] > max) max = query[i];
if (query[i] < min) min = query[i];
}
//确定桶数量
int bucketSize = (max - min) / query.size() + 1;
vector<vector<int>> bucket(bucketSize);
//遍历arr,将数据放入桶内
for (int i = 0; i < query.size(); ++i)
{
int idx = (query[i] - min) / query.size();
bucket[idx].push_back(query[i]);
}
// 对桶内数据排序
int k = 0;
for (int i = 0; i < bucket.size(); ++i)
{
//********此处排序 可以选择之前7种排序方法，这些排序方法决定了算法时间复杂度和稳定性*******
// sort(bucket[i].begin(), bucket[i].begin() + bucket[i].size());
if (!bucket[i].empty())
{
std::sort(bucket[i].begin(), bucket[i].end());
for (int a : bucket[i]) query[k++] = a;
}
}
}
};
#endif