由于上一节学习了STL的使用,特别学习了vector的学习,所以在这里需要去回顾练习一下。下面是我的代码,我是用vector容器,实现了冒泡排序,选择排序和快速排序。特别的,在最后着重学习一个快速排序的原理。
(一):vector练习,实现几个排序算法
#include <iostream>
#include <vector>
using namespace std;
void swap(int &a,int &b);
vector<int> bubbleSort(vector<int> vec);
vector<int> selectSort(vector<int> vec);
void quickSort(vector<int> &vec,int first_lc,int last_lc);
int main() {
int size = 0;
cout << "Please enter the number of the array: ";
cin >> size;
vector<int> vec(size);
cout << "Please enter the value of the array:" <<endl;
for(int i = 0; i < size;i++){
cin >> vec[i];
}
quickSort(vec,0,size-1);
for(int i = 0;i < size;i++){
cout << vec[i] << " ";
}
cout << endl;
return 0;
}
vector<int> bubbleSort(vector<int> vec){
int size = vec.size();
for(int i = 0;i < size-1;i++){
for(int j = i;j < size-1;j++){
if(vec[j] > vec[j+1])
swap(vec[j],vec[j+1]);
}
}
return vec;
}
vector<int> selectSort(vector<int> vec){
int k = vec.size()-1;
for(int i = 0;i < vec.size();i++){
int max_lc = 0;
for(int j = 0;j <= k;j++){
if(vec[j] > vec[max_lc])
max_lc = j;
}
swap(vec[k],vec[max_lc]);
k--;
}
return vec;
}
void quickSort(vector<int> &vec,int first_lc,int last_lc){
if(first_lc >= last_lc)
return;
int i = first_lc;
int j = last_lc;
int key = vec[first_lc];
while(i < j){
while(i < j && vec[j] > key)
j--;
vec[i] = vec[j];
while(i < j && vec[i] < key)
i++;
vec[j] = vec[i];
}
vec[i] = key;
quickSort(vec,0,i-1);
quickSort(vec,i+1,last_lc);
}
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
(二):快速排序的原理
首先,快速排序采用的是分而治之的思想,在快速排序中,有三步:
1:从数组中选出一个元素,通常情况下是选择第一个元素,称为”基准”
2:将所有的比”基准”小的元素放在基准左边,比”基准大的元素”放在基准右边
3:采用递归,排序完成
下面结合一个例子去理解一下。
下面是一个数组:
1:我们需要定义两个数值:
int i = 0; //第一个元素的位置
int j = 5; //最后一个元素的位置
同时我们还需要一个变量来表示我们选择的基准值(也就是第一个元素值):
int key = array[i];
2:由于第一个元素即基准值被key取走了,所以我们需要找一个元素来取代这个位置,
我们刚刚看到,需要将小于基准值得元素放在其左边,所以,我们就需要从右向左找,
直到找到第一个小于基准值的元素,在这个例子中,在这个例子中,从右向左找一个小于
4的元素,在寻找过程中,j不断的在减小。
我们可以看到,当j=5 的时候,3 < 4的,所以此时
i = 0;
j = 5;
key = 4;
将位置5初的元素值替换位置0处的元素值。
3:此时,位置5处的数值3被空出来了,同理,由于需要将大于基准值得元素放在右边,所以我们需要
从左向右找到第一个大于4的值,就是6,此时
i = 2;
j = 5;
key = 4
进行替换:
4:此时,位置2处的6被空出来了,我们再从j位置开始,从右向左寻找第一个一个小于基准值的元素,
那就是1;
此时:
i = 2;
j = 4;
key = 4;
进行替换
5:我们接着再从i位置开始从左向右寻找第一个大于4的元素,就是7,则此时
i = 3;
j = 4;
key = 4;
进行替换:
当再继续进行的时候,从右向左再也找不到比4大的元素了,同时,从左向右再也找不到比4小的元素了,
所以,暂停一下,将基准值赋值给i所在位置的元素,即
array[i] = key;
则由此,比4小的都在4的左边了,比4大的都在4的右面了。
这样,将4的左边分离出来,4的右边分离出来,再进行上面同理的操作,最后就完成排序了。
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
版权声明:本文为博主原创文章,未经博主允许不得转载。
分享到:
相关推荐
从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件,这样就...
stl 练习 vector map iterator操作。
STL文件读写查,自己写的代码,有部分问题有待完善。而且是练习程序,所有有很多地方写的很烂,呵呵
练习: 实现生产者消费者模型 实现一个线程安全的队列 实现一个无锁队列 实现一个线程池 Go 连接数据库 Go Web 开发 Web 框架 Gin 框架 Beego 框架 Go 可视化库 Echarts C++ 攻略 STL vector list stack queue deque...
主要是STL的vector,list,stack的使用,包括优先级队列,线索链表等,还列出堆排序,最短路径等算法加以练习。
2.了解STL中一些类 vector list类的使用方法3.了解泛型算法的使用三、实验项目摘要1.练习vector和list的使用2.练习泛型算法的使用四、实
20.2.1 vector顺序容器 20.2.2 1ist顺序容器 20.2.3 deque顺序容器 20.3 关联容器 20.3.1 multiset关联容器 20. 3.2 set关联容器 20.3.3 mdtimap关联容器 20.3.4 map关联容器 20.4 容器适配器 ...
20.2.1 vector顺序容器 20.2.2 1ist顺序容器 20.2.3 deque顺序容器 20.3 关联容器 20.3.1 multiset关联容器 20. 3.2 set关联容器 20.3.3 mdtimap关联容器 20.3.4 map关联容器 20.4 容器适配器 ...
24.3 使用STL的vector·容器类 24.4 使用STL处理字符串数组 24.5 使用complex容器类处理复数数据 24.6 常犯的错误 24.7 本章重点 24.8 本章练习 第25章 最优化问题的求解 25.1 最优化问题 25.2 Simplex最...
树、图、stl:vector、stl:list、stl:map 算法 动态计划、贪婪、枚举、BFS、DFS 数学 类似于数论 给读者 大多数 cpp 文件是使用 Visual Studio IDE 创建的,其他文件是使用 Codeblocks IDE 创建的。 代码问题包含 在...
10.2.2Vector容器 90 10.2.3Deque容器 96 10.2.4stack容器 101 10.2.5Queue容器 103 10.2.6List容器 105 10.2.7优先级队列priority_queue 110 10.2.8Set和multiset容器 111 10.2.9Map和multimap容器 118 10.2.10容器...
1.4.4 vector和string 1.5 C++细节 1.5.1 指针 1.5.2 参数传递 1.5.3 返回值传递 1.5.4 引用变量 1.5.5 三大函数:析构函数、复制构造函数和operator= 1.5.6 C风格的数组和...
STL库介绍:vector, map, set等 异常处理 C++的实际应用 C++在游戏开发中的应用 C++在系统编程中的应用 C++与性能优化 学习资源与推荐 C++标准文档与参考书籍 在线学习资源与社区 实际项目练习与挑战 视频结尾: ...
1.4.4 vector和string 1.5 C++细节 1.5.1 指针 1.5.2 参数传递 1.5.3 返回值传递 1.5.4 引用变量 1.5.5 三大函数:析构函数、复制构造函数和operator= 1.5.6 C风格的...
STL算法常用函数:分隔组合:next_permutation()是检索当前范围内的划分,并重新排序为下一个替换,leetcode 556下一个元素元素III prev_permutation()是替换指定范围内的序列重新排列它重新排序为上一个序列。...
bind,这些STL库函数在算法中的妙用 , 也无法理解vector 或是 queue这些容器库的方便之处。 熟悉数据结构与算法 如果你不熟悉数据结构,那么像二叉树,BST,AVL树这些看似简单的结构都会让你头疼很久;更不用说在...
leetcode中国 2020年暑期编程练习 编程练习的题目 0、查漏补缺,将C语言基础语法必须全部学会,如下内容不需要在力扣和牛客网上寻找,请编程实现: ...STL:了解STL,学习vector和list用法,请参考下
像STL中的很多容器, vector,queue,stack,map,set等一定要比较熟悉,STL中的sort是必需要掌握的.掌握这些STL知识后写代码的时候相对于纯C会节省不少时间. C语言学习推荐:C程序设计(谭浩强编著) C++学习推荐: C++...
顺序存储:存储空间一定连续,按逻辑顺序存放,比如STL中的Array/Vector 链式存储:有线性结构(List/ForwardList/deque)和非线性结构(树) 索引存储 散列存储 一定要注意什么叫做线性结构的存储方式。线性结构是如...