C++基础语法十大排序算法后五个分享
本期是c++基础语法分享的第十六节，今天给大家来梳理一下十大排序算法后五个！
归并排序
归并排序：把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。
/***************** 迭代版*****************
///整數或浮點數皆可使用，若要使用物件（class）時必須設定“小於”（《）的運算子功能template《typename t》void merge_sort（t arr［］， int len） { t* a = arr;
t* b = new t［len］; for （int seg = 1;
seg 《 len; seg += seg） { for （int start = 0; start 《 len; start += seg + seg） { int low = start， mid = min（start + seg， len）， high = min（start + seg + seg， len）;
int k = low; int start1 = low， end1 = mid; int start2 = mid， end2 = high; while （start1 《 end1 && start2 《 end2） b［k++］ = a［start1］ 《 a［start2］ ？ a［start1++］ ： a［start2++］; while （start1 《 end1） b［k++］ = a［start1++］;
while （start2 《 end2） b［k++］ = a［start2++］; } t* temp = a;
a = b; b = temp; } if （a ！= arr） { for （int i = 0; i 《 len; i++） b［i］ = a［i］; b = a;
} delete［］ b;}
/***************** 递归版*****************/template《typename t》void merge_sort_recursive（t arr［］， t reg［］， int start， int end） { if （start 》= end） return; int len = end - start， mid = （len 》》 1） + start; int start1 = start， end1 = mid;
int start2 = mid + 1， end2 = end; merge_sort_recursive（arr， reg， start1， end1）; merge_sort_recursive（arr， reg， start2， end2）;
int k = start; while （start1 《= end1 && start2 《= end2） reg［k++］ = arr［start1］ 《 arr［start2］ ？ arr［start1++］ ： arr［start2++］;
while （start1 《= end1） reg［k++］ = arr［start1++］; while （start2 《= end2） reg［k++］ = arr［start2++］;
for （k = start; k 《= end; k++） arr［k］ = reg［k］;}//整數或浮點數皆可使用，若要使用物件（class）時必須設定“小於”（《）的運算子功能template《typename t》 void merge_sort（t arr［］， const int len） { t *reg = new t［len］; merge_sort_recursive（arr， reg， 0， len - 1）; delete［］ reg;}
希尔排序
希尔排序：每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是1。
template《typename t》void shell_sort（t array［］， int length） { int h = 1; while （h 《 length / 3） { h = 3 * h + 1; } while （h 》= 1） { for （int i = h; i 《 length; i++） { for （int j = i; j 》= h && array［j］ 《 array［j - h］; j -= h） { std：：swap（array［j］， array［j - h］）; } } h = h / 3; }}
计数排序
计数排序：统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。
计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。
如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。
计数排序不是比较排序，排序的速度快于任何比较排序算法。
时间复杂度为 o（n+k），空间复杂度为 o（n+k）
算法的步骤如下：
1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 c 的第 i 项
3. 对所有的计数累加（从 c 中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素 i 放在新数组的第 c［i］ 项，每放一个元素就将 c［i］ 减去 1
#include 《iostream》#include 《vector》#include 《algorithm》
using namespace std;
// 计数排序void countsort（vector《int》& vecraw， vector《int》& vecobj）{ // 确保待排序容器非空 if （vecraw.size（） == 0） return;
// 使用 vecraw 的最大值 + 1 作为计数容器 countvec 的大小 int veccountlength = （*max_element（begin（vecraw）， end（vecraw））） + 1; vector《int》 veccount（veccountlength， 0）;
// 统计每个键值出现的次数 for （int i = 0; i 《 vecraw.size（）; i++） veccount［vecraw［i］］++; // 后面的键值出现的位置为前面所有键值出现的次数之和 for （int i = 1; i 《 veccountlength; i++） veccount［i］ += veccount［i - 1］;
// 将键值放到目标位置 for （int i = vecraw.size（）; i 》 0; i--） // 此处逆序是为了保持相同键值的稳定性 vecobj［--veccount［vecraw［i - 1］］］ = vecraw［i - 1］;}
int main（）{ vector《int》 vecraw = { 0，5，7，9，6，3，4，5，2，8，6，9，2，1 }; vector《int》 vecobj（vecraw.size（）， 0）;
countsort（vecraw， vecobj）;
for （int i = 0; i 《 vecobj.size（）; ++i） cout 《《 vecobj［i］ 《《 “ ”; cout 《《 endl;
return 0;}
桶排序
桶排序：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
桶排序序思路：
1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。
假设数据分布在［0，100）之间，每个桶内部用链表表示，在数据入桶的同时插入排序，然后把各个桶中的数据合并。
const int bucket_num = 10;
struct listnode{ explicit listnode（int i=0）：mdata（i），mnext（null）{} listnode* mnext; int mdata;};
listnode* insert（listnode* head，int val）{ listnode dummynode; listnode *newnode = new listnode（val）; listnode *pre，*curr; dummynode.mnext = head; pre = &dummynode; curr = head; while（null！=curr && curr-》mdata《=val）{ pre = curr; curr = curr-》mnext; } newnode-》mnext = curr; pre-》mnext = newnode; return dummynode.mnext;}
listnode* merge（listnode *head1，listnode *head2）{ listnode dummynode; listnode *dummy = &dummynode; while（null！=head1 && null！=head2）{ if（head1-》mdata 《= head2-》mdata）{ dummy-》mnext = head1; head1 = head1-》mnext; }else{ dummy-》mnext = head2; head2 = head2-》mnext; } dummy = dummy-》mnext; } if（null！=head1） dummy-》mnext = head1; if（null！=head2） dummy-》mnext = head2; return dummynode.mnext;}
void bucketsort（int n，int arr［］）{ vector《listnode*》 buckets（bucket_num，（listnode*）（0））; for（int i=0;i《n;++i）{ int index = arr［i］/bucket_num; listnode *head = buckets.at（index）; buckets.at（index） = insert（head，arr［i］）; } listnode *head = buckets.at（0）; for（int i=1;i《bucket_num;++i）{ head = merge（head，buckets.at（i））; } for（int i=0;i《n;++i）{ arr［i］ = head-》mdata; head = head-》mnext; }}
基数排序
基数排序：一种多关键字的排序算法，可用桶排序实现。
int maxbit（int data［］， int n） //辅助函数，求数据的最大位数{ int maxdata = data［0］; ///《 最大数 /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。 for （int i = 1; i 《 n; ++i） { if （maxdata 《 data［i］） maxdata = data［i］;
} int d = 1;
int p = 10; while （maxdata 》= p） { //p *= 10; // maybe overflow maxdata /= 10; ++d; } return d;/* int d = 1; //保存最大的位数 int p = 10; for（int i = 0; i 《 n; ++i） { while（data［i］ 》= p） { p *= 10; ++d;
} } return d;*/}void radixsort（int data［］， int n） //基数排序{ int d = maxbit（data， n）;
int *tmp = new int［n］; int *count = new int［10］;
//计数器 int i， j， k; int radix = 1; for（i = 1; i 《= d; i++） //进行d次排序 { for（j = 0; j 《 10; j++） count［j］ = 0; //每次分配前清空计数器 for（j = 0; j 《 n; j++） { k = （data［j］ / radix） % 10; //统计每个桶中的记录数 count［k］++; } for（j = 1; j 《 10; j++） count［j］ = count［j - 1］ + count［j］;
//将tmp中的位置依次分配给每个桶 for（j = n - 1; j 》= 0; j--） //将所有桶中记录依次收集到tmp中 { k = （data［j］ / radix） % 10; tmp［count［k］ - 1］ = data［j］;
count［k］--; } for（j = 0; j 《 n; j++） //将临时数组的内容复制到data中 data［j］ = tmp［j］; radix = radix * 10;
} delete ［］tmp; delete ［］count;}
今天的分享就到这里了，大家要好好学c++哟~
焊接机器人工作站的组成部分有哪些
plc常用功能指令 典型的plc功能有哪些
BAT工程师有哪些成长阶段
羽毛球冠军戴资颖代言夏普 Aquos S3 全面屏搭配骁龙处理器
SX1278/SX1276/SX1272中文规格书
C++基础语法十大排序算法后五个分享
迅为2K1000龙芯开发板-pmon 下常用命令
为军事应用提供小型嵌入式计算案例
家电全渠道占比行业第一 亿台空调里程碑见证霸主地位
人工成本高企？华为云耀云服务器 L 实例打通企业网站开发最后堵着
华为小米等国产厂商发力 三星Q3中国市场份额降至2%
第四季度三星的DRAM和NAND芯片发货量增长约10%
电子芯闻早报：IBM推新服务器架构 小米Note2双曲面屏
关于SMT贴片中锡膏该如何选择？
俄罗斯明年开始生产***
CS5350/CS5328太阳能板供电铅酸蓄电池、磷酸铁锂电池、锂电池充电管理IC系列
LCD的三种广视角技术：IPS、MVA、TN+FILM
CV迎来GPT-3时刻：Meta开源“万物可分割AI”模型
史上最贵机器人1.2亿？可真人驾驶的机器人战士
“AI赋能”第二届国际摄像头技术应用大会圆满落幕
归并排序
归并排序：把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。
/***************** 迭代版*****************
///整數或浮點數皆可使用，若要使用物件（class）時必須設定“小於”（《）的運算子功能template《typename t》void merge_sort（t arr［］， int len） { t* a = arr;
t* b = new t［len］; for （int seg = 1;
seg 《 len; seg += seg） { for （int start = 0; start 《 len; start += seg + seg） { int low = start， mid = min（start + seg， len）， high = min（start + seg + seg， len）;
int k = low; int start1 = low， end1 = mid; int start2 = mid， end2 = high; while （start1 《 end1 && start2 《 end2） b［k++］ = a［start1］ 《 a［start2］ ？ a［start1++］ ： a［start2++］; while （start1 《 end1） b［k++］ = a［start1++］;
while （start2 《 end2） b［k++］ = a［start2++］; } t* temp = a;
a = b; b = temp; } if （a ！= arr） { for （int i = 0; i 《 len; i++） b［i］ = a［i］; b = a;
} delete［］ b;}
/***************** 递归版*****************/template《typename t》void merge_sort_recursive（t arr［］， t reg［］， int start， int end） { if （start 》= end） return; int len = end - start， mid = （len 》》 1） + start; int start1 = start， end1 = mid;
int start2 = mid + 1， end2 = end; merge_sort_recursive（arr， reg， start1， end1）; merge_sort_recursive（arr， reg， start2， end2）;
int k = start; while （start1 《= end1 && start2 《= end2） reg［k++］ = arr［start1］ 《 arr［start2］ ？ arr［start1++］ ： arr［start2++］;
while （start1 《= end1） reg［k++］ = arr［start1++］; while （start2 《= end2） reg［k++］ = arr［start2++］;
for （k = start; k 《= end; k++） arr［k］ = reg［k］;}//整數或浮點數皆可使用，若要使用物件（class）時必須設定“小於”（《）的運算子功能template《typename t》 void merge_sort（t arr［］， const int len） { t *reg = new t［len］; merge_sort_recursive（arr， reg， 0， len - 1）; delete［］ reg;}
希尔排序
希尔排序：每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是1。
template《typename t》void shell_sort（t array［］， int length） { int h = 1; while （h 《 length / 3） { h = 3 * h + 1; } while （h 》= 1） { for （int i = h; i 《 length; i++） { for （int j = i; j 》= h && array［j］ 《 array［j - h］; j -= h） { std：：swap（array［j］， array［j - h］）; } } h = h / 3; }}
计数排序
计数排序：统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。
计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。
如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。
计数排序不是比较排序，排序的速度快于任何比较排序算法。
时间复杂度为 o（n+k），空间复杂度为 o（n+k）
算法的步骤如下：
1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 c 的第 i 项
3. 对所有的计数累加（从 c 中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素 i 放在新数组的第 c［i］ 项，每放一个元素就将 c［i］ 减去 1
#include 《iostream》#include 《vector》#include 《algorithm》
using namespace std;
// 计数排序void countsort（vector《int》& vecraw， vector《int》& vecobj）{ // 确保待排序容器非空 if （vecraw.size（） == 0） return;
// 使用 vecraw 的最大值 + 1 作为计数容器 countvec 的大小 int veccountlength = （*max_element（begin（vecraw）， end（vecraw））） + 1; vector《int》 veccount（veccountlength， 0）;
// 统计每个键值出现的次数 for （int i = 0; i 《 vecraw.size（）; i++） veccount［vecraw［i］］++; // 后面的键值出现的位置为前面所有键值出现的次数之和 for （int i = 1; i 《 veccountlength; i++） veccount［i］ += veccount［i - 1］;
// 将键值放到目标位置 for （int i = vecraw.size（）; i 》 0; i--） // 此处逆序是为了保持相同键值的稳定性 vecobj［--veccount［vecraw［i - 1］］］ = vecraw［i - 1］;}
int main（）{ vector《int》 vecraw = { 0，5，7，9，6，3，4，5，2，8，6，9，2，1 }; vector《int》 vecobj（vecraw.size（）， 0）;
countsort（vecraw， vecobj）;
for （int i = 0; i 《 vecobj.size（）; ++i） cout 《《 vecobj［i］ 《《 “ ”; cout 《《 endl;
return 0;}
桶排序
桶排序：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
桶排序序思路：
1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。
假设数据分布在［0，100）之间，每个桶内部用链表表示，在数据入桶的同时插入排序，然后把各个桶中的数据合并。
const int bucket_num = 10;
struct listnode{ explicit listnode（int i=0）：mdata（i），mnext（null）{} listnode* mnext; int mdata;};
listnode* insert（listnode* head，int val）{ listnode dummynode; listnode *newnode = new listnode（val）; listnode *pre，*curr; dummynode.mnext = head; pre = &dummynode; curr = head; while（null！=curr && curr-》mdata《=val）{ pre = curr; curr = curr-》mnext; } newnode-》mnext = curr; pre-》mnext = newnode; return dummynode.mnext;}
listnode* merge（listnode *head1，listnode *head2）{ listnode dummynode; listnode *dummy = &dummynode; while（null！=head1 && null！=head2）{ if（head1-》mdata 《= head2-》mdata）{ dummy-》mnext = head1; head1 = head1-》mnext; }else{ dummy-》mnext = head2; head2 = head2-》mnext; } dummy = dummy-》mnext; } if（null！=head1） dummy-》mnext = head1; if（null！=head2） dummy-》mnext = head2; return dummynode.mnext;}
void bucketsort（int n，int arr［］）{ vector《listnode*》 buckets（bucket_num，（listnode*）（0））; for（int i=0;i《n;++i）{ int index = arr［i］/bucket_num; listnode *head = buckets.at（index）; buckets.at（index） = insert（head，arr［i］）; } listnode *head = buckets.at（0）; for（int i=1;i《bucket_num;++i）{ head = merge（head，buckets.at（i））; } for（int i=0;i《n;++i）{ arr［i］ = head-》mdata; head = head-》mnext; }}
基数排序
基数排序：一种多关键字的排序算法，可用桶排序实现。
int maxbit（int data［］， int n） //辅助函数，求数据的最大位数{ int maxdata = data［0］; ///《 最大数 /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。 for （int i = 1; i 《 n; ++i） { if （maxdata 《 data［i］） maxdata = data［i］;
} int d = 1;
int p = 10; while （maxdata 》= p） { //p *= 10; // maybe overflow maxdata /= 10; ++d; } return d;/* int d = 1; //保存最大的位数 int p = 10; for（int i = 0; i 《 n; ++i） { while（data［i］ 》= p） { p *= 10; ++d;
} } return d;*/}void radixsort（int data［］， int n） //基数排序{ int d = maxbit（data， n）;
int *tmp = new int［n］; int *count = new int［10］;
//计数器 int i， j， k; int radix = 1; for（i = 1; i 《= d; i++） //进行d次排序 { for（j = 0; j 《 10; j++） count［j］ = 0; //每次分配前清空计数器 for（j = 0; j 《 n; j++） { k = （data［j］ / radix） % 10; //统计每个桶中的记录数 count［k］++; } for（j = 1; j 《 10; j++） count［j］ = count［j - 1］ + count［j］;
//将tmp中的位置依次分配给每个桶 for（j = n - 1; j 》= 0; j--） //将所有桶中记录依次收集到tmp中 { k = （data［j］ / radix） % 10; tmp［count［k］ - 1］ = data［j］;
count［k］--; } for（j = 0; j 《 n; j++） //将临时数组的内容复制到data中 data［j］ = tmp［j］; radix = radix * 10;
} delete ［］tmp; delete ［］count;}
今天的分享就到这里了，大家要好好学c++哟~
焊接机器人工作站的组成部分有哪些
plc常用功能指令 典型的plc功能有哪些
BAT工程师有哪些成长阶段
羽毛球冠军戴资颖代言夏普 Aquos S3 全面屏搭配骁龙处理器
SX1278/SX1276/SX1272中文规格书
C++基础语法十大排序算法后五个分享
迅为2K1000龙芯开发板-pmon 下常用命令
为军事应用提供小型嵌入式计算案例
家电全渠道占比行业第一 亿台空调里程碑见证霸主地位
人工成本高企？华为云耀云服务器 L 实例打通企业网站开发最后堵着
华为小米等国产厂商发力 三星Q3中国市场份额降至2%
第四季度三星的DRAM和NAND芯片发货量增长约10%
电子芯闻早报：IBM推新服务器架构 小米Note2双曲面屏
关于SMT贴片中锡膏该如何选择？
俄罗斯明年开始生产***
CS5350/CS5328太阳能板供电铅酸蓄电池、磷酸铁锂电池、锂电池充电管理IC系列
LCD的三种广视角技术：IPS、MVA、TN+FILM
CV迎来GPT-3时刻：Meta开源“万物可分割AI”模型
史上最贵机器人1.2亿？可真人驾驶的机器人战士
“AI赋能”第二届国际摄像头技术应用大会圆满落幕