本帖最后由 古月不傲 于 2020-11-21 17:45 编辑
[C++] 纯文本查看 复制代码 #ifndef _CONFIG_H_
#define _CONFIG_H_
#define LENTH 20
#define HIDE 0
#endif
[C++] 纯文本查看 复制代码 #ifndef _AB_SORT_H_
#define _AB_SORT_H_
#include <iostream>
#include "config.h"
using namespace std;
namespace _sort
{
template <typename _type>
class ab_sort
{
public:
virtual ~ab_sort() {}
public:
virtual void sort() = 0;
virtual unsigned int get_swapped_times() const = 0;
protected:
_type *m_arr;
unsigned int m_len;
unsigned int m_swapped_times; // 交换次数
};
}
#endif
[C++] 纯文本查看 复制代码 #ifndef _SELECT_SORT_H_
#define _SELECT_SORT_H_
#include "ab_sort.h"
// 选择排序 很慢
/*
时间复杂度： 平均 O(n^2) 最好 O(n^2) 最差 O(n^2)
空间复杂度： O(1)
稳定性： 不稳定 举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法
*/
namespace _sort
{
template <typename _type>
class select_sort : public ab_sort<_type>
{
public:
select_sort(_type *arr, unsigned int len);
~select_sort();
public:
virtual void sort() override;
virtual unsigned int get_swapped_times() const override;
};
}
namespace _sort
{
template <typename _type>
select_sort<_type>::select_sort(_type *arr, unsigned int len)
{
if (arr == nullptr || len == 0)
return;
this->m_arr = arr;
this->m_len = len;
this->m_swapped_times = 0;
}
template <typename _type>
select_sort<_type>::~select_sort() {}
template <typename _type>
void select_sort<_type>::sort()
{
// 这里之所以-1 是由于最后只剩下两个元素进行比较过后 大的已经放入最后
for (int i = 0; i < this->m_len - 1; i++)
{
for (int j = i + 1; j < this->m_len; j++)
{
if (this->m_arr[i] > this->m_arr[j])
{
swap(this->m_arr[i], this->m_arr[j]);
this->m_swapped_times++;
}
}
}
}
template <typename _type>
unsigned int select_sort<_type>::get_swapped_times() const
{
return this->m_swapped_times;
}
}
#endif
[C++] 纯文本查看 复制代码 #ifndef _BUBBLE_SORT_H_
#define _BUBBLE_SORT_H_
#include "ab_sort.h"
// 冒泡排序 很慢
/*
时间复杂度： 平均 O(n^2) 最好 O(n^2) 最差 O(n^2)
空间复杂度： O(1)
稳定性： 稳定 波纹交换 所以不会打乱顺序
*/
namespace _sort
{
template <typename _type>
class bubble_sort : public ab_sort<_type>
{
public:
bubble_sort(_type *arr, unsigned int len);
~bubble_sort();
public:
virtual void sort() override;
virtual unsigned int get_swapped_times() const override;
};
}
namespace _sort
{
template <typename _type>
bubble_sort<_type>::bubble_sort(_type *arr, unsigned int len)
{
if (arr == nullptr || len == 0)
return;
this->m_arr = arr;
this->m_len = len;
this->m_swapped_times = 0;
}
template <typename _type>
bubble_sort<_type>::~bubble_sort() {}
template <typename _type>
void bubble_sort<_type>::sort()
{
this->m_swapped_times = 0;
bool is_swapped;
for (int i = 0; i < this->m_len - 1; i++)
{
is_swapped = true;
// 由于冒泡的特性 和选择相反 每次导致最后一个值最大 所以-i
for (int j = 0; j < this->m_len - 1 - i; j++)
{
if (this->m_arr[j] > this->m_arr[j + 1])
{
swap(this->m_arr[j], this->m_arr[j + 1]);
this->m_swapped_times++;
is_swapped = false;
}
}
// 如果后面数据都是有序的就没必要再做比较
if (is_swapped)
break;
}
}
template <typename _type>
unsigned int bubble_sort<_type>::get_swapped_times() const
{
return this->m_swapped_times;
}
}
#endif
[C++] 纯文本查看 复制代码 #ifndef _INSERT_SORT_H_
#define _INSERT_SORT_H_
#include "ab_sort.h"
// 插入排序 很慢
/*
时间复杂度： 平均 O(n^2) 最好 O(n^2) 最差 O(n^2)
空间复杂度： O(1)
稳定性： 稳定 理论上就是选择排序的思想 但是是逆向 6 8 5 5 9 这里的第一5会比后面的5先跑到前面去
*/
namespace _sort
{
template <typename _type>
class insert_sort : public ab_sort<_type>
{
public:
insert_sort(_type *arr, unsigned int len);
~insert_sort();
public:
virtual void sort() override;
virtual unsigned int get_swapped_times() const override;
};
}
namespace _sort
{
template <typename _type>
insert_sort<_type>::insert_sort(_type *arr, unsigned int len)
{
if (arr == nullptr || len == 0)
return;
this->m_arr = arr;
this->m_len = len;
this->m_swapped_times = 0;
}
template <typename _type>
insert_sort<_type>::~insert_sort() {}
template <typename _type>
void insert_sort<_type>::sort()
{
int current, current_index;
for (int i = 1; i < this->m_len; i++)
{
current = this->m_arr[i];
current_index = i;
// 思想就是每前进一步就和它之前的数一一对比 通过选择排序的思想 让第一个数始终最小
while (current_index - 1 >= 0 && current < this->m_arr[current_index - 1])
{
this->m_arr[current_index] = this->m_arr[current_index - 1];
current_index--;
this->m_swapped_times++;
}
this->m_arr[current_index] = current;
}
}
template <typename _type>
unsigned int insert_sort<_type>::get_swapped_times() const
{
return this->m_swapped_times;
}
}
#endif
[C++] 纯文本查看 复制代码 #ifndef _SHELL_SORT_H_
#define _SHELL_SORT_H_
#include "ab_sort.h"
// 希尔排序 慢
/*
插入排序升级版 原理实际上是分治 先将一个大的数组从右到左切割n次进行初步排序 形成一定的顺序 这样最后一轮插入排序的交换次数会变少
假设是20 切割后 10 5 2 1 理论上越往后交换的次数越少
时间复杂度： 平均 O(n^（1.3—2） 最好 O(n^1.3) 最差 O(n^2)
稳定性： 不稳定 分组的原因可能会到导致错乱
空间复杂度： O(1)
*/
namespace _sort
{
template <typename _type>
class shell_sort : public ab_sort<_type>
{
public:
shell_sort(_type *arr, unsigned int len);
~shell_sort();
public:
virtual void sort() override;
virtual unsigned int get_swapped_times() const override;
};
}
namespace _sort
{
template <typename _type>
shell_sort<_type>::shell_sort(_type *arr, unsigned int len)
{
if (arr == nullptr || len == 0)
return;
this->m_arr = arr;
this->m_len = len;
this->m_swapped_times = 0;
}
template <typename _type>
shell_sort<_type>::~shell_sort() {}
template <typename _type>
void shell_sort<_type>::sort()
{
int current, current_index;
for (int gap = this->m_len / 2; gap >= 1; gap = gap / 2)
{
for (int i = gap; i < this->m_len; i++)
{
current = this->m_arr[i];
current_index = i;
// 同插入排序
while (current_index - gap >= 0 && current < this->m_arr[current_index - gap])
{
this->m_arr[current_index] = this->m_arr[current_index - gap];
current_index -= gap;
this->m_swapped_times++;
}
this->m_arr[current_index] = current;
}
}
}
template <typename _type>
unsigned int shell_sort<_type>::get_swapped_times() const
{
return this->m_swapped_times;
}
}
#endif
[C++] 纯文本查看 复制代码 #ifndef _MERGE_SORT_H_
#define _MERGE_SORT_H_
#include "ab_sort.h"
#include <vector>
// 归并排序 慢
/*
发明者 冯诺伊曼 切割成小块 分治排序
时间复杂度： 平均 O(nlogn) 最好O(nlogn) 最差O(n^2)
稳定性： 稳定
空间复杂度： O(n)
*/
namespace _sort
{
template <typename _type>
class merge_sort : public ab_sort<_type>
{
public:
merge_sort(_type *arr, unsigned int len);
~merge_sort();
public:
virtual void sort() override;
virtual unsigned int get_swapped_times() const override;
private:
void sort(_type *arr, int left, int right);
void meger(int *arr, int left, int mid, int right);
private:
int m_left;
int m_right;
};
}
namespace _sort
{
template <typename _type>
merge_sort<_type>::merge_sort(_type *arr, unsigned int len)
{
if (arr == nullptr || len == 0)
return;
this->m_arr = arr;
this->m_len = len;
this->m_swapped_times = 0;
this->m_left = 0;
this->m_right = len - 1;
}
template <typename _type>
merge_sort<_type>::~merge_sort() {}
template <typename _type>
void merge_sort<_type>::sort()
{
this->sort(this->m_arr, this->m_left, this->m_right);
}
template <typename _type>
void merge_sort<_type>::sort(_type *arr, int left, int right)
{
// 递归出口 两个相等说明不能再分割
if (right <= left)
return;
int mid = (left + right) / 2;
// 左边切割成小块
sort(arr, left, mid);
// 右边切割成小块
sort(arr, mid + 1, right);
// 归并
meger(arr, left, mid, right);
}
template <typename _type>
void merge_sort<_type>::meger(int *arr, int left, int mid, int right)
{
vector<int> vec(right - left + 1);
int index = 0;
int loc_left = left;
int loc_right = mid + 1;
// 两边哪个小 先放哪个
while (loc_left <= mid && loc_right <= right)
{
vec[index++] = arr[loc_left] <= arr[loc_right] ? arr[loc_left++] : arr[loc_right++];
this->m_swapped_times++;
}
// 剩下的放入数组
while (loc_left <= mid)
{
vec[index++] = arr[loc_left++];
this->m_swapped_times++;
}
// 剩下的放入数组
while (loc_right <= right)
{
vec[index++] = arr[loc_right++];
this->m_swapped_times++;
}
// 放回原数组
for (int t = 0; t < vec.size(); t++)
arr[left++] = vec[t];
}
template <typename _type>
unsigned int merge_sort<_type>::get_swapped_times() const
{
return this->m_swapped_times;
}
}
#endif
[C++] 纯文本查看 复制代码 #ifndef _QUICK_SORT_H_
#define _QUICK_SORT_H_
#include "ab_sort.h"
// 快速排序 很快 数据越多 性能越能体现 是其他排序的 n^2
/*
发明者 托尼·霍尔
时间复杂度： 平均 O(nlogn) 最好O(nlogn) 最差O(n^2)
稳定性： 稳定
空间复杂度： O(nlog2n)
*/
namespace _sort
{
template <typename _type>
class quick_sort : public ab_sort<_type>
{
public:
quick_sort(_type *arr, unsigned int len);
~quick_sort();
public:
virtual void sort() override;
virtual unsigned int get_swapped_times() const override;
private:
void sort(_type *arr, int left, int right);
int partition(_type *arr, int left, int right);
private:
int m_left;
int m_right;
};
}
namespace _sort
{
template <typename _type>
quick_sort<_type>::quick_sort(_type *arr, unsigned int len)
{
if (arr == nullptr || len == 0)
return;
this->m_arr = arr;
this->m_len = len;
this->m_swapped_times = 0;
this->m_left = 0;
this->m_right = len - 1;
}
template <typename _type>
quick_sort<_type>::~quick_sort() {}
template <typename _type>
void quick_sort<_type>::sort()
{
this->sort(this->m_arr, this->m_left, this->m_right);
}
template <typename _type>
void quick_sort<_type>::sort(_type *arr, int left, int right)
{
// 递归出口 两个相等说明不能再分割
if (right <= left)
return;
// 找基数
int pivot = partition(arr, left, right);
// 排左边
sort(arr, left, pivot - 1);
// 排右边
sort(arr, pivot + 1, right);
}
template <typename _type>
int quick_sort<_type>::partition(_type *arr, int left, int right)
{
// 基数
int key = arr[left];
while (left < right)
{
// 从右往前搜找比基数大的数
while (left < right && arr[right] >= key)
right--;
if (left < right)
{
arr[left] = arr[right];
this->m_swapped_times++;
}
// 从左往后搜找比基数小的数
while (left < right && arr[left] <= key)
left++;
if (left < right)
{
arr[right] = arr[left];
this->m_swapped_times++;
}
}
arr[left] = key;
this->m_swapped_times++;
return left;
}
template <typename _type>
unsigned int quick_sort<_type>::get_swapped_times() const
{
return this->m_swapped_times;
}
}
#endif
[C++] 纯文本查看 复制代码 #ifndef _SORT_H_
#define _SORT_H_
#include "include/select_sort.h"
#include "include/bubble_sort.h"
#include "include/insert_sort.h"
#include "include/shell_sort.h"
#include "include/merge_sort.h"
#include "include/quick_sort.h"
#endif
[C++] 纯文本查看 复制代码 #include <iostream>
#include <ctime>
#include "sort.h"
using namespace std;
// 排序
namespace _sort
{
template <typename _type>
class solution_sort
{
public:
solution_sort(ab_sort<_type> *sort) : m_sort(sort) {}
~solution_sort() {}
public:
void start()
{
this->m_sort->sort();
}
unsigned get_swapped_times() const
{
return this->m_sort->get_swapped_times();
}
private:
// 禁止拷贝 赋值 防止深拷贝
solution_sort(const solution_sort<_type> &obj) = delete;
solution_sort<_type> &operator= (const solution_sort<_type> &obj) = delete;
private:
ab_sort<_type> *m_sort;
};
};
int main(void)
{
srand((unsigned int)(time(NULL)));
int arr[LENTH] = {0};
_sort::ab_sort<int> *select = new _sort::select_sort<int>(arr, LENTH);
_sort::ab_sort<int> *bubble = new _sort::bubble_sort<int>(arr, LENTH);
_sort::ab_sort<int> *insert = new _sort::insert_sort<int>(arr, LENTH);
_sort::ab_sort<int> *shell = new _sort::shell_sort<int>(arr, LENTH);
_sort::ab_sort<int> *merge = new _sort::merge_sort<int>(arr, LENTH);
_sort::ab_sort<int> *quick = new _sort::quick_sort<int>(arr, LENTH);
const char *arr_sort_name[] = {"select_sort", "bubble_sort", "insert_sort", "shell_sort", "merge_sort", "quick_sort"};
_sort::ab_sort<int> *arr_sort_pointer[] = {select, bubble, insert, shell, merge, quick};
for (int i = 0; i < 6; i++)
{
for (int i = 0; i < LENTH; i++)
arr[i] = rand() % (LENTH * 100);
printf("================================================================\n");
printf("%s\n", arr_sort_name[i]);
_sort::solution_sort<int> sort_obj(arr_sort_pointer[i]);
sort_obj.start();
if (!HIDE)
{
for (int i = 0; i < LENTH; i++)
printf("%d ", arr[i]);
}
printf("\n");
printf("%s swpped_times:%d\n", arr_sort_name[i], sort_obj.get_swapped_times());
delete arr_sort_pointer[i];
}
return 0;
} | 
发表于 2020-11-19 22:30
