七大排序算法之冒泡排序
@(算法筆記)[排序算法, 冒泡排序, C++實(shí)現(xiàn)]
冒泡排序介紹
冒泡排序是七大排序算法中較為簡單的一個(gè)签则，它的時(shí)間復(fù)雜度為O(n^2)汰寓，相較于快速排序卦方，它的耗時(shí)較長稍算，但是不會(huì)帶來額外的空間開銷(快速排序?qū)５男枨?江解，因此它適用于數(shù)據(jù)量較小且對時(shí)間要求不高的業(yè)務(wù)块仆，然而在實(shí)際使用過程中，幾乎遇不到這種情況惋鹅，所以冒泡排序極少被使用，但是作為一個(gè)基礎(chǔ)的入門排序算法殉簸，他的算法思想還是十分值得我們?nèi)W(xué)習(xí)的闰集。
冒泡排序核心思想
冒泡排序的思想十分簡單沽讹，它是依據(jù)氣泡在水中不斷上浮的靈感設(shè)計(jì)出來的：每次冒泡排序都是從頭到尾，依次將緊挨著的兩個(gè)數(shù)進(jìn)行比較武鲁，如果前者比后者大爽雄，就交換兩者的位置，否則不操作沐鼠，直至末尾挚瘟，比如先判斷第一個(gè)和第二個(gè)的數(shù)，如果第一個(gè)比第二個(gè)大饲梭，就將兩者交換乘盖，再接著判斷第二個(gè)和第三個(gè)，以此類推憔涉，這樣就達(dá)到了將最大的數(shù)放在最后面的效果订框，也就是將最大的數(shù)成功放在了它正確的位置上，之后再對前面的序列重復(fù)本操作兜叨，直到所有數(shù)都找到了自己正確的位置為止(正確的位置指的是排序之后它在序列中的位置)穿扳。
簡單的例子
假設(shè)待排序的序列是：
5，8国旷，4矛物，2，7
第一輪操作：
5比8小跪但，不交換：5履羞，8，4特漩，2吧雹，7
8比4大，要交換：5涂身，4雄卷，8，2蛤售，7
8比2大丁鹉，要交換：5，4悴能，2揣钦，8，7
8比7大漠酿，要交換：5冯凹，4，2炒嘲，7宇姚，8
第一輪操作結(jié)束匈庭，最后的數(shù)放在最后的位置上
第二輪操作：
5比4大，要交換：4浑劳，5阱持，2，7魔熏，8
5比2大衷咽，要交換：4，2蒜绽，5镶骗，7，8
5比7小滓窍，不交換：4卖词，2，5吏夯，7此蜈，8
第二輪操作結(jié)束，這次操作不用處理最后的8噪生，因?yàn)?已經(jīng)找到了自己的位置
第三輪操作：
4比2大裆赵，要交換：2，4跺嗽，5战授，7，8
4比5小桨嫁，不交換：2植兰，4，5璃吧，7楣导，8
第三輪操作結(jié)束
第四輪操作：
2比4小，不交換：2畜挨，4筒繁，5，7巴元，8
第四輪操作結(jié)束
冒泡排序結(jié)束
冒泡排序時(shí)間復(fù)雜度討論
顯而易見毡咏，當(dāng)待排序數(shù)列的長度為n的時(shí)候，我們需要進(jìn)行n-1次操作逮刨，第m輪操作需要判斷n-m次呕缭，因?yàn)闀r(shí)間復(fù)雜度討論的是數(shù)量級的關(guān)系，所以冒泡排序的時(shí)間復(fù)雜度為O(n^2)。
代碼
#include <iostream>
using namespace std;
void BubbleSort(int nums[],int n)
{
int temp;
for(int i=1;i<n;i++)
{
for(int j=0;j<n-i;j++)
{
if(nums[j]>nums[j+1])
{
temp=nums[j+1];
nums[j+1]=nums[j];
nums[j]=temp;
}
}
}
}
int main()
{
int nums[]={5,8,4,2,7};
BubbleSort(nums, 5);
for(int i=0;i<5;i++)
{
cout<<nums[i]<<' ';
}
cout<<endl;
}
