Aros/开发者/游戏编程/基础

针对 Aros 维基教科书的导航栏

Aros 用户

Aros 用户文档

Aros 用户常见问题解答

Aros 开发文档

特定平台

Aros Intel AMD x86 安装

Aros 存储支持 IDE SATA 等

Aros Poseidon USB 支持

x86-64 支持

Motorola 68k Amiga 支持

Linux 和 FreeBSD 支持

Windows Mingw 和 MacOSX 支持

Android 支持

Arm Raspberry Pi 支持

PPC Power Architecture

杂项

Aros 公共许可证

简介

学会像程序员一样思考
学习 C C++
学习 AROS (Amiga) 的工作原理

第一个基本上是关于算法设计和要避免的事项。你是否知道“意大利面条代码”的含义？结构化编程？如何进行面向对象设计？大“O”符号？递归？快速排序？这些概念无论你使用什么语言或平台都非常重要。

游戏引擎系统相对于其他系统的定位

第 1 级 - C、C++ 基础
第 2 级 - 具有 OpenGL 框架的 SDL、具有 OpenGL 的 Raylib
第 3 级 - Godot 引擎、Ren'Py、GameMaker、Scratch、Unity、Unreal 等（AROS 没有）

游戏设计文档 GDD

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

AROS (Amiga)

当然，你需要学习在 Amiga 上编程。幸运的是，Amiga 是一台有趣的计算机，可以用相对较小的 API 进行编程。也就是说，你不会被操作系统调用淹没，但是，也有一些糟糕的部分。如果你只想打开一个窗口并创建一些按钮，那很简单。想编写一个网络浏览器吗？那会很困难，主要是因为操作系统没有提供你需要的很多东西，所以你最终会自己编写。 :-)

2D

设置图块、遮罩、平台相关内容等
双缓冲用于移动对象精灵（碰撞）或滚动
2D 框架，它承担了编写你自己的例程（如 SDL1.2）或 raylib5 的部分工作
从以下每个游戏类型中至少创建一个：棋盘/网格、迷宫、卡片等，以积累经验

SDL youtube 视频

碰撞盒
旋转
重力
阻力 - 弹簧阻尼质量模型
区域划分艺术资产
使用 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 */
             }
        }
}

2.5D 计算距离/深度

透视变换（透视投影 == 除以 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

3D

单路线（困难且耗时）？？并使用 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]

将 2D 纹理映射到 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 星

A*（A 星）算法从给定的起点移动到给定的目的地网格中。它所做的每一步都存储在一个节点中。在这个节点数据结构中存储了三个值

从起点开始的当前块的坐标
从该块到终点的距离（不同的方法，曼哈顿距离、对角线距离、欧几里得距离（可选的平方版本））
以及该块的父块（用于以后的回溯模式）

当算法向目的地移动时，它将这些节点存储到两个堆栈中：打开堆栈和关闭堆栈。一旦到达目的地块，我们就通过节点回溯（使用指向父节点的指针），我们就有了描述的路径

Youtube 视频在这里和在这里

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、理论，

更简单的语言介绍

Javascript - [1]、[2]、[3]、[4]、[5]、[6]、[7]，
Lua - Love2D，
HTML5、[8]，
可移植

C 及其同伴

C
C++ [9]

学习 C 并不难，学习如何正确使用它可能很困难。C 的语法虽然简洁，但非常简单。您可以在几张纸上描述整个 C 语言，它没有太多内容。但是，正如我的教授总是告诉我的那样，C 给您足够的绳索来把自己（以及周围的所有人）吊死。基本上，C 相信您知道自己在做什么，如果您告诉它破坏内存，它会很乐意为您做到。C 不会像 Basic 一样牵着您的手，但它会为您提供比任何其他语言都更强大的功能和灵活性。总之，我对所有 C 新手最好的建议是研究指针。当你认为自己理解指针时，再学习它们一些。这是 C 中让人生畏的部分之一。

在 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 视频这里

[], [],

用途