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