選擇排序和冒泡排序

冒泡排序

算法思路

每次冒泡操作都會(huì)對(duì)相鄰的兩個(gè)元素進(jìn)行比較,看是否滿(mǎn)足大小關(guān)系要求。如果不滿(mǎn)足就讓它倆互換妒茬。
一次冒泡會(huì)讓至少一個(gè)元素移動(dòng)到它應(yīng)該在的位置,重復(fù) n 次蔚晨,就完成了 n 個(gè)數(shù)據(jù)的排序工作乍钻。

第一次冒泡操作.png

經(jīng)過(guò)一次冒泡操作之后,6 這個(gè)元素已經(jīng)存儲(chǔ)在正確的位置上铭腕。要想完成所有數(shù)據(jù)的排序银择,我們只要進(jìn)行 6 次這樣的冒泡操作就行了。

image.png
void bubleSort(vector<int>& vec) 
{
    for (int i = 0; i < vec.size(); i++)  
    {
        // 提前退出冒泡循環(huán)的標(biāo)志位
        bool flag = false;           
        for (int j = 0; j < vec.size() - i - 1; ++j) 
        {
            if (vec[j] > vec[j+1]) 
            {
                swap(vec[j], vec[j+1]);
                flag = true;
            }
        }
        if (!flag)  break;   // 掃描一趟沒(méi)有發(fā)生交換時(shí)累舷,說(shuō)明當(dāng)前索引右邊元素已經(jīng)有序浩考。
     }
 }
特點(diǎn)
  • 冒泡排序是原地排序算法嗎?
    冒泡的過(guò)程只涉及相鄰數(shù)據(jù)的交換操作被盈,只需要常量級(jí)的臨時(shí)空間析孽,所以它的空間復(fù)雜度為 O(1),是一個(gè)原地排序算法害捕。

  • 冒泡排序是穩(wěn)定的排序算法嗎绿淋?
    冒泡排序中闷畸,只有交換才可以改變兩個(gè)元素的前后順序尝盼。為了保證冒泡排序算法的穩(wěn)定性,當(dāng)有相鄰的兩個(gè)元素大小相等的時(shí)候佑菩,我們不做交換盾沫,相同大小的數(shù)據(jù)在排序前后不會(huì)改變順序,所以冒泡排序是穩(wěn)定的排序算法殿漠。

  • 冒泡排序算法的時(shí)間復(fù)雜度是多少赴精?

    • 若序列是有序的,則只需要一趟掃描就可以結(jié)束绞幌,此時(shí)蕾哟,比較次數(shù)為n-1,移動(dòng)次數(shù)也為0莲蜘,此時(shí)情況最好谭确。

    • 若序列是逆序的,則需要比較n(n-1)/2票渠,交換n(n-1)/2逐哈。此時(shí)情況最差。

      image.png
    平均時(shí)間 最差 最佳 輔助空間 穩(wěn)定性
    O(n^2) O(n^2) O(n) O(1) 穩(wěn)定

選擇排序

算法思路

選擇排序會(huì)將整個(gè)數(shù)組分為已排序區(qū)間和未排序區(qū)間问顷,每次會(huì)從未排序區(qū)間中找到最小的元素昂秃,將其放到已排序區(qū)間的末尾禀梳。

image.png
void selectSort(vector<int> &vec)  
{
    for (int i = 0; i < vec.size(); i++) 
    {
        int minIndex = i;
        for (int j = i+1; j < vec.size(); j++)
        {
            if (vec[j] < vec[minIndex]) 
            {
                minIndex = j;
                swap(vec[i], vec[minIndex]);
             }
        }
    }
}
特點(diǎn)
  • 選擇排序是原地排序算法嗎?
    選擇排序空間復(fù)雜度為 O(1)肠骆,是一種原地排序算法算途。

  • 選擇排序是穩(wěn)定的排序算法嗎?
    選擇排序是一種不穩(wěn)定的排序算法哗戈,選擇排序每次都要找剩余未排序元素中的最小值郊艘,并和前面的元素交換位置,這樣破壞了穩(wěn)定性唯咬。
    比如 5纱注,8,5胆胰,2狞贱,9 這樣一組數(shù)據(jù),使用選擇排序算法來(lái)排序的話(huà)蜀涨,第一次找到最小元素 2瞎嬉,與第一個(gè) 5 交換位置,那第一個(gè) 5 和中間的 5 順序就變了厚柳,所以就不穩(wěn)定了氧枣。

  • 選擇排序算法的時(shí)間復(fù)雜度是多少?
    選擇排序有2個(gè)鮮明特點(diǎn):

    • 運(yùn)行時(shí)間和輸入無(wú)關(guān)别垮,對(duì)于長(zhǎng)度為N的數(shù)組便监,選擇排序需要N(N-1)/2次比較和N次交換
    • 數(shù)據(jù)移動(dòng)最少,選擇排序用了N次交換碳想,交換次數(shù)和數(shù)組大小是線(xiàn)性關(guān)系烧董。其他任何算法不具備這個(gè)特征,大部分都是線(xiàn)性對(duì)數(shù)或者平方胧奔。
    平均時(shí)間 最差 最佳 輔助空間 穩(wěn)定性
    O(n^2) O(n^2) O(n^2) O(1) 不穩(wěn)定
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末逊移,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子龙填,更是在濱河造成了極大的恐慌胳泉,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件岩遗,死亡現(xiàn)場(chǎng)離奇詭異扇商,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)喘先,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)钳吟,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人窘拯,你說(shuō)我怎么就攤上這事红且“泳ィ” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵暇番,是天一觀的道長(zhǎng)嗤放。 經(jīng)常有香客問(wèn)我,道長(zhǎng)壁酬,這世上最難降的妖魔是什么次酌? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮舆乔,結(jié)果婚禮上岳服,老公的妹妹穿的比我還像新娘。我一直安慰自己希俩,他們只是感情好吊宋,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著颜武,像睡著了一般璃搜。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上鳞上,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天这吻,我揣著相機(jī)與錄音,去河邊找鬼篙议。 笑死唾糯,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的涡上。 我是一名探鬼主播趾断,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼拒名,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼吩愧!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起增显,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤雁佳,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后同云,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體糖权,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年炸站,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了星澳。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡旱易,死狀恐怖禁偎,靈堂內(nèi)的尸體忽然破棺而出腿堤,到底是詐尸還是另有隱情,我是刑警寧澤如暖,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布笆檀,位于F島的核電站,受9級(jí)特大地震影響盒至,放射性物質(zhì)發(fā)生泄漏酗洒。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一枷遂、第九天 我趴在偏房一處隱蔽的房頂上張望樱衷。 院中可真熱鬧,春花似錦酒唉、人聲如沸箫老。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)耍鬓。三九已至,卻和暖如春流妻,著一層夾襖步出監(jiān)牢的瞬間牲蜀,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工绅这, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留涣达,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓证薇,卻偏偏與公主長(zhǎng)得像度苔,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子浑度,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問(wèn)題, 分享了一些自己做題目的經(jīng)驗(yàn)寇窑。 張土汪:刷leetcod...
    土汪閱讀 12,748評(píng)論 0 33
  • 總結(jié)一下常見(jiàn)的排序算法。 排序分內(nèi)排序和外排序箩张。內(nèi)排序:指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序甩骏。外排序:指在排序...
    jiangliang閱讀 1,354評(píng)論 0 1
  • 剛開(kāi)始學(xué)習(xí)Java,大家都會(huì)學(xué)習(xí)排序算法先慷,但是只有理解了排序的方法饮笛,才能更好的將其轉(zhuǎn)換為代碼。剛開(kāi)始學(xué)習(xí)我也為了理...
    朽木丿碎風(fēng)閱讀 508評(píng)論 1 1
  • 想來(lái)你看見(jiàn)這個(gè)題目會(huì)很不滿(mǎn)意论熙。我們的白素貞阿福青,白娘子阿,每天里里外外的忙碌,張羅著給人看病无午,藥鋪的生意經(jīng)營(yíng)的紅紅...
    君子既來(lái)云胡不喜閱讀 342評(píng)論 0 1
  • 記不清是哪一天了二蓝,只記得大約一個(gè)月前的某天,無(wú)意間和小姐妹說(shuō)到了運(yùn)動(dòng)指厌,她問(wèn)我有沒(méi)有加入微信運(yùn)動(dòng)刊愚,我說(shuō):“微信運(yùn)動(dòng)是...
    竺亦心閱讀 592評(píng)論 3 2