渡過了一個期中考....恩哼。
排序章節早就看完了XD
只是抽不出時間寫筆記QQQ
=============午安分隔線=================
< 排序 >
當有一連串資料的時候，如何有效率的將他們排列成指定的順序？
假設現在有10個0~9的數字，要如何用代碼將它們依序排列、並輸出？
ex. 5237147482 → ??? → 122345778
> 桶子排序(簡化版)
1. 一個大小為10+1的陣列。i, j, t 三個變數。
☆ int a[11], i, j, t ;
2. 初始化陣列數值為0。
☆ for (int i = 0; i <= 10; i++) {
a[ i ] = 0;
}
3. 將數字依序讀入，並進行計數。假設讀入一個3，就將 a[ 3 ] 的數值+1。
☆ for (int i = 0; i <= 10; i++){
scanf( "%d", &t ); a[ t ] ++;
}
4. 將number中儲存好的數字，根據數量依序輸出。假設 a[ 1 ] = 3，即輸出1 1 1。
☆ for (int i = 0; i <= 10; i++){
for (int j = 0; j <= a[ i ]; j++){
printf( "%d ", i);
}
}
★演算法的時間複雜度：O( M+N )
M(桶子總數)+N(待排序數字總量)。適合處理數字(數據)總量大時的狀況。
> 氣泡排序(少用)
每次比較兩個相鄰的元素，如果順序錯誤就把它們交換，直到換到最後一位為止。
將最小的數字歸位後，重新開始新的一輪。
利用結構體(struct)能將數字以外的資訊一併輸入、輸出。
★演算法的時間複雜度：O( N^2 )
N(待排序數字總量)。複雜度高，使用起來會浪費太多時間。
> 快速排序(最常用)
是一個看懂後會發自內心覺得...想出來的人真的是天才的演算法。
不過代碼方面比較複雜和長就是了...所以只記錄核心概念。
1. 將第一個數設定為基準，從序列最尾端 j 開始往前找一個 小於等於 基準數的數，再從序列頭 i 開始往後找一個 大於等於 基準數的數。
(1) 找到兩個數後，將它們交換。 5237147482 → 5232147487
(2) 繼續移動。 5232147487 → 5232144787
(3) 當 i 和 j 指定在同一個數時，和基準數交換後，結束這一輪。
5232144787 → 4232145787
2. 可看到原本的基準數5，已順利移動到序列的中間，並將左右兩側的序列分成小於5、以及大於5的兩部份。
(1) 用同樣的規則交換左右兩側序列的順序，直到無法拆解新的子序列為止。
423214 5 787 → 423214 5 778 → 42321 4 5 778 → 12324 4 5 778 →
1232 4 4 5 7 7 8 → 1 232 4 4 5 7 7 8 → 1 223 4 4 5 7 7 8 → 1 2 2 3 4 4 5 7 7 8
★演算法的時間複雜度：O( NlogN )
N(待排序數字總量)。從氣泡排序演化出的一種帥氣排序法，能節省大量時間。
============額外的什麼什麼=============
1. 通常狀況下，桶子排序最快。
2. 但當桶子數目超過2*10^9左右時，會超過陣列的最大長度，此時就只能使用快速排序。
3. 序列中兩個數值交換的方法：
t = a [ i ];
a [ i ] = a [ j ];
a [ j ] = t;
4. 若只是單純交換數字，也可不使用 t 暫存就將 a[ i ] 和 a[ j ] 兩個數值交換，
a [ i ] = a [ j ] - a [ i ] ;
a [ j ] = a [ j ] - a [ i ] ;
a [ i ] = a [ j ] + a [ i ] ;
( 計算並記錄 a [ i ] 到 a [ j ] 的距離，從a [ j ] 往回推得到舊的 a [ i ] 數值後，再加回去取得新的 a [ i ] 數值)
( EX. a [ i ] = 3; a [ j ] = 5; )
( a [ i ] = 5 - 3 = 2; a [ j ] = 5 - 2 = 3; a [ i ] = 3 + 2 = 5;)
========================================
筆記大多是書裡面摘錄的東西OvO...
有興趣的巴友們能自己google更詳細的資料XD
閱讀進度 26 / 244。
創作內容
【演算法】心得筆記 - 2 - 排序
遊戲製作 (0)
