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ù)組在整個(gè)遍歷過程中沒有發(fā)生交換，說明待排序數(shù)組已經(jīng)有序，此時(shí)可以直接結(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;
}解析
時(shí)間復(fù)雜度：
最好時(shí)間復(fù)雜度(有序情況)：O(n)
比較n-1次，交換0次 故最好時(shí)間復(fù)雜度為O(n)
最壞時(shí)間復(fù)雜度(逆序情況):O(n2)
第一次排序時(shí)是n個(gè)元素，比較n-1次,交換n-1次
第二次排序時(shí)是n-1個(gè)元素，比較n-2次，交換n-2次
...
第n-1次排序時(shí)是2個(gè)元素，比較1次，交換1次
第n次排序時(shí)是1個(gè)元素，比較0次，交換0次
故選擇排序時(shí)間復(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++類的大小，在C++中，結(jié)構(gòu)體和類的唯一區(qū)別就是結(jié)構(gòu)體和類具有不同的默認(rèn)訪問控制屬性，下面一起進(jìn)入文章查看詳細(xì)內(nèi)容2021-11-11
這篇文章主要介紹了QML?怎么調(diào)用?C++?中的內(nèi)容,這里主要是總結(jié)一下，怎么在 QML 文件中引用 C ++ 文件里定義的內(nèi)容，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-10-10
C++中實(shí)現(xiàn)隊(duì)列類鏈?zhǔn)酱鎯?chǔ)與棧類鏈?zhǔn)酱鎯?chǔ)的代碼示例
這篇文章主要介紹了C++中實(shí)現(xiàn)隊(duì)列類鏈?zhǔn)酱鎯?chǔ)與棧類鏈?zhǔn)酱鎯?chǔ)的代碼示例,通過注釋來說明,直接上代碼，簡單粗暴XD 需要的朋友可以參考下2016-03-03
大家好，本篇文章主要講的是C語言庫函數(shù)中qsort()的用法，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
C++實(shí)現(xiàn)PyMysql的基本功能實(shí)例詳解
這篇文章主要介紹了C++實(shí)現(xiàn)PyMysql的基本功能,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的工作或?qū)W習(xí)有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-03-03
這篇文章主要介紹了基于C語言實(shí)現(xiàn)的迷宮游戲代碼,對于學(xué)習(xí)游戲開發(fā)的朋友相信有一定的借鑒價(jià)值,需要的朋友可以參考下2014-08-08
C++實(shí)現(xiàn)順序表的常用操作(插入刪出查找輸出)
實(shí)現(xiàn)順序表的插入，刪除，查找，輸出操作在C語言中經(jīng)常用到。下面小編給大家整理實(shí)現(xiàn)代碼，一起看下吧2016-08-08
C++實(shí)現(xiàn)彩色飛機(jī)大戰(zhàn)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)彩色飛機(jī)大戰(zhàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-10-10
C/C++?Qt?數(shù)據(jù)庫與TreeView組件綁定詳解
本篇文章主要介紹了QT數(shù)據(jù)庫與View組件的綁定，通過數(shù)據(jù)庫與組件關(guān)聯(lián)可實(shí)現(xiàn)動(dòng)態(tài)展示數(shù)據(jù)庫中的表記錄。感興趣的小伙伴可以了解一下2021-12-12
這篇文章主要為大家詳細(xì)介紹了C語言中K-means算法的實(shí)現(xiàn)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02