建站
咨詢
售后
建站咨詢
新聞中心
[[427403]]
本文轉(zhuǎn)載自微信公眾號(hào)「JS每日一題」，作者灰灰 。轉(zhuǎn)載本文請(qǐng)聯(lián)系JS每日一題公眾號(hào)。
創(chuàng)新互聯(lián)是專業(yè)的南昌縣網(wǎng)站建設(shè)公司，南昌縣接單;提供成都網(wǎng)站制作、成都網(wǎng)站建設(shè),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行南昌縣網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!
一、是什么
冒泡排序(Bubble Sort)，是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法
冒泡排序的思想就是在每次遍歷一遍未排序的數(shù)列之后，將一個(gè)數(shù)據(jù)元素浮上去(也就是排好了一個(gè)數(shù)據(jù))
如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣，故名“冒泡排序”
假如我們要把 12、35、99、18、76 這 5 個(gè)數(shù)從大到小進(jìn)行排序，那么數(shù)越大，越需要把它放在前面
思路如下：
- 從后開(kāi)始遍歷，首先比較 18 和 76，發(fā)現(xiàn) 76 比 18 大，就把兩個(gè)數(shù)交換順序，得到 12、35、99、76、18
- 接著比較 76 和 99，發(fā)現(xiàn) 76 比 99 小，所以不用交換順序
- 接著比較 99 和 35，發(fā)現(xiàn) 99 比 35 大，交換順序
- 接著比較 99 和 12，發(fā)現(xiàn) 99 比 12 大，交換順序
最終第 1 趟排序的結(jié)果變成了 99、12、35、76、18，如下圖所示：
上述可以看到，經(jīng)過(guò)第一趟的排序，可以得到最大的元素，接下來(lái)第二趟排序則對(duì)剩下的的4個(gè)元素進(jìn)行排序，如下圖所示：
經(jīng)過(guò)第 2 趟排序，結(jié)果為 99、76、12、35、18
然后開(kāi)始第3趟的排序，結(jié)果為99、76、35、12、18
然后第四趟排序結(jié)果為99、76、35、18、12
經(jīng)過(guò) 4 趟排序之后，只剩一個(gè) 12 需要排序了，這時(shí)已經(jīng)沒(méi)有可比較的元素了，這時(shí)排序完成
二、如何實(shí)現(xiàn)
如果要實(shí)現(xiàn)一個(gè)從小到大的排序，算法原理如下：
首先比較相鄰的元素，如果第一個(gè)元素比第二個(gè)元素大，則交換它們
針對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣，最后的元素會(huì)是最大的數(shù)
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較
用代碼表示則如下：
- function bubbleSort(arr) {
- const len = arr.length;
- for (let i = 0; i < len - 1; i++) {
- for (let j = 0; j < len - 1 - i; j++) {
- if (arr[j] > arr[j+1]) { // 相鄰元素兩兩對(duì)比
- var temp = arr[j+1]; // 元素交換
- arr[j+1] = arr[j];
- arr[j] = temp;
- }
- }
- }
- return arr;
- }
可以看到：冒泡排序在每一輪排序中都會(huì)使一個(gè)元素排到一趟， 也就是最終需要 n-1 輪這樣的排序
而在每輪排序中都需要對(duì)相鄰的兩個(gè)元素進(jìn)行比較，在最壞的情況下，每次比較之后都需要交換位置，此時(shí)時(shí)間復(fù)雜度為O(n^2)
優(yōu)化
對(duì)冒泡排序常見(jiàn)的改進(jìn)方法是加入一標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過(guò)程中是否有數(shù)據(jù)交換
如果進(jìn)行某一趟排序時(shí)并沒(méi)有進(jìn)行數(shù)據(jù)交換，則說(shuō)明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序，避免不必要的比較過(guò)程
可以設(shè)置一標(biāo)志性變量pos，用于記錄每趟排序中最后一次進(jìn)行交換的位置，由于pos位置之后的記錄均已交換到位，故在進(jìn)行下一趟排序時(shí)只要掃描到pos位置即可，如下：
- function bubbleSort1(arr){
- const i=arr.length-1;//初始時(shí),最后位置保持不變
- while(i>0){
- let pos = 0;//每趟開(kāi)始時(shí),無(wú)記錄交換
- for(let j = 0; j < i; j++){
- if(arr[j] > arr[j+1]){
- let tmp = arr[j];
- arr[j] = arr[j+1];
- arr[j+1] = tmp;
- pos = j;//記錄最后交換的位置
- }
- }
- i = pos;//為下一趟排序作準(zhǔn)備
- }
- return arr;
- }
在待排序的數(shù)列有序的情況下，只需要一輪排序并且不用交換，此時(shí)情況最好，時(shí)間復(fù)雜度為O(n)
并且從上述比較中看到，只有后一個(gè)元素比前面的元素大(小)時(shí)才會(huì)對(duì)它們交換位置并向上冒出，對(duì)于同樣大小的元素，是不需要交換位置的，所以對(duì)于同樣大小的元素來(lái)說(shuō)，相對(duì)位置是不會(huì)改變的，因此， 冒泡排序是穩(wěn)定的
三、應(yīng)用場(chǎng)景
冒泡排的核心部分是雙重嵌套循環(huán)， 時(shí)間復(fù)雜度是 O(N 2 )，相比其它排序算法，這是一個(gè)相對(duì)較高的時(shí)間復(fù)雜度，一般情況不推薦使用，由于冒泡排序的簡(jiǎn)潔性，通常被用來(lái)對(duì)于程序設(shè)計(jì)入門的學(xué)生介紹算法的概念
參考文獻(xiàn)
- https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306
- https://www.runoob.com/w3cnote/bubble-sort.html
- http://data.biancheng.net/view/116.html
- https://dsb123dsb.github.io/2017/03/07/js%E5%AE%9E%E7%8E%B0%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E4%BB%A5%E5%8F%8A%E4%BC%98%E5%8C%96/
當(dāng)前題目：面試官：說(shuō)說(shuō)你對(duì)冒泡排序的理解？如何實(shí)現(xiàn)？應(yīng)用場(chǎng)景？
鏈接URL：http://fisionsoft.com.cn/article/cdpoppg.html
