目录
- 主流排序算法
- stl中sort的实现
- 冒泡算法
- 优化点
- 资料
- 收获
Stl中算法组件是Function template，stl中提供了几十种算法，分为质变算法和非质变算法，主要头文件有 <algorithm> <functional> <numeric>，我们今天从排序算法开始学习实践。
主流排序算法
我们先来看下主流的排序算法有哪些？
根据时间复杂度的不同，主流的排序算法可以分为3大类
-
时间复杂度为O(n^2)的排序算法
冒泡排序
选择排序
插入排序 -
时间复杂度为O(nlogn)的排序算法
快速排序
归并排序
堆排序 -
时间复杂度为线性的排序算法
计数排序
桶排序
基数排序
Stl中使用的是时间复杂的为O(nlogn)的快速排序、堆排序以及时间复杂度为O(n^2)的插入排序。
由于自己对算法这块基础知识的掌握十分薄弱。趁此机会也把算法来学习下，今天我们就从最基础的冒泡排序开始学起。接下来几篇逐一学习其他几种排序算法，最后分析stl中sort的实现。
二、stl中sort的使用
stl的排序算法仅适用于普通数组和部分类型的容器( array、vector、deque )
sort() 函数有 2 种用法，其语法格式分别为：
//方法1: 对 [first, last) 区域内的元素做默认的升序排序,其中first 和 last 都为随机访问迭代器
void sort (RandomAccessIterator first, RandomAccessIterator last);
//方法2: 按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序，默认是升序排列，stl中也提供了std::greater<T>降序排列的函数对象
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
下面我们来实践，使用sort进行排序
#include <iostream>
#include<array>
#include<algorithm>
using namespace std;
//声明一个函数对象，用于sort的cmp
struct myclass{
bool operator()(int x,int y){return x<y;};
} mycmp;
bool cmp(int x,int y)
{
return x<y;
}
void printSortArray(int myarray[],int size){
for(int k=0; k<size; k++)
{
cout<<myarray[k]<<" ";
}
cout<<endl;
}
int main(void) {
int myarray[] ={4,3,5,9,2,7,1,8,6};
int size = sizeof(myarray)/sizeof(myarray[0]) ;
//方案1. 使用 sort (RandomAccessIterator first, RandomAccessIterator last)进行排序
//使用stl提供的算法进行排序，前闭后开区间，传递的参数是迭代器
//stl sort实现排序的平均时间复杂度为O(n*log2n)（其中 n 为指定区域 [first, last) 中 last 和 first 的距离）。
// sort(myarray,myarray+size);
//方案2. 按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
//函数进行cmp
// sort(myarray,myarray+size,cmp);
//也可以使用函数对象或者成为仿函数进行比较
// sort(myarray,myarray+size,mycmp);
sort(myarray,myarray+size,myclass());
//cpp 提供了降序排列的comp函数对象模版
// sort(myarray,myarray+size,greater<int>());
printSortArray(myarray,size);
return 0;
}
三、冒泡排序
冒泡排序是指：把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；否则 位置保持不变。
冒泡排序每一轮都要遍历所有元素，总共遍历（元素个数-1）轮，每一轮之后保证大的排在后面，时间复杂度是O(n^2)
下面我们来实践，实现冒泡排序
#include <iostream>
#include<array>
using namespace std;
void printSortArray(int i,int myarray[],int size){
cout<<"loop = " <<i+1 <<"" <<endl;
for(int k=0; k<size; k++)
{
cout<<myarray[k]<<" ";
}
cout<<endl;
}
/**
* 冒泡排序是指：
* 把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；
* 当一个元素小于等于右侧元素时，位置保持不变。
*
* @param myarray
* @param size
*/
void bubbleSort(int myarray[] ,int size){
//冒泡排序每一轮都要遍历所有元素，总共遍历（元素个数-1）轮,每一轮之后保证大的排在后面
//时间复杂度是O(n^2)
for(int i=0;i<size-1;i++)
{
for (int j = 0; j < size-i-1; j++)
{
int tmp = 0;
//如果前一个比后一个大，则交换
if(myarray[j]>myarray[j+1]){
tmp = myarray[j];
myarray[j] =myarray[j+1];
myarray[j+1] = tmp;
}
}
printSortArray(i,myarray,size);
}
}
int main(void) {
int myarray[] ={4,3,5,9,2,7,1,8,6};
int size = sizeof(myarray)/sizeof(myarray[0]) ;
cout<<"size="<<size<<endl;
bubbleSort(myarray,size);
return 0;
}
输出结果如下：
@"size=9\r\n"
@"loop = 1\r\n"
@"3 4 5 2 7 1 8 6 9 \r\n"
@"loop = 2\r\n"
@"3 4 2 5 1 7 6 8 9 \r\n"
@"loop = 3\r\n"
@"3 2 4 1 5 6 7 8 9 \r\n"
@"loop = 4\r\n"
@"2 3 1 4 5 6 7 8 9 \r\n"
@"loop = 5\r\n"
@"2 1 3 4 5 6 7 8 9 \r\n"
@"loop = 6\r\n"
@"1 2 3 4 5 6 7 8 9 \r\n"
@"loop = 7\r\n"
@"1 2 3 4 5 6 7 8 9 \r\n"
@"loop = 8\r\n"
@"1 2 3 4 5 6 7 8 9 \r\n"
可以看到 对数组进行了升序排序。同时也存在两个可优化点
- 当遍历第6轮后就已经完成了排序，但是后面依旧进行了多次遍历。
- 第3轮后 5 6 7 8 9已经是有序排列了，但是还是会执行相邻元素冒泡判断
下面小节我们这两个问题进行优化
四、冒泡排序的优化
当完成排序后，不需要再进行后续几轮的遍历。
已经完成排序的部分，不需要每次遍历是再进行比较
针对第一个问题，我们可以在每轮遍历式看看是否还有发生位置交换，如果没有即认为已经完成排序，后续几轮就可以省略了，为此加一个变量进行区分即可。
针对第二个问题，我们可以记录已经排序的头的位置，没轮遍历时，从开始对比到“有序的头位置”即可。为此也要一个变量来记录“有序的头位置”
下面我们来实践
#include <iostream>
#include<array>
#include<algorithm>
using namespace std;
void printSortArray(int i,int myarray[],int size){
cout<<"loop = " <<i+1 <<"" <<endl;
for(int k=0; k<size; k++)
{
cout<<myarray[k]<<" ";
}
cout<<endl;
}
/**
* 冒泡排序是指：
* 把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；
* 当一个元素小于等于右侧元素时，位置保持不变。
*
* @param myarray
* @param size
*/
void bubbleSort(int myarray[] ,int size){
//定义遍历sortBorder记录 有序边界的位置
int sortBorder =size-1;
for(int i=0;i<size-1;i++)
{
//加入变量hasSwap记录，当次遍历是否有发生排序交换
bool hasSwap = false;
int tmpPos = sortBorder;
cout<<"sortBorder = "<<sortBorder<<"size-i-1 ="<<size-i-1<<endl;
// for (int j = 0; j < size-i-1; j++)
for (int j = 0; j < sortBorder; j++)
{
int tmp =0;
if(myarray[j]>myarray[j+1]){
tmp = myarray[j];
myarray[j] =myarray[j+1];
myarray[j+1] = tmp;
hasSwap = true;
//如果当前位置有发生交换，则把交换后的位置记录为有序编辑的开始位置
tmpPos= j+1;
}
}
//把上一次遍历时，有序位置的起点记录，作为下一次遍历的右开边界
sortBorder = tmpPos;
printSortArray(i,myarray,size);
//如果没有排序位置交换，则认为已经完成排序，不用再后续遍历
if(!hasSwap){
break;
}
}
}
int main(void) {
int myarray[] ={3,4,2,1,5,6,7,8,9};
int size = sizeof(myarray)/sizeof(myarray[0]) ;
cout<<"size="<<size<<endl;
bubbleSort(myarray,size);
return 0;
}
冒泡排序就到这里，接下来几篇逐一学习其他几种排序算法，最后分析stl中sort的实现。一起来学习成长吧。
五、资料
《漫画算法》
《编程珠玑》
[侯捷C++ STL 体系结构与内核分析] : https://www.bilibili.com/video/BV1db411q7B8?from=search&seid=653949808386505225
[C++ STL常用算法（排序、合并、搜索和分区）] : http://c.biancheng.net/stl/algorithms/
六、收获
- 了解不同排序算法的时间复杂度
- 运用stl sort排序
- 实现冒泡排序，并做出优化。
感谢你的阅读
下一篇我们学习实践快速排序，欢迎关注公众号“音视频开发之旅”，一起学习成长。
欢迎交流
网友评论