TypeScript實(shí)現(xiàn)十大排序算法之冒泡排序示例詳解
一. 冒泡排序的定義
冒泡排序是一種簡(jiǎn)單的排序方法。
- 基本思路是通過(guò)兩兩比較相鄰的元素并交換它們的位置,從而使整個(gè)序列按照順序排列。
- 該算法一趟排序后,最大值總是會(huì)移到數(shù)組最后面,那么接下來(lái)就不用再考慮這個(gè)最大值。
- 一直重復(fù)這樣的操作,最終就可以得到排序完成的數(shù)組。
這種算法是穩(wěn)定的,即相等元素的相對(duì)位置不會(huì)發(fā)生變化。
- 而且在最壞情況下,時(shí)間復(fù)雜度為O(n^2),在最好情況下,時(shí)間復(fù)雜度為O(n)。
因此,冒泡排序適用于數(shù)據(jù)規(guī)模小的場(chǎng)景。
二. 冒泡排序的流程
冒泡排序的流程如下:
- 從第一個(gè)元素開始,逐一比較相鄰元素的大小。
- 如果前一個(gè)元素比后一個(gè)元素大,則交換位置。
- 在第一輪比較結(jié)束后,最大的元素被移動(dòng)到了最后一個(gè)位置。
- 在下一輪比較中,不再考慮最后一個(gè)位置的元素,重復(fù)上述操作。
- 每輪比較結(jié)束后,需要排序的元素?cái)?shù)量減一,直到?jīng)]有需要排序的元素。
- 排序結(jié)束。
- 這個(gè)流程會(huì)一直循環(huán),直到所有元素都有序排列為止。
三. 冒泡排序的圖解
四. 冒泡排序的代碼
// 定義函數(shù),用于實(shí)現(xiàn)冒泡排序算法 function bubbleSort(arr: number[]): number[] { // 外層循環(huán),控制需要比較的輪數(shù) for (let i = 0; i < arr.length - 1; i++) { // 內(nèi)層循環(huán),控制每輪需要比較的次數(shù) for (let j = 0; j < arr.length - 1 - i; j++) { // 如果前一個(gè)元素比后一個(gè)元素大,則交換它們的位置 if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } // 返回排序后的數(shù)組 return arr; } // 測(cè)試代碼 const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]; console.log(bubbleSort(arr)); // 輸出:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
說(shuō)明:
- 冒泡排序是一種暴力枚舉算法,通過(guò)多次循環(huán)比較相鄰的元素,把最大的元素逐漸冒泡到數(shù)組末端。
- 外層循環(huán):控制排序的趟數(shù),每一輪排序會(huì)把最大的元素放到最后,因此每次循環(huán)需要比較的元素個(gè)數(shù)也會(huì)逐漸減少。
- 內(nèi)層循環(huán):比較相鄰元素,如果左邊元素比右邊元素大,則交換位置。
- 冒泡排序是一種時(shí)間復(fù)雜度較高的算法,一般不用于大數(shù)據(jù)量的排序,但它很容易理解,是一種初學(xué)者學(xué)習(xí)排序算法的好
五. 冒泡排序的時(shí)間復(fù)雜度
在冒泡排序中,每次比較兩個(gè)相鄰的元素,并交換他們的位置,如果左邊的元素比右邊的元素大,則交換它們的位置。這樣的比較和交換的過(guò)程可以用一個(gè)循環(huán)實(shí)現(xiàn)。
- 在最好的情況下,數(shù)組已經(jīng)是有序的,那么比較和交換的次數(shù)是最少的。
- 在這種情況下,比較次數(shù)是n-1次,交換次數(shù)是0次,其中n是數(shù)組的長(zhǎng)度。
- 在最壞的情況下,數(shù)組是逆序的,那么比較和交換的次數(shù)是最多的。
- 在這種情況下,比較次數(shù)是n-1次,交換次數(shù)是n(n-1)/2次,其中n是數(shù)組的長(zhǎng)度。
- 在平均情況下,比較和交換的次數(shù)取決于數(shù)組的排列方式。
- 一般來(lái)說(shuō),平均情況下比較次數(shù)是n-1次,交換次數(shù)是n(n-1)/4次,其中n是數(shù)組的長(zhǎng)度。
冒泡排序的時(shí)間復(fù)雜度分析:
- 最好情況:當(dāng)序列已經(jīng)有序,每次比較和交換操作都不會(huì)進(jìn)行,只需要進(jìn)行n-1次比較,時(shí)間復(fù)雜度為O(n)。
- 最壞情況:當(dāng)序列完全逆序,需要進(jìn)行n-1輪比較和n-1次交換操作,時(shí)間復(fù)雜度為O(n^2)。
- 平均情況:需要進(jìn)行的比較和交換操作的次數(shù)在所有情況中的平均值,時(shí)間復(fù)雜度也是O(n^2)。
由此可見,冒泡排序的時(shí)間復(fù)雜度主要取決于數(shù)據(jù)的初始順序,最壞情況下時(shí)間復(fù)雜度是O(n^2),不適用于大規(guī)模數(shù)據(jù)的排序。
六. 冒泡排序的總結(jié)
- 冒泡排序適用于數(shù)據(jù)規(guī)模較小的情況,因?yàn)樗臅r(shí)間復(fù)雜度為O(n^2),對(duì)于大數(shù)據(jù)量的排序會(huì)變得很慢。
- 同時(shí),它的實(shí)現(xiàn)簡(jiǎn)單,代碼實(shí)現(xiàn)也容易理解,適用于學(xué)習(xí)排序算法的初學(xué)者。
- 但是,在實(shí)際的應(yīng)用中,冒泡排序并不常用,因?yàn)樗男瘦^低。
- 此外,冒泡排序比較和交換的次數(shù)較多,占用更多的存儲(chǔ)空間和時(shí)間,不適用于處理大數(shù)據(jù)量的情況。
- 因此,在實(shí)際應(yīng)用中,冒泡排序通常被更高效的排序算法代替,如快速排序、歸并排序等。
以上就是TypeScript實(shí)現(xiàn)十大排序算法之冒泡排序示例詳解的詳細(xì)內(nèi)容,更多關(guān)于TypeScript冒泡排序算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
TypeScript數(shù)據(jù)結(jié)構(gòu)之隊(duì)列結(jié)構(gòu)Queue教程示例
這篇文章主要為大家介紹了TypeScript數(shù)據(jù)結(jié)構(gòu)之隊(duì)列結(jié)構(gòu)Queue教程示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-02-02TypeScript十大排序算法之選擇排序?qū)崿F(xiàn)示例詳解
這篇文章主要為大家介紹了TypeScript十大排序算法之選擇排序?qū)崿F(xiàn)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-02-02TypeScript使用noImplicitAny實(shí)戰(zhàn)解析
這篇文章主要為大家介紹了TypeScript使用noImplicitAny實(shí)戰(zhàn)解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08typescript快速上手的進(jìn)階類型與技術(shù)
本文講述了typescript開發(fā)的一些高級(jí)的類型與技術(shù),算是對(duì)于基礎(chǔ)知識(shí)點(diǎn)的補(bǔ)充,具體內(nèi)容包括:比如元組、枚舉類、接口、泛型相關(guān)概念等。雖說(shuō)是進(jìn)階,但是內(nèi)容不算多也并不難理解。2022-12-12