seo做的最好的網(wǎng)站排行,discuz 做網(wǎng)站可以嗎,濟(jì)寧最新通知今天,簡(jiǎn)單建設(shè)一個(gè)網(wǎng)站的過程目錄 一、冒泡排序思想 二、冒泡排序代碼 三、冒泡排序時(shí)間復(fù)雜度與空間復(fù)雜度 1. 時(shí)間復(fù)雜度分析 2. 空間復(fù)雜度分析 一、冒泡排序思想 冒泡排序的核?思想就是#xff1a;兩兩相鄰的元素進(jìn)??較#xff0c;元素 小 / 大 就交換#xff0c;然后進(jìn)行下一個(gè)兩兩相鄰的元…目錄一、冒泡排序思想二、冒泡排序代碼三、冒泡排序時(shí)間復(fù)雜度與空間復(fù)雜度1. 時(shí)間復(fù)雜度分析2. 空間復(fù)雜度分析一、冒泡排序思想冒泡排序的核?思想就是兩兩相鄰的元素進(jìn)??較元素 小 / 大 就交換然后進(jìn)行下一個(gè)兩兩相鄰的元素進(jìn)??較重復(fù)以上動(dòng)作直到 升序 / 降序。二、冒泡排序代碼#includestdio.h void bubble_sort(int* arr, int sz) { int i 0; for (i 0; i sz - 1; i) { int j 0; int flag 1; for (j 0; j sz - 1 - i; j) { if (arr[j] arr[j1]) { int tmp 0; tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; flag 0; } } if (flag) { break; } } } int main() { int arr[] { 10,9,8,7,6,5,4,3,2,1 }; int sz sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz); for (int i 0; i sz; i) { printf(%d , arr[i]); } return 0; }進(jìn)行升序排序如圖三、冒泡排序時(shí)間復(fù)雜度與空間復(fù)雜度1. 時(shí)間復(fù)雜度分析冒泡排序的核心操作是比較和交換。我們通過嵌套循環(huán)來實(shí)現(xiàn)外層循環(huán)控制排序的“輪數(shù)”。對(duì)于 n 個(gè)元素最多需要 n-1 輪才能確保完全有序。內(nèi)層循環(huán)在每一輪中對(duì)未排序部分的相鄰元素進(jìn)行兩兩比較并根據(jù)需要交換位置。時(shí)間復(fù)雜度我們只討論最壞情況當(dāng)需要排序成升序的數(shù)組完全是逆序的時(shí)每一輪都需要進(jìn)行最大次數(shù)的比較和交換。比較次數(shù) (n-1) (n-2) ... 2 1 n(n-1)/2交換次數(shù)同樣約為n(n-1)/2。因此總操作次數(shù)與 n2 成正比時(shí)間復(fù)雜度為O(n2)。2. 空間復(fù)雜度分析冒泡排序的整個(gè)排序過程只在原數(shù)組內(nèi)部進(jìn)行。除了使用幾個(gè)固定的臨時(shí)變量如用于交換的tmp、循環(huán)計(jì)數(shù)器i, j、判斷是否已經(jīng) 升序 / 降序 的flag外不需要申請(qǐng)額外的、與數(shù)據(jù)規(guī)模 n 相關(guān)的存儲(chǔ)空間。所以無論數(shù)組有多大這些臨時(shí)變量的數(shù)量都是固定的。因此冒泡排序的空間復(fù)雜度為O(1)。