C++排序算法之冒泡排序解析
更新時間：2023年10月31日 09:22:30 作者：大慶指針
這篇文章主要介紹了C++排序算法之冒泡排序解析,從左到右,相鄰兩數兩兩比較,若下標小的數大于下標大的數則交換,將最大的數放在數組的最后一位,,再次遍歷數組,將第二大的數,放在數組倒數第二的位置,以此類推,直到數組有序需要的朋友可以參考下
C++冒泡排序
思想
從左到右，相鄰兩數兩兩比較，若下標小的數大于下標大的數則交換，將最大的數放在數組的最后一位(即下標n-1的位置)
采用相同的方法，再次遍歷數組，將第二大的數，放在數組倒數第二的位置(即n-2的位置)，以此類推，直到數組有序
優(yōu)化：當數組在整個遍歷過程中沒有發(fā)生交換，說明待排序數組已經有序，此時可以直接結束排序過程(用bool類型變量作標記)。
代碼
#include<iostream>
#include<vector>
using namespace std;
void bubbleSort(vector<int>&vec, int n)
{
for (int j = n; j >= 1; j--)
{
bool flag = true;
for (int i = 0; i < j - 1; i++)
{
if (vec[i] > vec[i + 1])
{
swap(vec[i], vec[i + 1]);
flag = false;
}
}
if (flag) return;
}
}
int main()
{
vector<int>vec = { 2,3,5,8,9,7,4,6,1 };
bubbleSort(vec, vec.size());
for (auto it : vec)
{
cout << it << " ";
}
return 0;
}解析
時間復雜度：
最好時間復雜度(有序情況)：O(n)
比較n-1次，交換0次 故最好時間復雜度為O(n)
最壞時間復雜度(逆序情況):O(n2)
第一次排序時是n個元素，比較n-1次,交換n-1次
第二次排序時是n-1個元素，比較n-2次，交換n-2次
...
第n-1次排序時是2個元素，比較1次，交換1次
第n次排序時是1個元素，比較0次，交換0次
故選擇排序時間復雜度為O((1+2+3+...+n-1)*2)=O(n*(n-1))=O(n2)
空間復雜度：
在原數組上操作，即使用了常數級空間O(1)
到此這篇關于C++排序算法之冒泡排序解析的文章就介紹到這了,更多相關C++冒泡排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
C++的繼承機制相對其他語言是比較復雜的一種，不同于java只支持單繼承，C++不僅支持單繼承，也支持多繼承。本文將詳細講解C++中單繼承與多繼承的使用，需要的可以參考一下2022-04-04
折線圖目前應用最廣的也是用來繪制各種軌跡，折線圖其實就是后面動態(tài)軌跡圖、飛機航線圖的前身，公用的一個方法addPolyline。本文將教大家如何通過QT實現覆蓋物折線圖，快來學習吧2021-12-12
本篇文章是對使用Inotify 監(jiān)控目錄與文件的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
QTreeView,顧名思義,就是一種樹形的控件,在我們需要做類似于文件列表的視圖時,是一個不錯的選擇,下面我們就來看看qt如何重寫QTreeView實現酷炫樣式,感興趣的可以了解一下2023-08-08
這篇文章主要為大家詳細介紹了用C語言簡單實現掃雷小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要為大家詳細介紹了C++引用變量時那些你不知道的東西——引用變量延遲綁定，文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2022-11-11
今天小編就為大家分享一篇關于C++小知識:C/C++中不要按值傳遞數組，小編覺得內容挺不錯的，現在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
IOS開發(fā)之UIScrollView實現圖片輪播器的無限滾動
這篇文章主要介紹了IOS開發(fā)之UIScrollView實現圖片輪播器的無限滾動的相關資料,需要的朋友可以參考下2017-07-07
C語言中,字符串是以'\0'結尾的一些字符的集合,為了操作方便,C標準庫中提供了一些str系列的庫函數,但是這些庫函數和字符串是分離的,本文給大家介紹了C++ string字符串的使用和簡單模擬實現,感興趣的朋友可以參考下2024-06-06
這篇文章主要給大家介紹了關于c++stack與queue模擬實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面跟著小編來一起學習學習吧2021-08-08