`
hongbochen1223
  • 浏览: 43277 次
文章分类
社区版块
存档分类
最新评论

STL vector练习

 
阅读更多

由于上一节学习了STL的使用,特别学习了vector的学习,所以在这里需要去回顾练习一下。下面是我的代码,我是用vector容器,实现了冒泡排序,选择排序和快速排序。特别的,在最后着重学习一个快速排序的原理。

(一):vector练习,实现几个排序算法

//================================
// Name        : VectorTest.cpp
// Author      : hongboChen
// Version     :
// Copyright   : Your copyright notice
// Description : 由于上一节学习使用了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() {

 //用于保存vector的大小
 int size = 0;

 cout << "Please enter the number of the array: ";
 cin >> size;

 //新建一个vector对象,并设置其大小
 vector<int> vec(size);

 //获取vector的遍历器
 //vector<int>::iterator it = vec.begin();

 //获取用户输入的数值,并赋值给vector
 cout << "Please enter the value of the array:" <<endl;

 for(int i = 0; i < size;i++){
  cin >> vec[i];
  //或者是
  //cin >> vec.at(i);
  //或者是
  //it += i;
  //cin >> *it;
 }

 //下面就是对数组进行排序
 //冒泡排序
 //vec = bubbleSort(vec);

 //选择排序
 //vec = selectSort(vec);

 //快速排序
 quickSort(vec,0,size-1);

 for(int i = 0;i < size;i++){
  cout << vec[i] << "   ";
 }

 cout << endl;

 return 0;
}

//最简单的就是冒泡排序
/**
 * 冒泡排序的思想就是
 * 每次循环的时候都是找相邻的两个元素
 * 如果相邻的两个元素符合顺序要求,就i不必切换位置
 * 如果相邻的两个元素不符合顺序要求,就将这两个元素的位置对换
 */
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;
}

/**
 *  快速排序思想:算法复杂度为O(nlog(n))
 *
 *  1:从数组中选出一个元素,通常情况下是选择第一个元素,称为"基准"
 *  2:将所有的比"基准"小的元素放在基准左边,比"基准大的元素"放在基准右边
 *  3:采用递归,排序完成
 */
/**
 * vec   :  要排序的数组
 * first_lc  :  第一个元素的位置
 * last_lc   :  最后一个元素的位置
 *
 */
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库介绍与练习

    从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件,这样就...

    stl练习资料

    stl 练习 vector map iterator操作。

    STL文件读写查

    STL文件读写查,自己写的代码,有部分问题有待完善。而且是练习程序,所有有很多地方写的很烂,呵呵

    go-web:后端开发指南(笔记)

    练习: 实现生产者消费者模型 实现一个线程安全的队列 实现一个无锁队列 实现一个线程池 Go 连接数据库 Go Web 开发 Web 框架 Gin 框架 Beego 框架 Go 可视化库 Echarts C++ 攻略 STL vector list stack queue deque...

    常用数据结构

    主要是STL的vector,list,stack的使用,包括优先级队列,线索链表等,还列出堆排序,最短路径等算法加以练习。

    程序设计个人实验报告1

    2.了解STL中一些类 vector list类的使用方法3.了解泛型算法的使用三、实验项目摘要1.练习vector和list的使用2.练习泛型算法的使用四、实

    C++大学教程,一本适合初学者的入门教材(part2)

    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 容器适配器 ...

    C++大学教程,一本适合初学者的入门教材(part1)

    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 容器适配器 ...

    C++程序设计彻底研究(是code不是书)

    24.3 使用STL的vector·容器类 24.4 使用STL处理字符串数组 24.5 使用complex容器类处理复数数据 24.6 常犯的错误 24.7 本章重点 24.8 本章练习 第25章 最优化问题的求解 25.1 最优化问题 25.2 Simplex最...

    leetcode和oj-OJ_exercise:今年,作者被清华大学软件学院录取。这里是JIKAO编码练习

    树、图、stl:vector、stl:list、stl:map 算法 动态计划、贪婪、枚举、BFS、DFS 数学 类似于数论 给读者 大多数 cpp 文件是使用 Visual Studio IDE 创建的,其他文件是使用 Codeblocks IDE 创建的。 代码问题包含 在...

    C++进阶课程讲义_v1.0.4.pdf

    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容器...

    数据结构与算法分析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风格的数组和...

    第一章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风格的...

    LeetCode:LeetCode练习

    STL算法常用函数:分隔组合:next_permutation()是检索当前范围内的划分,并重新排序为下一个替换,leetcode 556下一个元素元素III prev_permutation()是替换指定范围内的序列重新排列它重新排序为上一个序列。...

    leetcode题库-LeetCode:leetcode练习集合(分专题练习)

    bind,这些STL库函数在算法中的妙用 , 也无法理解vector 或是 queue这些容器库的方便之处。 熟悉数据结构与算法 如果你不熟悉数据结构,那么像二叉树,BST,AVL树这些看似简单的结构都会让你头疼很久;更不用说在...

    leetcode中国-Programing-practice-of-summer-vacation-in-2020:2020年暑假编程实践

    leetcode中国 2020年暑期编程练习 编程练习的题目 0、查漏补缺,将C语言基础语法必须全部学会,如下内容不需要在力扣和牛客网上寻找,请编程实现: ...STL:了解STL,学习vector和list用法,请参考下

    如何学习ACM,看后受益匪浅

    像STL中的很多容器, vector,queue,stack,map,set等一定要比较熟悉,STL中的sort是必需要掌握的.掌握这些STL知识后写代码的时候相对于纯C会节省不少时间. C语言学习推荐:C程序设计(谭浩强编著) C++学习推荐: C++...

    leetcode叫数-DataStructure:常见数据结构C++(leetcode/牛客)

    顺序存储:存储空间一定连续,按逻辑顺序存放,比如STL中的Array/Vector 链式存储:有线性结构(List/ForwardList/deque)和非线性结构(树) 索引存储 散列存储 一定要注意什么叫做线性结构的存储方式。线性结构是如...

Global site tag (gtag.js) - Google Analytics