Aros/開發者/遊戲程式設計/基礎
- 學會像程式設計師一樣思考
- 學習 C C++
- 學習 AROS (Amiga) 的工作原理
第一個基本上是關於演算法設計和要避免的事項。你是否知道“義大利麵條程式碼”的含義？結構化程式設計？如何進行面向物件設計？大“O”符號？遞迴？快速排序？這些概念無論你使用什麼語言或平臺都非常重要。
遊戲引擎系統相對於其他系統的定位
- 第 1 級 - C、C++ 基礎
- 第 2 級 - 具有 OpenGL 框架的 SDL、具有 OpenGL 的 Raylib
- 第 3 級 - Godot 引擎、Ren'Py、GameMaker、Scratch、Unity、Unreal 等（AROS 沒有）
Top 100 games have over 90% market share
概念（按難度排列的營銷要點） - 遊戲風格，但...
arcade, catch, platformer, endless runner, mazes, tower defense, puzzle, city builder, rhythm, text, visual novel, adventure, party, shoot 'em up, metrovania, bullet hell, beat 'em up, walking sim on rails, card deck builder, cooking, racing, fighter, tactical turn based, real time strategy rts long term, relationships, survival, collectothon, fps, sandbox, management simulator, trading, sports, betting, rogue, roguelite, roguelike, dungeon crawler, rpg, horror, souls, soulslite, soulslike, battle royale, arena,
類似遊戲 - 相同...外觀/感覺/型別/範圍/目標受眾
測量（規模） - 角色/敵人的互動方式，例如範圍、揮動、抓取等
原型 - 粗糙的灰盒版本、模型、概念、螢幕截圖、配色方案、徽標、字型等
10 分鐘演示 - 用於資金籌集的垂直切片，獲取關於良好部分、糟糕想法、缺失部分等的初步印象，即玩遊戲測試
樂趣，例如克服障礙挑戰、升級（任務日誌到待辦事項列表）和獎勵、奇妙感
設計模式 - 有限狀態機（透過狀態實體轉換的行為）、事件匯流排單例（管理來自物件的訊號）、實體元件模式（構建塊）
遊戲迴圈 - 、提取、掠奪射擊遊戲、
機制
- 牆壁、尖刺、 等
故事 - 敘事、故事情節、
釋出
- 遊戲果醬，以限制範圍並在 1 周內完成乾淨的程式碼
- 然後隨著你獲得經驗和知識，擴充套件到 3、4 和 6 個月週期，之後最多 9 或 12 個月以積累經驗並保持專注
design process - Empathize: Research user needs - Define: State user needs and problems - Refine: Challenge assumptions and create ideas - Prototype: Start to create solutions - Test: Try out solutions
當然，你需要學習在 Amiga 上程式設計。幸運的是，Amiga 是一臺有趣的計算機，可以用相對較小的 API 進行程式設計。也就是說，你不會被作業系統呼叫淹沒，但是，也有一些糟糕的部分。如果你只想開啟一個視窗並建立一些按鈕，那很簡單。想編寫一個網路瀏覽器嗎？那會很困難，主要是因為作業系統沒有提供你需要的很多東西，所以你最終會自己編寫。 :-)
- 設定 圖塊、遮罩、平臺相關內容 等
- 雙緩衝用於移動物件精靈（碰撞）或滾動
- 2D 框架，它承擔了編寫你自己的例程（如 SDL1.2）或 raylib5 的部分工作
- 從以下每個遊戲型別中至少建立一個：棋盤/網格、迷宮、卡片等，以積累經驗
- 碰撞盒
- 旋轉
- 重力
- 阻力 - 彈簧阻尼質量模型
- 區域劃分藝術資產
- 使用 2D 法線貼圖的照明/陰影
- 粒子效果，火焰、餘燼、煙霧、火花、燈籠、
- 碰撞
點旋轉
x' = x*cos(a) - y*sin(a) y' = x*sin(a) + y*cos(a)
在教程中簡要提及它是一個昂貴的操作，這裡是最基本的點旋轉公式。如你所見，它至少涉及 2 次表查詢、4 次乘法和 2 次加法，但正弦和餘弦值可以對每個點重複使用。為了山丘旋轉的目的，這意味著旋轉 Z 和 Y 座標，而不是 X 和 Y 座標。要找到此公式的推導，請查詢“座標軸旋轉”。
/* assuming width and height are integers with the image's dimensions */
for(int x = 0; x < width; x++) {
int hwidth = width / 2;
int hheight = height / 2;
double sinma = sin(-angle);
double cosma = cos(-angle);
for(int y = 0; y < height; y++) {
int xt = x - hwidth;
int yt = y - hheight;
int xs = (int)round((cosma * xt - sinma * yt) + hwidth);
int ys = (int)round((sinma * xt + cosma * yt) + hheight);
if(xs >= 0 && xs < width && ys >= 0 && ys < height) {
/* set target pixel (x,y) to color at (xs,ys) */
} else {
/* set target pixel (x,y) to some default background */
}
}
}
透視變換（透視投影 == 除以 Z）相當於
x = x*d/z+d y = y*d/z+d
其中 d 是視角與視點的距離，x、y、z 是（顯然）你在 3D 空間中的 x、y、z 座標。如果不存在“除以 Z”，則深度方向的移動會感覺錯誤，並且你的物體會在錯誤的時間加速/減速。
3d 投影
y_screen = (y_world / z) + (screen_height >> 1)
或
z = y_world / (y_screen - (screen_height >> 1))
此公式採用物體的 x 或 y 世界座標、物體的 z，並返回 x 或 y 畫素位置。或者，反過來，給定世界和螢幕座標，返回 z 位置。
快速線性插值
o(x) = y1 + ((d * (y2-y1)) >> 16)
假設所有數字都採用 16.16 定點格式。y1 和 y2 是要插值的兩個值，d 是這兩個點之間的 16 位分數距離。例如，如果 d=$7fff，則表示這兩個值之間的一半。這對於找出某個值位於兩個線段之間的哪個位置非常有用。
定點算術 對於沒有專用數學硬體的舊系統而言，浮點數非常昂貴。相反，使用了稱為定點的系統。這為數字的小數部分保留了特定數量的位。對於測試案例，假設你只為小數部分保留一位，為整數部分保留七位。該小數位將表示二分之一（因為二分之一加二分之一等於一個）。要獲取該位元組中儲存的整數，將數字右移一位。這可以擴充套件到為數字的小數部分和整數部分使用任意數量的位。
定點乘法比加法更棘手。在此操作中，你會將兩個數字相乘，然後右移保留用於小數部分的位數。由於溢位，有時你可能需要在乘法之前而不是之後進行移位。請參閱“快速線性插值”以瞭解定點乘法的示例。
避免除法 代替在標準投影公式中除以物體的 z，您可以利用道路的一些屬性來加快計算速度。假設您有一個 3D 線段的 z 位置和 y 位置，並且您想找到它屬於螢幕的哪一行。首先，遍歷 z 對映，直到您到達 3D 線段的 z 位置。然後，將線段的高度乘以相應的縮放值。結果是線段所屬的道路上方的畫素數量。
使用 Z 作為縮放值 縮放例程透過減慢或加快繪製例程讀取圖形資料的速度來工作。例如，如果您將讀取速度設定為一半，這將繪製一個大小是原始大小兩倍的精靈。這是因為每次繪製一個畫素時，精靈資料中的讀取位置只遞增一半，導致讀取位置每兩個畫素只遞增一個整數值。
通常，縮放例程具有諸如 x、y 和縮放因子之類的引數。但由於縮放因子只是 1/z，我們可以直接重用該精靈的 Z 值！儘管如此，我們仍然需要縮放因子來確定精靈的邊界，以便在縮放時保持其居中。
閱讀有關 2.5D 的更多資訊 這裡
二叉樹（簡單但有侷限性）蛇形演算法（比二叉樹更好）深度優先搜尋（DFS）（好的簡單迷宮 - 跟蹤路線並回溯以填補缺失部分）生長樹
遞迴細分（新增牆壁 - 分形狀）
Aldous-Broeder（基於效率低的均勻生成樹）Wilson's（更好的生成樹）Prim's（另一個生成樹）Kruskal's（好的但複雜的生成樹）
求解演算法
死衚衕回溯
一個完美的迷宮，從迷宮中的任意一點到任意另一點只有一條路徑。也就是說，沒有無法到達的部分，沒有迴圈路徑，也沒有開放區域。一個完美的迷宮可以使用深度優先搜尋演算法輕鬆地用計算機生成。
二維迷宮可以表示為一個矩形陣列的方格。每個方格有四面牆。每個方格中每個牆（北、南、東、西）的狀態儲存在由記錄陣列組成的資料結構中。每個記錄儲存一個表示方格中每個牆的狀態的位值。要建立相鄰方格之間的路徑，將移除當前方格的出口牆和下一個方格的入口牆。例如，如果下一個方格在當前方格的右邊（東），則移除當前方格的右邊（東）牆和下一個方格的左邊（西）牆。
深度優先搜尋 - 最簡單的迷宮生成演算法
- 從網格中的隨機方格開始
- 查詢尚未訪問過的隨機相鄰方格
- 如果您找到一個，移動到那裡，打碎方格之間的牆壁。如果找不到，則退回到前一個方格
- 重複步驟 2 和 3，直到您訪問了網格中的每個方格
虛擬碼
create a CellStack (LIFO) to hold a list of cell locations
set TotalCells = number of cells in grid
choose a cell at random and call it CurrentCell
set VisitedCells = 1
while VisitedCells < TotalCells
find all neighbors of CurrentCell with all walls intact
if one or more found
choose one at random
knock down the wall between it and CurrentCell
push CurrentCell location on the CellStack
make the new cell CurrentCell
add 1 to VisitedCells
else
pop the most recent cell entry off the CellStack
make it CurrentCell
endIf
endWhile
假設您有一個大小為 x b 的迷宮，您需要 a + 1 和 b + 1 的牆壁，因此陣列的大小應該是（size * 2 + 1）
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 61 // 30 * 2 + 1
#define CELL 900 // 30 * 30
#define WALL 1
#define PATH 0
void init_maze(int maze[MAX][MAX]);
void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int bactrack_y[CELL], int x, int y, int n, int visited);
void print_maze(int maze[MAX][MAX], int maze_size);
int is_closed(int maze[MAX][MAX], int x, int y);
int main(void)
{
srand((unsigned)time(NULL));
int size;
int indeks = 0;
printf("MAZE CREATOR\n\n");
printf("input (0 ~ 30): ");
scanf("%d", &size);
printf("\n");
int maze[MAX][MAX];
int backtrack_x[CELL];
int backtrack_y[CELL];
init_maze(maze);
backtrack_x[indeks] = 1;
backtrack_y[indeks] = 1;
maze_generator(indeks, maze, backtrack_x, backtrack_y, 1, 1, size, 1);
print_maze(maze, size);
getch();
return 0;
}
void init_maze(int maze[MAX][MAX])
{
for(int a = 0; a < MAX; a++)
{
for(int b = 0; b < MAX; b++)
{
if(a % 2 == 0 || b % 2 == 0)
maze[a][b] = 1;
else
maze[a][b] = PATH;
}
}
}
void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int backtrack_y[CELL], int x, int y, int n, int visited)
{
if(visited < n * n)
{
int neighbour_valid = -1;
int neighbour_x[4];
int neighbour_y[4];
int step[4];
int x_next;
int y_next;
if(x - 2 > 0 && is_closed(maze, x - 2, y)) // upside
{
neighbour_valid++;
neighbour_x[neighbour_valid]=x - 2;;
neighbour_y[neighbour_valid]=y;
step[neighbour_valid]=1;
}
if(y - 2 > 0 && is_closed(maze, x, y - 2)) // leftside
{
neighbour_valid++;
neighbour_x[neighbour_valid]=x;
neighbour_y[neighbour_valid]=y - 2;
step[neighbour_valid]=2;
}
if(y + 2 < n * 2 + 1 && is_closed(maze, x, y + 2)) // rightside
{
neighbour_valid++;
neighbour_x[neighbour_valid]=x;
neighbour_y[neighbour_valid]=y + 2;
step[neighbour_valid]=3;
}
if(x + 2 < n * 2 + 1 && is_closed(maze, x + 2, y)) // downside
{
neighbour_valid++;
neighbour_x[neighbour_valid]=x+2;
neighbour_y[neighbour_valid]=y;
step[neighbour_valid]=4;
}
if(neighbour_valid == -1)
{
// backtrack
x_next = backtrack_x[indeks];
y_next = backtrack_y[indeks];
indeks--;
}
if(neighbour_valid!=-1)
{
int randomization = neighbour_valid + 1;
int random = rand()%randomization;
x_next = neighbour_x[random];
y_next = neighbour_y[random];
indeks++;
backtrack_x[indeks] = x_next;
backtrack_y[indeks] = y_next;
int rstep = step[random];
if(rstep == 1)
maze[x_next+1][y_next] = PATH;
else if(rstep == 2)
maze[x_next][y_next + 1] = PATH;
else if(rstep == 3)
maze[x_next][y_next - 1] = PATH;
else if(rstep == 4)
maze[x_next - 1][y_next] = PATH;
visited++;
}
maze_generator(indeks, maze, backtrack_x, backtrack_y, x_next, y_next, n, visited);
}
}
void print_maze(int maze[MAX][MAX], int maze_size)
{
for(int a = 0; a < maze_size * 2 + 1; a++)
{
for(int b = 0; b < maze_size * 2 + 1; b++)
{
if(maze[a][b] == WALL)
printf("#");
else
printf(" ");
}
printf("\n");
}
}
int is_closed(int maze[MAX][MAX], int x, int y)
{
if(maze[x - 1][y] == WALL
&& maze[x][y - 1] == WALL
&& maze[x][y + 1] == WALL
&& maze[x + 1][y] == WALL
)
return 1;
return 0;
}
生長樹
它首先選擇一個隨機方格並將其新增到列表中
x, y = rand(width), rand(height) cells << [x, y] The program them simply loops until the list is empty until cells.empty? # ... end
在迴圈中，我們首先選擇要操作的方格。我要在這裡將我自己的程式的複雜性隱藏在一個簡單的“choose_index”方法後面；它接受一個數字並返回小於該數字的數字。
index = choose_index(cells.length) x, y = cells[index]
接下來，我們迭代一個隨機排列的方向列表，尋找一個未訪問的鄰居。如果找不到這樣的鄰居，我們將刪除列表中的給定方格，然後繼續。
[N, S, E, W].shuffle.each do |dir|
nx, ny = x + DX[dir], y + DY[dir]
if nx >= 0 && ny >= 0 && nx < width && ny < height && grid[ny][nx] == 0
# ...
end
end
cells.delete_at(index) if index
當找到一個有效的、未訪問的鄰居時，我們在當前方格和該鄰居之間開闢一條通道，將鄰居新增到列表中，將索引設定為 nil（表示找到了一個未訪問的鄰居），然後退出最內層迴圈。
grid[y][x] |= dir grid[ny][nx] |= OPPOSITE[dir] cells << [nx, ny] index = nil break
這就是它的全部內容。choose_index 方法的一些可能實現可能是
def choose_index(ceil) return ceil-1 if choose_newest? return 0 if choose_oldest? return rand(ceil) if choose_random? # or implement your own! end
- 單路線（困難且耗時）？？並使用 OpenGL（Mesa）例程] 或 raylib
- 3D 遊戲引擎，如 Antiryad Gx、panda 3d、[Quake Doom id Tech 1 到 3 用 C 語言編寫]、[id Tech 4 用 C++ 編寫]、Urho3d、[Terathon C4（商業）
AROS 目前沒有這些
- 3D 圖形引擎（需要新增網路、物理、聲音、指令碼、關卡編輯器等），如 Ogre3D C++、Crystal Space C++、irrlicht C++、3D 體素等、Cube C、Luxinia in C BSD、horde 3d、[]、[torque 3d]
您需要為每個類物件例項建立一個單獨的上下文，並在例項處於活動狀態時保持其活動狀態。上下文繫結到正在執行的任務，並且一次只能繫結一個上下文。開啟庫本身不會執行任何操作 - 所有操作都是相對於上下文執行的。
為了在子類中訪問右鍵按鈕，我在 setup 方法中添加了以下內容
set(_win(obj), MUIA_Window_NoMenus, TRUE);
如果您要繪製到的正方形是二維的並且沒有旋轉，那麼您可能在尋找 glDrawPixels。它允許您將矩形區域的畫素直接繪製到緩衝區，而無需使用任何多邊形。
glTexImage2D。這是在 OpenGL 中為 2D 紋理載入影像的呼叫。glTexImage2D 實際上接受指向影像中畫素資料的原始指標。您可以自己分配記憶體，並直接設定影像資料（無論您想如何），然後呼叫此函式將影像傳遞給 OpenGL。建立紋理後，您可以將其繫結到狀態，以便您的三角形使用該紋理。如果紋理需要更改，您將需要重新執行 glTexImage2D() 呼叫，或者使用諸如 glTexSubImage2D() 之類的功能進行部分更新。
只需將一個 GLubyte 陣列傳遞給 glTexImage2D 函式（以及繫結紋理等所需的所有函式）。沒有嘗試過這段程式碼，但它應該可以正常工作。陣列元素表示行、列和通道的序列版本。
int pixelIndex = 0;
GLubyte pixels[400];
for (int x = 0; x < 10; x++)
{
for (int y = 0; y < 10; x++)
{
for (int channel = 0; channel < 4; channel++)
{
// 0 = black, 255 = white
pixels[pixelIndex++] = 255;
}
}
}
glTexImage2D(
GL_TEXTURE_2D, 0, GL_RGBA, SIZE, SIZE, 0,
GL_RGBA, GL_UNSIGNED_BYTE, pixels);
您可以使用的 OpenGL 書籍可以使用二維陣列表示單色影像，因此假設您也可以使用三維陣列。
- 關於球體與三角形相交，以及稱為“2PI 求和方法”的東西來確定射線是否擊中三角形。
- 從您的牆壁建立平面並進行射線與平面相交測試。一個非常簡單的測試是點積測試。如果基於向量的標量“點”積的結果大於 0，或者向量指向大致相同的方向，那麼您就知道您在牆壁的近側。如果它小於 0，或者向量幾乎指向相反的方向，那麼您就在牆壁的遠側。
- 為了測試畫素級精度，您必須找到您的攝像機射線與所討論的平面相交的點。將攝像機退回到該點，計算碰撞響應，然後繼續
- 進行射線與三角形測試，然後計算三角形內部的重心座標。它還會在 NAN 上退出，這會導致問題。它也只使用點積。
射線與平面相交的方程。在迷宮中這樣做更容易，因為我們知道所有牆壁都會形成一個平面，因此不需要進行昂貴的射線與三角形測試。
Ray: p(t)=p0+td
Plane: p dot n=d
Equation: t=(d-p0 dot n)/(d dot n)
If ray is parallel to plane or (d dot n)=0 then there is no intersection.
If (d dot n)<0 then intersection during interval.
求解 p0，它實際上是此方程中的 p0.x 和 p0.y。這已經針對 t 求解，以在該時間間隔內測試相交。這件好事是點積測試和點測試在一個演算法中合併了。如果第一次時間間隔測試透過，則可以求解 p0。
- 基於網格的
- 迪傑斯特拉演算法 和 教程 以及它的近親 A* 演算法 和 虛擬碼
- 洪水演算法，然後聲音傳播。 將我的角色的虛擬版本放置在給定位置（通常是生成點）。我進行一次初始射線投射以將他與地面齊平，然後將該單個可佔用單元格新增到我的“未處理列表”中。然後，我檢查該單元格的四個鄰居，以檢視虛擬玩家是否可以不受到阻礙/過分跌落/攀爬的情況下踏入那裡。我將成功單元格新增到未處理列表中，並將初始單元格放入已處理列表中。重複此操作，直到未處理列表為空。我的演算法中的單元格還儲存地面的位置，這可能會根據遇到樓梯或斜坡而上升或下降。當從相關單元格列表建立扇區時，它使用包含所有這些點（+ 每個單元格的寬度和高度）的軸對齊邊界框
- D* 是一個動態 A*
- 3D 網格導航
A*（A 星）演算法從給定的起點移動到給定的目的地網格中。它所做的每一步都儲存在一個節點中。在這個節點資料結構中儲存了三個值
- 從起點開始的當前塊的座標
- 從該塊到終點的距離（不同的方法，曼哈頓距離、對角線距離、歐幾里得距離（可選的平方版本））
- 以及該塊的父塊（用於以後的回溯模式）
當演算法向目的地移動時，它將這些節點儲存到兩個堆疊中：開啟堆疊和關閉堆疊。一旦到達目的地塊，我們就透過節點回溯（使用指向父節點的指標），我們就有了描述的路徑
Insert the start point onto the open stack
while( nodes left on open stack ) {
//Pop first (closest) node off of open stack
node = openstack.pop
if( node.bDestination == 1 ) {
Loop upwards through data structure to generate path
exit function
}
//If we get here, this node isn't the destination
for( up, down, forward, backward, left, right in grid ) {
//GetNewNode returns null if block is occupied or in //closed stack
newnode = GetNewNode( currentDirection )
if( newnode ) {
//This InsertSorted function inserts the node //sorted based on the block's distance from the //destination
openstack.InsertSorted(newnode);
}
}
//Once a node is on the closedstack it is no longer used //(unless one of its children is the destination)
closedstack.push( node );
}
在這個演算法中，棘手的部分實際上是在 openstack 的 InsertSorted() 方法中。您根據節點到目的地的距離對節點進行排序。這是演算法中最重要的一部分，因為演算法選擇要搜尋的節點的順序基於這種排序。傳統上（至少在我的示例中），您使用曼哈頓距離，即從目的地到網格塊的距離。我對這個距離函式進行了調整，而是使用當前塊的中心點到目的地的 3D 距離（使用 BlockDistance3D）。出於某種原因，這使演算法在我的情況下執行得更好……它與使用曼哈頓距離相比，始終搜尋的節點更少。
Minecraft 克隆 OpenGL、Minetest C55、理論，
- C
- C++ [9]
學習 C 並不難，學習如何正確使用它可能很困難。C 的語法雖然簡潔，但非常簡單。您可以在幾張紙上描述整個 C 語言，它沒有太多內容。但是，正如我的教授總是告訴我的那樣，C 給您足夠的繩索來把自己（以及周圍的所有人）吊死。基本上，C 相信您知道自己在做什麼，如果您告訴它破壞記憶體，它會很樂意為您做到。C 不會像 Basic 一樣牽著您的手，但它會為您提供比任何其他語言都更強大的功能和靈活性。總之，我對所有 C 新手最好的建議是研究指標。當你認為自己 理解指標 時，再學習 它們 一些。這是 C 中讓人生畏的部分之一。
c value &c address of c *c pointed to by c
.c should contains functions .h usually contain #define #include typedef enum struct extern
C++ BASIC types and variables conditionals and loops i/o structures MEDIUM class constructor destructor methods instance variables
C++ 的底層語義（例如，何時使用虛擬，複製建構函式的作用）。即使沒有資料隱藏繼承、引用、多型性，您仍然擁有強大的結構。非常方便的功能，例如函式名稱過載（謹慎且適度使用）、宣告作為語句、對名稱的引用等等……資料和方法組合在一起稱為類。面嚮物件語言是類和物件。面向物件意味著具有資料和方法的物件。方法從一個物件傳送到另一個物件，而物件會操作其資料。它也有一些問題：語法很複雜（雖然不至於難以忍受），它沒有垃圾回收，您仍然需要自己管理記憶體，以及其他一些問題，這些問題可能不會直接影響獨自工作的程式設計師，但會在團隊合作時出現。
俄羅斯方塊、等等
Algorithms with youtube videos but start with small WB games first.
閱讀更多 這裡
算法理論涉及思考增長率（空間和時間）以及將問題分解為虛擬碼和 大 O 表示法，它教會了在選擇和最佳化演算法時要考慮哪些因素。
- 搜尋樹，例如：B 樹、B+ 樹、紅黑樹
- 排序演算法，例如快速排序、自然歸併排序、桶排序，
- 廣度優先搜尋（http://en.wikipedia.org/wiki/Graph_traversal）、深度優先搜尋（迷宮），
- 路徑查詢，例如爬山法、A 星，
- 向量,
# A is the array, p is the start position and r the end position
# i is the pivot value, p the start position value and r the end position value
#
# Randomised-Partition(A,p,r)
# i <- Random(p,r)
# exchange A(r) with A(i)
# return Partition(A,p,r)
#
# Randomised-QuickSort(A,p,r)
# if p< r then
# q <- Randomised-Partition(A,p,r)
# Randomised-QuickSort(A,p,q)
# Randomised-QuickSort(A,q+1,r)
#
#
void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
# choose (random?) pivot number and partition numbers into lower and greater around pivot
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
Youtube 影片 這裡 和
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
Youtube 影片 這裡
[], [],