基本排序算法
#include<iostream>
#include<vector>
#include<map>
#include<math.h>
using namespace std;
/* 实现了几种基本排序呢算法，目录如下
1. 冒泡 O(n^2) 稳定
2. 选择 O(n^2) 不稳定
3. 插入 O(n^2) 稳定
4. 快速 O(nlog(n)) 不稳定 最差O(n^2)
5. 希尔 O(nlog(n)) 不稳定
6. 归并 O(nlog(n)) 稳定
7. 计数 O(n+k) 非比较,稳定，适用于数据密集的排序
8. 堆排序 O(nlog(n)) 不稳定
9. 基数排序 O(d(r+n)) 稳定,可以实现字符串排序
*/
class MySortAlgorihm{
public:
/* 冒泡排序
type 为 false 从小到大排序, 默认
type 为 true 从大到小排序
*/
template<typename T>
void bubble_sort(vector<T>& data,bool type=false){
int len=data.size();
if(len==0){
return;
}
// 相邻的两两交换， 先把最小/最大的放到最后
for(int i=0;i<len;++i){
for(int j=0;j<len-i-1;++j){
if(!type){
if(data[j]>data[j+1]){
swap(data[j],data[j+1]);
}
}else{
if(data[j]<data[j+1]){
swap(data[j],data[j+1]);
}
}
}
}
}
/* 选择排序
type 为 false 从小到大排序, 默认
type 为 true 从大到小排序
*/
template<typename T>
void selection_sort(vector<T>& data,bool type=0){
int len=data.size();
if(len==0){
return;
}
// 选择最大/最小的放到前面
for(int i=0;i<len-1;++i){
for(int j=i+1;j<len;++j){
if(!type){
if(data[i]>data[j]){
swap(data[i],data[j]);
}
}else{
if(data[i]<data[j]){
swap(data[i],data[j]);
}
}
}
}
}
/* 插入排序, 这是直接插入，还有折半插入，就是找插入位置时从中间开始找
type 为 false 从小到大排序, 默认
type 为 true 从大到小排序
step 是步长，这个是为了适配希尔排序，默认步长为1
*/
template<typename T>
void insertion_sort(vector<T>& data,bool type=0,int step=1){
int len = data.size();
if(len == 0){
return;
}
// 假设前面已经排好序了，往前插入
for(int i=0; i<len-1; ++i){
for(int j=i+step; j-step>=0 && j<len; j=j-step){
if(!type){
if(data[j]<data[j-step]){
swap(data[j],data[j-step]);
}else{
break;
}
}else{
if(data[j]>data[j-step]){
swap(data[j],data[j-step]);
}else{
break;
}
}
}
}
// 原来的没有加step参数的插入排序
// for(int i=0; i<len-1; ++i){
// for(int j=i+1; j>0; --j){
// if(!type){
// if(data[j]<data[j-1]){
// swap(data[j],data[j-1]);
// }else{
// break;
// }
// }else{
// if(data[j]>data[j-1]){
// swap(data[j],data[j-1]);
// }else{
// break;
// }
// }
// }
// }
}
/* 快速排序
type 为 false 从小到大排序, 默认
type 为 true 从大到小排序
*/
template<typename T>
void quick_sort(vector<T>& data, bool type=0){
int len = data.size();
if(len == 0){
return;
}
// 找一个数，左边的都比这个数小，右边的都比这个数大
quick(data,0,len,type);
}
template<typename T>
void quick(vector<T>& data ,int left,int right,int type){
if(left >= right-1){
return;
}
T first = data[left];
int l_i=left,r_i=right-1;
while(l_i<r_i){
if(!type){
while(data[l_i]<=first && l_i<right-1){
l_i++;
}
while(data[r_i]>first && r_i>left ){
r_i--;
}
swap(data[l_i],data[r_i]);
}else{
while(data[l_i]>=first && l_i<right-1){
l_i++;
}
while(data[r_i]<first && r_i>left ){
r_i--;
}
swap(data[l_i],data[r_i]);
}
}
// 最后一步多交换了，所以再交换回来
swap(data[l_i],data[r_i]);
// 然后把标记位的数据放到中间
swap(data[left],data[r_i]);
// 左右两边分别递归排序
quick(data,left,r_i,type);
quick(data,l_i,right,type);
}
/* 希尔排序
type 为 false 从小到大排序, 默认
type 为 true 从大到小排序
*/
template<typename T>
void shell_sort(vector<T>& data, bool type=0){
// int increament=data.size()-1;
int increment = 3;
do{
insertion_sort(data,type,increment);
increment--;
}while(increment>=1);
// insertion_sort(data,0,1);
}
/* 归并排序,这个实现的不是归并排序,只是有用到归并的思想
type 为 false 从小到大排序, 默认
type 为 true 从大到小排序
*/
template<typename T>
void merge_sort(vector<T>& data, bool type=0){
if(data.size()==0){
return;
}
merge(data,0,data.size()-1,type);
}
template<typename T>
void merge(vector<T>& data,int left,int right,bool type){
if(left>=right){
return;
}
int mid = (left+right)/2+1;
merge(data,left,mid-1,type);
merge(data,mid,right,type);
// 这时mid两边的分别排好了，现在需要把left到right之间排序,用一个插入排序,这样就不是归并排序了,应该用额外的空间的...
for(int i=mid;i<=right;++i){
for(int j=i;j>left;--j){
if(!type){
if(data[j]<data[j-1]){
swap(data[j],data[j-1]);
}
}else{
if(data[j]>data[j-1]){
swap(data[j],data[j-1]);
}
}
}
}
}
/* 计数排序，是一种非比较性质的排序算法，计数排序只适用于元素值较为集中的情况，若集合中存在最大最小元素值相差甚远的情况，则计数排序开销较大、性能较差。只能用于整数排序
type 为 false 从小到大排序, 默认
type 为 true 从大到小排序
*/
void count_sort(vector<int>& data, bool type=0){
int len = data.size();
if(len<=1){
return;
}
// 找到data的最大值和最小值，作为数组的下标
int max_data = find_max(data);
int min_data = find_min(data);
int size = max_data-min_data+1;
// int count_array[size]={ 0 };
int count_array[size];
for(int i=0;i<len;++i){
count_array[data[i]-min_data]++;
}
data.clear();
if(!type){
for(int i=0;i<size;++i){
while(count_array[i]>0){
data.push_back(i+min_data);
count_array[i]--;
}
}
}else{
for(int i=size-1;i>=0;--i){
while(count_array[i]>0){
data.push_back(i+min_data);
count_array[i]--;
}
}
}
}
template<typename T>
T find_max(vector<T>& data){
T rel;
if(data.size()==0){
return rel;
}
rel=data[0];
for(int i=1;i<data.size();++i){
if(data[i]>rel){
rel=data[i];
}
}
return rel;
}
template<typename T>
T find_min(vector<T>& data){
T rel;
if(data.size()==0){
return rel;
}
rel=data[0];
for(int i=1;i<data.size();++i){
if(data[i]<rel){
rel=data[i];
}
}
return rel;
}
/* 堆排序， 适用于大量数据， 可以求最大值，最小值（大顶堆小顶堆），求排前几的值
主要是堆的构建，堆的筛选排序
*/
template<typename T>
void heap_sort(vector<T>& data, int type=0){
int len = data.size();
if(len<=1){
return;
}
// 先构建堆
// 交换堆顶和最后一个元素，然后堆的数量减一，再构建堆，直到堆元素数量为1
while(len>0){
heap_build(data,len,type);
swap(data[0],data[len-1]);
len--;
}
}
/* 构建整个堆 */
template<typename T>
void heap_build(vector<T>& data,int len,bool type){
// 从最后一个父节点开始调整，也就是自底向上构建
for(int i=len/2-1;i>=0;--i){
if(!type){
max_heapify(data,i,len-1);
}else{
min_heapify(data,i,len-1);
}
}
}
/* 调整一次大顶堆 */
template<typename T>
void max_heapify(vector<T>& data, int start, int end){
int father = start;
int child = start*2+1; // start从0开始，所以要+1，若是从1开始就不用加
while(child <= end){
// 找到子节点中较大的那个
if(child+1<=end)
child = data[child]>data[child+1]?child:child+1;
// 若子节点小于父节点，返回
if(data[child]<data[father]){
return;
}else{ // 大于父节点，交换，然后处理子节点
swap(data[child],data[father]);
father = child;
child = father*2+1;
}
}
}
/* 调整一次小顶堆 */
template<typename T>
void min_heapify(vector<T>& data, int start, int end){
int father = start;
int child = start*2+1; // start从0开始，所以要+1，若是从1开始就不用加
while(child <= end){
// 找到子节点中较小的那个
if(child+1<=end)
child = data[child]<data[child+1]?child:child+1;
// 若子节点大于父节点，返回
if(data[child]>data[father]){
return;
}else{ // 小于父节点，交换，然后处理子节点
swap(data[child],data[father]);
father = child;
child = father*2+1;
}
}
}
/* 基数排序，假设以10为基数，就首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中，这样对个位排序了，然后再看十位、百位。。。只适用于正整数
*/
void radix_sort(vector<int>& data, bool type=0){
int len=data.size();
if(len<=1){
return;
}
vector<int> bucket[10]; // 假设数据够小，不会爆栈吧
// 找到最大值，看其有多少位
int max_value = find_max(data);
int max_size = 0;
while(max_value>0){
max_value/=10;
max_size++;
}
int cur_place=0;
while(cur_place<max_size){
// 比较cur_place （个十百千）位，重新排序
for(int i=0; i<len; ++i){
// pow 返回double，转成int型
int index=(data[i]/static_cast<int>(pow(10,cur_place)))%10;
bucket[index].push_back(data[i]);
}
// 重新排序
data.clear();
if(!type){
for(int i=0;i<10;++i){
for(int j=0; j<bucket[i].size();++j){
data.push_back(bucket[i][j]);
}
bucket[i].clear();
}
}else{
for(int i=9;i>=0;--i){
for(int j=bucket[i].size()-1; j>=0;--j){
data.push_back(bucket[i][j]);
}
bucket[i].clear();
}
}
cur_place++;
}
}
};
template<typename T>
void print_vector(vector<T>& data){
if(data.size()==0){
return;
}
int i=0;
for(;i<data.size()-1;++i){
cout<<data[i]<<' ';
}
cout<<data[i]<<endl;
}
/************ 冒泡排序测试 ****************/
void bubble_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"冒泡排序测试"<<endl;
vector<int> v_int1 = {1,5,2,6,3,4};
my_sort.bubble_sort(v_int1); // 从小到大
print_vector(v_int1);
vector<double> v_double1 = {1.3,5.6,2.4,6,3,3,3,4,9.6,15.3,6.4,2.1};
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.bubble_sort(v_double1,1); // 从大到小
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_double1);
double cost_time1=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time1 <<" ns"<<endl;
cout<<endl;
}
/************ 选择排序测试 ****************/
void selection_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"选择排序测试"<<endl;
vector<int> v_int2={1,5,2,6,3,4,4,4,};
my_sort.selection_sort(v_int2); // 从小到大
print_vector(v_int2);
vector<double> v_double2={1.3,5.6,2.4,6,3,3,3,4,9.6,15.3,6.4,2.1};
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.selection_sort(v_double2,1); // 从大到小
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_double2);
double cost_time2=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time2 <<" ns"<<endl;
cout<<endl;
}
/************ 插入排序测试 ****************/
void insertion_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"插入排序测试"<<endl;
vector<int> v_int3={1,5,2,6,3,4,4,4,16,89,54,23,56,45};
my_sort.insertion_sort(v_int3); // 从小到大
print_vector(v_int3);
vector<double> v_double3={1.3,5.6,2.4,6,3,3,3,4,9.6,15.3,6.4,2.1};
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.insertion_sort(v_double3,1); // 从大到小
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_double3);
double cost_time3=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time3 <<" ns"<<endl;
cout<<endl;
}
/************ 快速排序测试 ****************/
void quick_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"快速排序测试"<<endl;
vector<int> v_int4={5,4,3,2,1,56,89,78,78,78,23};
my_sort.quick_sort(v_int4); // 从小到大
print_vector(v_int4);
vector<double> v_double4={1.3,5.6,2.4,6,3,3,3,4,9.6,15.3,6.4,2.1};
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.quick_sort(v_double4,1); // 从大到小
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_double4);
double cost_time4=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time4 <<" ns"<<endl;
cout<<endl;
}
/************ 希尔排序测试 ****************/
void shell_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"希尔排序测试"<<endl;
vector<int> v_int={5,4,3,2,1,56,89,78,78,78,23};
my_sort.shell_sort(v_int); // 从小到大
print_vector(v_int);
vector<double> v_double={1.3,5.6,2.4,6,3,3,3,4,9.6,15.3,6.4,2.1};
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.shell_sort(v_double,1); // 从大到小
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_double);
double cost_time=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time <<" ns"<<endl;
cout<<endl;
}
/************ 归并排序测试 ****************/
void merge_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"归并排序测试"<<endl;
vector<int> v_int={5,4,3,2,1,56,89,78,78,78,23};
my_sort.merge_sort(v_int); // 从小到大
print_vector(v_int);
vector<double> v_double={1.3,5.6,2.4,6,3,3,3,4,9.6,15.3,6.4,2.1};
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.merge_sort(v_double,1); // 从大到小
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_double);
double cost_time=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time <<" ns"<<endl;
cout<<endl;
}
/************ 计数排序测试 ****************/
void count_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"计数排序测试"<<endl;
vector<int> v_int={5,4,3,2,1,56,89,78,78,78,23};
my_sort.count_sort(v_int); // 从小到大
print_vector(v_int);
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.count_sort(v_int,1); // 从大到小
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_int);
double cost_time=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time <<" ns"<<endl;
cout<<endl;
}
/************ 堆排序测试 ****************/
void heap_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"堆排序测试"<<endl;
vector<int> v_int={5,4,3,2,1,56,89,78,78,78,23};
my_sort.heap_sort(v_int); // 从小到大
print_vector(v_int);
vector<double> v_double={1.3,5.6,2.4,6,3,3,3,4,9.6,15.3,6.4,2.1};
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.heap_sort(v_double,1); // 从大到小
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_double);
double cost_time=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time <<" ns"<<endl;
cout<<endl;
}
/************ 基数排序测试 ****************/
void radix_test(MySortAlgorihm& my_sort){
timespec t1,t2;
cout<<"基数排序测试"<<endl;
vector<int> v_int = {5,4,3,2,1,56,89,78,78,78,23};
//v_int = {5,4,3,2,1,56,89,78,78,78,23};
clock_gettime(CLOCK_MONOTONIC,&t1);
my_sort.radix_sort(v_int); // 从小到大
clock_gettime(CLOCK_MONOTONIC,&t2);
print_vector(v_int);
my_sort.radix_sort(v_int,1); // 从大到小
print_vector(v_int);
double cost_time=(t2.tv_sec - t1.tv_sec) * 10^9 + t2.tv_nsec - t1.tv_nsec;
cout<<"所花时间："<< cost_time <<" ns"<<endl;
cout<<endl;
}
/* 简单测试 */
int main(){
MySortAlgorihm my_sort;
bubble_test(my_sort);
selection_test(my_sort);
insertion_test(my_sort);
quick_test(my_sort);
shell_test(my_sort);
merge_test(my_sort);
count_test(my_sort);
heap_test(my_sort);
radix_test(my_sort);
return 0;
}
最后更新于
这有帮助吗？