新星計劃Day10【資料結構與算法】 排序算法1
👩💻部落格首頁：京與舊鋪的部落格首頁
✨歡迎關注🖱點贊🎀收藏⭐留言✒
🔮本文由京與舊鋪原創，
😘系列專欄：java學習
👕參考網課：尚矽谷
💻首發時間：🎞2022年5月11日🎠
🎨你做三四月的事，八九月就會有答案，一起加油吧
🀄如果覺得部落客的文章還不錯的話，請三連支援一下部落客哦
🎧最後的話，作者是一個新人，在很多方面還做的不好，歡迎大佬指正，一起學習哦，沖沖沖
💬推薦一款模拟面試、刷題神器👉點選進入網站
🛒導航小助手🎪
文章目錄
- 新星計劃Day10【資料結構與算法】 排序算法1
- 🛒導航小助手🎪
- @[toc]
- 👜50.排序算法介紹和分類
- 👛51.時間頻度介紹和特點
- 🧤52.時間複雜度計算和舉例說明
- 常數階O(1)
- 對數階O(log2n)
- 線性階O(n)
- 線性對數階O(nlogN)
- 平方階O(n²)
- 立方階O(n³)、K次方階O(n^k)
- 🩱53.平均和最壞時間複雜度介紹
- 平均時間複雜度和最壞時間複雜度
- 空間複雜度
- 🎍54.冒泡排序算法圖解
- 冒泡排序
- 基本介紹
👜50.排序算法介紹和分類
排序也稱排序算法(Sort Algorithm)，排序是将一組資料，依指定的順序進行排列 的過程。
排序的分類
- 内部排序：指将需要處理的所有資料都加載到内部存儲器中進行排序。
-
外部排序法：資料量過大，無法全部加載到記憶體中，需要借助外部存儲進行排序。
算法的時間複雜度：
度量一個程式(算法)執行時間的兩種方法
-
事後統計的方法
這種方法可行, 但是有兩個問題：
一是要想對設計的算法的運作性能進行評測，需要實際運作該程式
二是所得時間的統計量依賴于計算機的硬體、軟體等環境因素
這種方式，要在同一台計算機的相同狀态下運作，才能比較那個算法速度更快
- 事前估算的方法 通過分析某個算法的時間複雜度來判斷哪個算法更優
👛51.時間頻度介紹和特點
時間頻度：一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
- 2n+20 和 2n 随着n 變大，執行曲線無限接近，20可以忽略
- 3n+10 和 3n 随着n 變大，執行曲線無限接近，10可以忽略
- 2n^2+3n+10 和 2n^2 随着n 變大，執行曲線無限接近，可以忽略 3n+10
- n^2+5n+20 和 n^2 随着n 變大，執行曲線無限接近，可以忽略 5n+20
- 随着n值變大，5n^2+7n 和 3n^2 + 2n ，執行曲線重合，說明 這種情況下，5和3可以忽略
- 而n^3+5n 和 6n^3+4n ，執行曲線分離，說明多少次方式關鍵
🧤52.時間複雜度計算和舉例說明
- 一般情況下，算法中的基本操作語句的重複執行次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近于無窮大時，T(n) / f(n) 的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作 T(n)=Ｏ( f(n) )，稱Ｏ( f(n) ) 為算法的漸進時間複雜度，簡稱時間複雜度。
- T(n) 不同，但時間複雜度可能相同。 如：T(n)=n²+7n+6 與 T(n)=3n²+2n+2 它們的T(n) 不同，但時間複雜度相同，都為O(n²)。
- 計算時間複雜度的方法：
- 用常數1代替運作時間中的所有加法常數 T(n)=n²+7n+6 => T(n)=n²+7n+1
- 修改後的運作次數函數中，隻保留最高階項 T(n)=n²+7n+1 => T(n) = n²
- 去除最高階項的系數 T(n) = n² => T(n) = n² => O(n²)
常見的時間複雜度
- 常數階O(1)
- 對數階O(log2n)
- 線性階O(n)
- 線性對數階O(nlog2n)
- 平方階O(n^2)
- 立方階O(n^3)
- k次方階O(n^k)
- 指數階O(2^n)
常數階O(1)
- 無論代碼執行了多少行，隻要是沒有循環等複雜結構，那這個代碼的時間複雜度就都是O(1)
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;複制到剪貼闆複制失敗複制成功 - 上述代碼在執行的時候，它消耗的時候并不随着某個變量的增長而增長，那麼無論這類代碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時間複雜度。
對數階O(log2n)
int n = 100;
int i = 1;
while (i < n) {
i = i * 2;
}複制到剪貼闆複制失敗複制成功 說明：在while循環裡面，每次都将 i 乘以 2，乘完之後，i 距離 n 就越來越近了。假設循環x次之後，i 就大于 2 了，此時這個循環就退出了，也就是說 2 的 x 次方等于 n，那麼 x = log2n也就是說當循環 log2n 次以後，這個代碼就結束了。是以這個代碼的時間複雜度為：O(log2n) 。 O(log2n) 的這個2 時間上是根據代碼變化的，i = i * 3 ，則是 O(log3n)
線性階O(n)
int n = 100;
int j = 0;
for (int i = 1; i <= n; i++) {
j = i;
j++;
}複制到剪貼闆複制失敗複制成功 說明：這段代碼，for循環裡面的代碼會執行n遍，是以它消耗的時間是随着n的變化而變化的，是以這類代碼都可以用O(n)來表示它的時間複雜度
線性對數階O(nlogN)
int n = 100;
int m;
int i;
for (m = 1; m < n; m++) {
i = 1;
while (i < n) {
i = i * 2;
}
}複制到剪貼闆複制失敗複制成功 說明：線性對數階O(nlogN) 其實非常容易了解，将時間複雜度為O(logn)的代碼循環N遍的話，那麼它的時間複雜度就是 n*O(log2N)，也就是了O(nlog2N)
平方階O(n²)
int x;
int j;
int i = 0;
int n = 100;
for (x = 1; i <= n; x++) {
for (i = 1; i <= n; i++) {
j = i;
j ++;
}
}複制到剪貼闆複制失敗複制成功 說明：平方階O(n²) 就更容易了解了，如果把 O(n) 的代碼再嵌套循環一遍，它的時間複雜度就是 O(n²)，這段代碼其實就是嵌套了2層n循環，它的時間複雜度就是 O(nn)，即 O(n²) 如果将其中一層循環的n改成m，那它的時間複雜度就變成了 O(mn)
立方階O(n³)、K次方階O(n^k)
說明：參考上面的O(n²) 去了解就好了，O(n³)相當于三層n循環，其它的類似
🩱53.平均和最壞時間複雜度介紹
平均時間複雜度和最壞時間複雜度
- 平均時間複雜度是指所有可能的輸入執行個體均以等機率出現的情況下，該算法的運作時間。
- 最壞情況下的時間複雜度稱最壞時間複雜度。一般讨論的時間複雜度均是最壞情況下的時間複雜度。 這樣做的原因是：最壞情況下的時間複雜度是算法在任何輸入
- 執行個體上運作時間的界限，這就保證了算法的運作時間不會比最壞情況更長。平均時間複雜度和最壞時間複雜度是否一緻，和算法有關
空間複雜度
- 類似于時間複雜度的讨論，一個算法的空間複雜度(Space Complexity)定義為該算法所耗費的存儲空間，它也是問題規模n的函數
- 空間複雜度(Space Complexity)是對一個算法在運作過程中臨時占用存儲空間大小的量度。有的算法需要占用的臨時工作單元數與解決問題的規模n有關，它随着n的增大而增大，當n較大時，将占用較多的存儲單元，例如快速排序和歸并排序算法就屬于這種情況
- 在做算法分析時，主要讨論的是時間複雜度。從使用者使用體驗上看，更看重的程式執行的速度。一些緩存産品(redis、memcache)和算法(基數排序)本質就是用空間換時間
🎍54.冒泡排序算法圖解
冒泡排序
基本介紹
- 冒泡排序（Bubble Sorting）的基本思想是：通過對待排序序列從前向後（從下标較小的元素開始），依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向後部，就象水底下的氣泡一樣逐漸向上冒。
- 因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，是以要在排序過程中設定一個标志flag判斷元素是否進行過交換。進而減少不必要的比較。(這裡說的優化，可以在冒泡排序寫好後，在進行)
- 周遊1次過後，可以指定已經排好序資料的下标flag，那麼下1次排序排到flag就可以了，flag不斷向前移動，移動到第1位之後排序就結束了
下期預告：力扣每日一練之連結清單Day8