博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数据结构基础(3) --Permutation & 插入排序
阅读量:5876 次
发布时间:2019-06-19

本文共 3403 字,大约阅读时间需要 11 分钟。

Permutation(排列组合)

排列问题:

设R = {r1, r2, ... , rn}是要进行排列的n个元素, Ri = R-{ri}; 集合X中元素的全排列记为Permutation(X), (ri)Permutation(X)表示在全排列Permutation(X)的每一个排列前加上前缀ri得到的排列.

R的全排列可归纳定义如下:

当n=1时,Permutation(R)={r},r是集合R中唯一的元素;

当n>1时,Permutation(R)由(r1)Permutation(R1),(r2)Permutation(R2), ..., (rn)Permutation(Rn)构成。

依次递归定义,则可设计产生Permutation(X)的递归算法如下:

template 
void permutation(Type *array, int front, int last){ //已经递归到了最后一个元素 if (front == last) { //打印输出 for (int i = 0; i < front; ++i) { cout << array[i] << ' '; } cout << array[front] << endl; return ; } else { for (int i = front; i <= last; ++i) { // 不断的从下标为[front ~ last]的元素中选择一个元素 //作为当前序列的开头元素 std::swap(array[front], array[i]); permutation(array, front+1, last); std::swap(array[front], array[i]); } }}

算法说明:

算法Permutation(array, k, m)递归地产生所有前缀是array[0:k-1],且后缀是array[k:m]的全排列的所有排列.函数调用(list, 0, n-1)则产生list[0:n-1]的全排列.

 

算法演示:

char str[] = “abc”;的递归调用过程如图:

小结:

虽然我们自己实现了Permutation, 但C++ STL中也实现了std::next_permutation算法, 在一般应用中, 我比较推荐使用STL中已经实现好的next_permutation, 毕竟STL的代码质量还是非常高的, 而且速度一点也不逊色于我们的实现;

 

插入排序

插入排序是低级排序中速度最快的一种(冒泡/选择/插入排序效率均为O(N^2)),但是跟快速排序(NlogN),归并排序(NlogN)还是有一定的差距的⊙﹏⊙b汗!

算法思想:

不断的从尚未排序的序列中选择一个元素插入到已经排好序的序列中(当然,会有一个选择插入位置的过程:选择一个位置, 该位置前的元素都比该元素小, 该位置后的元素都比该元素大),类似于现实生活中的斗地主的摸排过程.

//实现与解析/**说明:    outer:第一个未排序的元素    inner:搜索第一个小于tmp的元素的位置    tmp:  用于暂存第一个尚未排序的元素*/template 
void insertionSort(Type *begin, Type *end) throw (std::range_error){ if ((begin == end) || (begin == NULL) || (end == NULL)) throw std::range_error("pointer unavailable"); //假设第一个元素已经排好序了 for (Type *outer = begin+1; outer < end; ++outer) { Type tmp = *outer; //暂存第一个未排序的元素 Type *inner = outer; //inner 不断寻找一个位置(*(inner-1) <= tmp), //使得tmp->*inner(tmp所保存的值插入到inner位置) while (inner > begin && *(inner-1) > tmp) { *inner = *(inner-1); //元素后移 -- inner; //指针前移 } *inner = tmp; //将元素插入已排序序列 }}template
void insertionSort(Iter begin, Iter end){ return insertionSort(&(*begin), &(*end));}
/**insertionSort_2算法的由来:    可以使用*begin(序列的第一个元素)作为哨兵,    这样就可以省去insertionSort 中第15行的inner > begin判断,    但付出的代价是begin所指向的位置不能再存储有用的数据,    只能被用作排序的哨兵 -> 以空间换时间(个人感觉没什么必要...)*/template 
void insertionSort_2(Type *begin, Type *end) throw (std::range_error){ if ((begin == end) || (begin == NULL) || (end == NULL)) throw std::range_error("pointer unavailable"); for (Type *outer = begin+2; outer < end; ++outer) { *begin = *outer; Type *inner = outer; //因为*begin不可能 > *begin, 所以该循环一定会退出 while (*(inner-1) > *begin) { *(inner) = *(inner-1); --inner; } *inner = *begin; }}

附-permutation与std::next_permutation测试代码

int main(){    vector
str; for (char ch = 'a'; ch <= 'c'; ++ch) str.push_back(ch); permutation(&(*str.begin()), 0, 2); cout << "----------" << endl; typedef vector
::iterator Iter_type; do { for (Iter_type iter = str.begin(); iter != str.end(); ++iter) cout << *iter << ' '; cout << endl; } while (std::next_permutation(str.begin(), str.end())); return 0;}
你可能感兴趣的文章
gng3使用方法,正确的路由器防火墙安全配置方式
查看>>
VIP漂移生效时间可以用如下命令去缩短
查看>>
基于域名虚拟主机及主站迁移
查看>>
linux sed
查看>>
高可用高性能负载均衡软件HAproxy详解指南-第一章(简介、安装)
查看>>
超级碗另一面:大逆转背后,你没看到的人工智能大PK
查看>>
IntelliJ Idea 常用快捷键列表
查看>>
SQL Server 2005系列教学(3) 创建数据表
查看>>
我的书也开始赚美金
查看>>
Windows Azure Storage (9) Windows Azure 上的托管服务CDN (中) Blob Service
查看>>
Redis 中的事务
查看>>
用 Subversion 构建版本控制环境
查看>>
js24---工厂模式2
查看>>
pa/patch/115/sql 下的pls文件在EBS启动的时候会去更新数据库中的pkg ?
查看>>
Windows Mobile, Windows Embedded CE工程师的海外找工经验
查看>>
MonoRail学习笔记七:页面交互的输入输出方式总结
查看>>
项目利益相关者
查看>>
android window.requestWindowFeature()常用方法
查看>>
【Javascript Demo】移动端访问PC端网页时跳转到对应的移动端网页
查看>>
走在网页游戏开发的路上(四)
查看>>