]]>
Q本文假讑֝标系为左手坐标系中，旋{方向为顺旉。）
所求问题：
l定L单位轴q(向量),求向量p(x,y,z)(或点p)饶q旋{theta角度的变换后的新向量p'(或点p')Q?/strong>
1.用四元数工具Q?br />-------------------------------------------------------------------------
l论Q构造四元数变换p'= q*p*q-1Q（p,q是由向量p,q扩展成的四元敎ͼ。那么，p'转换臛_应的向量(或点)是变换后的新向量p'(或点p')?/p>
其中Qp',q,p,q-1均ؓ四元数。q由向量q扩展,为q=(cos(theta/2),sin(theta/2)*q)Qp由向量p扩展,为p=(0,x,y,z),q-1为q的逆，因ؓq为单位四元数Q所以q-1=q*=(cos(theta/2),-sin(theta/2)*q)?br />-------------------------------------------------------------------------
Q这个结论的证明q程可以在网上找到。这里略厅R）
下面看其旉复杂度：
首先有个三角函数的计时_q个可以预先计算好，p旉不计。考虑n个四元数怹需q行4*4*(n-1)=16*(n-1)ơ乘法，15*(n-1)ơ加法，因ؓ加法化费旉较少Q这里仅考虑乘法。这里涉及到三个四元数的乘法Q设一ơ乘法的旉为T,故花?6*2=32T
2.旋{矩阵工具Q?/strong>
-------------------------------------------------------------------------
l论Q构造旋转矩阵变换Trot,则变换后的新向量p'(或点p')为p'= p*Trot
其中Qp'Qx',y',z',1Q?p(x,y,z,1)为向量p'Qp?D齐次坐标表示QTrot =
|t*x*x + c, t*x*y + s*z, t*x*z - s*y, 0|
|t*x*y - s*z, t*y*y + c, t*y*z + s*x, 0|
|t*x*z + s*y, t*y*z - s*x, t*z*z + c, 0|
|0, 0, 0, 1|
c=cos(theta), s=sin(theta),t=1-c.
-------------------------------------------------------------------------
Q这个结论的证明q程可以在网上找到。这里略厅R）
下面看其旉复杂度：
三角函数的计时间不计。矩阉|w的元素乘法主要是计t*x和s*x之类Q需q行12+3=15ơ乘法。两个矩늛乘的需q行n*n*nơ乘?q里n=4Q所以花?*4*4=64ơ乘法时?但这里有个注意的地方是旋{矩阵的第4l无考虑Q即可简化ؓ3X3的矩c故p3*3*3=27ơ乘法时_d的时间ؓ15+27=42ơ乘法时间。cost=42T.
比较来看Q还是用四元数的效率要高出一些，q在要变换的点的数目大Ӟ体现的越明显。实际上Q有很多3D引擎Z利用四元数运的高效率性，一般先矩阵{换成四元数后q行q算再{回ؓ矩阵后，再传lDirectX或OpenGL库函数?br />
关于四元数和矩阵在向量（方向Q之间的q行插值的效率比较Q见下篇Q?br />探讨Q物体绕L向量的旋?四元数法VS.旋{矩阵法的性能比较
]]>
1.相机I间到视q面的变?br />2.视^面到屏幕的变?br />3.l合
4.一般情?br />
1.相机I间到视q面的变?/font>
* p (xc,0, zc)
/ |
/ |
/ |
X |/ |
^ *p' |(xp,0,zp)
| / | |
| / | |
| / | |
C(cam) |/ | |
--------*----|----*------------->Z
0 dx zc
(X-Zq面的投q?
a.透视投媄一般的视景体ؓ台Q相机空间的物体会投影到视^面z=dQ这里考虑左手坐标p，矩阵使用行优先方式。如图所C，qg角Ş知识可知相机I间中的物体投媄到视q面上的坐标为：
xp = xc*(dx/zc)
yp = yc*(dy/zc)
其中,xc,yc,zc为相机空间坐?xp,yp,zpq面坐标QdxQdy为x,y轴向的视距view distanceQ视q面到camera的距?
故相机空间投影到视^面上的矩阵Tcp为：
|dx 0 0 0 |
|0 dy 0 0 |
|0 0 1 1 |
|0 0 0 0 |
(验证:Tcp右乘点p(xc,yc,zc,1)得点p'(xc*dx, yc*dy, zc, zc),转换?D坐标?xc*dx/zc, yc*dy/zc, 1),正确?
********************************************************************
注：因ؓ转换q程中点使用的是4D齐次坐标,所以最后需转换?D坐标?D齐次坐标(x,y,z,w)转换?D坐标的方法ؓ除以w分量Q即对应3D坐标?x/w,y/w,z/w)?br />********************************************************************
考虑dx/zc和dy/zc，如果dx != dy,则投影后x,y的比例会发生变化Q原因：投媄前坐标比例ؓxc/yc,投媄后ؓxp/yp = xc*(dx/zc)/yc*(dy/zc) = xc*dx/yc*dyQ，从而投影后的图像的x,y比例会发生变形?br />
---------------------------------------------
l论1Q所以，一般都会od=dx=dy,即x,y向的视距相同。否则，囑փq?br />---------------------------------------------
考虑视角Qview angle,或视野filed of viewQ的问题Q视角的大小不会影响到物体投影后的坐标，只会影响可视的范围?/p>
在视距一L情况下，x,y轴的视角可以不一栗如果一P那么视^面就是一个正方Ş的。于是有Q?/p>
tan(theta_x/2) = width_p/d
tan(theta_y/2) = height_p/d
其中Qtheta_xQtheta_y为x,y轴向的视角，width_pQheight_pq面z=d的宽度（x_和高?y??br />----------------------------------------------------------------
l论2Q视q面的宽高比rp=width_p/height_p = tan(theta_x/2)/tan(theta_y/2)?br />----------------------------------------------------------------
2.视^面到屏幕的变?/font>
下面是视^面到屏幕的变换了Q这是一?D?D的变换（视^面的坐标需伸羃以填满整个屏q空?卛_视^面中出现的所有的点要变换到屏q上去，同时x,y轴向的比例还要维持和变换前一P以免比例qQ同时视q面的坐标原点和屏幕中心点（x0=(width_s)/2, y0=(height_s)/2Q对应）Q其实，是一个坐标羃攑֊q移的过E?
xs = xp*kx + x0
ys = -yp*ky + y0
矩阵Tps为：
|kx 0 0 0 |
|0 -ky 0 0 |
|0 0 1 0 |
|x0 y0 0 1 |
(验证:Tps右乘点p(xp,yp,zp,1)得点p'(xp*kx + x0, -yp*ky + y0, zp, 1),转换?D坐标?xp*kx + x0, -yp*ky + y0, zp)Q正?
其中Qkx,ky(kx>0,ky>0)为x,y轴向的羃攑֛子（kx=(width_s)/(width_p)Q?ky = (height_s)/(height_pQ，和视距相同，kx,ky的值必MP否则囑փ的x,y比例又会发生变Ş。这?yp*ky是因Z般屏q的y轴是向下的，跟相机空间和视^面坐标系中的y轴方向相反?br />------------------------------------------------------------------------------------------------
l论3: 一般ok=kx=kyQ即x,y向的~放因子相同。否则，囑փq?br />于是有，width_s/width_p = height_s/height_pQ变化等式得Qrp = width_p/height_p = width_s/height_s = rs
所以，在x,y轴视距一L情况下，要想最后变换到屏幕上的囑փx,y比例不失真，必须rp=rs,卌q面的宽高比和屏q的宽高比一栗?/strong>
-----------------------------------------------------------------------------------------------
********************************************************************
注：若屏q宽高ؓW,HQ当W != HQ即屏幕不ؓ方Ş的时候，要确保投影到屏幕上的囑փx,y比例不失真，则x,y轴视?或视野FOV)肯定不能相等?
原因Q?q?,3知，rp=width_p/height_p = tan(theta_x/2)/tan(theta_y/2)=width_s/height_s=rs=W/H?故由W/H != 1 => theta_x != theta_Y.
********************************************************************
3.l合Q?/font>
相机I间点p转换到屏q空间点p'Q变换公式ؓQ?/p>
xs = xc*(dx/zc)*kx + x0 = xc*(d/zc)*k + x0
ys = -yc*(dy/zc)*ky + y0 = -yc*(d/zc)*k + y0
l合变换矩阵(相机I间到屏q空?Tcs为：
Tcs = Tcp*Tps =
|d*k 0 0 0 |
|0 -d*k 0 0 |
|x0 y0 1 1 |
|0 0 0 0|
其中Qd距，k为屏q宽高比或视q面宽高比，x0,y0为屏q中心，注：最后需转换?D坐标?/p>
(验证:Tcs右乘点p(xc,yc,zc,1)得点p'(xc*d*k + x0*zc, -yc*d*k + y0*zc, zc, zc),转换?D坐标?xc*(d/zc)*k + x0, -yc*(d/zc)*k + y0, 1)Q正?
4.一般情形：
************************************
视距?Qx轴视角ؓ90度，屏幕宽高为W,H.
************************************
代入d=1Qtheta_x = PI/2,x0= W/2,y0=H/2,则视q面宽高为width_p = 2?br />要确保屏q上的图像x,y比例不失真，即rs=rp,?br />height_p = 2/rp=2/rs=2H/W,
k=kx=ky=width_s/width_p = W/2.
于是,矩阵?
Tcs1 =
|W/2 0 0 0 |
|0 -W/2 0 0 |
|W/2 H/2 1 1 |
|0 0 0 0 |
?br />
|W/2 0 0 0 |
|0 -H/2*(W/H) 0 0 |
|W/2 H/2 1 1 |
|0 0 0 0 |
(可以看到Qy轴的~放因子中乘上了宽高?aspect ratio))
q个矩阵较常用?br />
---------------------
有什么问?Ƣ迎探讨.
]]>
单测试了下，应该没问题?br />We have 4 kinds of blocks, they are:
(1,1,1)
(1,2,3)
(2,3,4)
(2,3,2)
Building the tower of babylon...
The max height of tower is: 18.
Totally 7 blocks are used, they are:
(1) block (1,1,1), area = 1
(2) block (1,2,3), area = 2
(3) block (1,2,3), area = 3
(4) block (2,3,2), area = 4
(5) block (2,3,4), area = 6
(6) block (2,3,4), area = 8
(7) block (2,3,4), area = 12
------------------------------------
TowerOfBabylon.cpp:
------------------------------------
//
// File: [TowerOfBabylon.cpp]
// Description:[This program illustrates how to get the Tower Of Babylon. the Tower Of Babylon: Given N kinds of blocks,
// you need to buid the tower under the condition that every upper block's area should less than the lower one.]
// Author:[SoRoMan]
// Date:[2006-08-08]
// Version:[2.0]
// History: [1.0: initial draft.
// 2.0: add a new type TOWER
// 3.0: chnage the sequence data structure to list structure to avoid memory access violation.]
//
// INCLUDES //////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "malloc.h"
// DEFINES //////////////////////////////////////////////////////////////////////////
#define N 4
// TYPES //////////////////////////////////////////////////////////////////////////
typedef struct BLOCK_TYP
{
int x,y,z;
int area;
int height;
BLOCK_TYP *pNext;
} BLOCK, *BLOCK_PTR;
typedef struct TOWER_TYP
{
int height;
int num_block;
BLOCK_PTR pTowerTop;
} TOWER, *TOWER_PTR;
// PROTOTYPES //////////////////////////////////////////////////////////////////////////
TOWER_PTR BuildTower(BLOCK_PTR pBlock, int n);
// FUNCTIONS //////////////////////////////////////////////////////////////////////////
int main(int argc, wchar_t* argv[])
{
BLOCK blocks[N] = {{1,1,1},{2,2,2},{3,3,3},{4,4,4}};
printf("We have %d kinds of blocks, they are:\n", N);
int i;
for(i = 0; i < N; i++)
{
printf("(%d,%d,%d)\n", blocks[i].x, blocks[i].y, blocks[i].z);
}
printf("Building the tower of babylon...\n");
TOWER_PTR pT = BuildTower(blocks, N);
printf("The max height of tower is: %d.\nTotally %d blocks are used, they are:\n", pT->height, pT->num_block );
BLOCK_PTR pBlock = pT->pTowerTop;
for(i = 0; i < pT->num_block; i++)
{
printf("(%d) block (%d,%d,%d), area = %d, height = %d\n", i+1, pBlock->x, pBlock->y, pBlock->z, pBlock->area, pBlock->height);
pBlock = pBlock->pNext;
}
getchar();
return 0;
}
////////////////////////////////////////////////////////////////////////////////
// Algorithm of building the Tower Of Babylon.
// Input Parameters: pBlock: pointer variable that identifies blocks sequence.
// n: int variable that identifies how many kinds of blocks.
// Output Parameters: None.
// Return: pointer variable that identifies the built tower.
////////////////////////////////////////////////////////////////////////////////
TOWER_PTR BuildTower(BLOCK_PTR pBlock, int n)
{
int index_block = 0;
TOWER_PTR pTower = new TOWER();
BLOCK_PTR pTop = new BLOCK();
pTower->pTowerTop = pTop;
// initialize tower
pTower->pTowerTop->x = pBlock->x;
pTower->pTowerTop->y = pBlock->y;
pTower->pTowerTop->z = pBlock->z;
pTower->pTowerTop->area = (pBlock->x)*(pBlock->y);
pTower->pTowerTop->height = pBlock->z;
pTower->height = pTower->pTowerTop->height;
pTower->num_block = 1;
for(int i = 1; i < 3*n; i++)
{
index_block = i/3;
if (i%3 == 0) // condition 1, area = x*y, height = z.
{
(pBlock+index_block)->area = ((pBlock+index_block)->x)*((pBlock+index_block)->y);
(pBlock+index_block)->height = (pBlock+index_block)->z;
}
else if (i%3 == 1) // condition 2, area = x*z, height = y.
{
(pBlock+index_block)->area = ((pBlock+index_block)->x)*((pBlock+index_block)->z);
(pBlock+index_block)->height = (pBlock+index_block)->y;
}
else // condition 3, area = y*z, height = z.
{
(pBlock+index_block)->area = ((pBlock+index_block)->y)*((pBlock+index_block)->z);
(pBlock+index_block)->height = (pBlock+index_block)->x;
}
bool bNeedToBeAdded = true;
BLOCK_PTR pB = pTower->pTowerTop;
BLOCK_PTR pPrev = pTower->pTowerTop;
while(pB != NULL)
{
if ((pBlock+index_block)->area < (pB->area))
{
// insert new block
BLOCK_PTR pNewBlock = new BLOCK();
*pNewBlock = *(pBlock+index_block);
if(pB == pPrev)
{
pNewBlock->pNext = pB;
pTower->pTowerTop = pNewBlock;
}
else
{
pNewBlock->pNext = pPrev->pNext;
pPrev->pNext = pNewBlock;
}
// increase number of blocks
pTower->num_block++;
// increase height of tower
pTower->height += (pBlock+index_block)->height;
bNeedToBeAdded = false;
break;
}
else if ((pBlock+index_block)->area == (pB->area))
{
if (pB->height < ((pBlock+index_block)->height))
{
// increase height of tower
pTower->height += (pBlock+index_block)->height - pB->height;
// replace blocks
BLOCK_PTR pNewBlock = new BLOCK();
*pNewBlock = *(pBlock+index_block);
if (pB == pPrev)
{
pNewBlock->pNext = pB->pNext;
pTower->pTowerTop = pNewBlock;
}
else
{
pNewBlock->pNext = pB->pNext;
pPrev->pNext = pNewBlock;
}
}
bNeedToBeAdded = false;
break;
}
pPrev = pB;
pB = pB->pNext;
}
if(bNeedToBeAdded)
{
// add new block at the end
BLOCK_PTR pNewBlock = new BLOCK();
*pNewBlock = *(pBlock+index_block);
pPrev->pNext = pNewBlock;
pNewBlock->pNext = NULL;
// increase number of blocks
pTower->num_block++;
// increase height of tower
pTower->height += (pBlock+index_block)->height;
}
}
return pTower;
}
]]>
一般左叛_标系的定义是q样说的Q?/strong>
在左手坐标系中，坐标轴的定义W合左手法则Q左手四个手指的旋{方向从X轴到Y_大拇指的指向是Z轴。但是没有给出数学上的定义。参考一些资?关于左右坐标pȝ定义Q涉及到向量叉积与左叛_标系的关pR?br />
从基说vQ?/strong>
基是nl的Ƨ式I间中的一l线性无关的向量V0,V1,...,Vn-1。关于线性无兛_量组的定义可以去参考其他资料?br />
Z坐标pȝ关系Q?br />如果一个基的行列式为正Q那么它可以Ş成一个右手坐标系。如果ؓ负则形成左手坐标pR?br />
向量叉积与三l左叛_标系的关p：
那么向量叉积与左叛_标系的关pL什么关pdQ由Z坐标pȝ关系可以推知Q比如在三维Ƨ式I间中，设有一个基Q向量组Q?Vx,Vy,Vz)存在Q那么我们知道行列式的表辑ּ|Vx,Vy,Vz|=(Vx*Vy).Vz,可以得知Q当向量Vz的方向与向量Vx*Vy(Vx与Vy的叉U?的夹角在0-PI/2之间的时候，׃定会?Vx*Vy).Vz>0Q那么由基（向量l）Vx,Vy,Vzl成的坐标系׃ؓx坐标pR其实，说白了，是向量叉积的方向规定了左右坐标pȝ定义?br />
三维x,y,z左右手坐标系特例Q?/strong>
令三l欧式空间空存在三向量Vx=QxQ?Q?Q?x>0)QVy=Q?QyQ?Q?y>0)QVz=Q?Q?QzQ（注：q里规定z轴的正方向和向量Vx*Vy的方向一致。）此时Q向量Vx*Vy的方向是W合x坐标pȝQ因为向量Vx*Vy的方向与其自w的夹角?Q由(Vx*Vy).Vz = xyz可知Q当z>0Ӟ该向量组Q（xQ?Q?Q，Q?QyQ?Q，Q?Q?QzQ）构成x坐标pR反之，若z<0Q那么由(Vx*Vy).Vz = xyz<0可知Q该向量l（QxQ?Q?Q，Q?QyQ?Q，Q?Q?QzQ）构成左手坐标pR特例：Q?Q?Q?Q，Q?Q?Q?Q，Q?Q?Q?Q构成右手坐标系Q（1Q?Q?Q，Q?Q?Q?Q，Q?Q?Q?1Q构成左手坐标系?/p>
]]>
// File: [TestSort.cpp]
// Description:[This file illustrate the sort methods. Make sure the length of the sequence consistent with its contents!]
// Author:[SoRoMan]
// Date:[07/31/2006]
// Version:[1.0]
// History: []
//
// INCLUDES ///////////////////////////////////////////////
#include "stdio.h"
// DEFINES ////////////////////////////////////////////////
#define N 11
// PROTOTYPES /////////////////////////////////////////////
void QuickSort(int *seq, int lenght);
void InsertSort(int *seq, int lenght);
void InsertSort2(int *seq, int lenght);
void ShellSort(int *seq, int lenght);
void IncrementInsertSort(int *seq, int length, int increment);
void HeapSort(int *seq, int length);
void SelectionSort(int *seq, int length);
void BubbleSort(int *seq, int length);
void BiBubbleSort(int *seq, int length);
void AdjustHeap(int *seq, int startIndex, int endIndex);
// GLOBALS ////////////////////////////////////////////////
int nAssignmentOperation = 0; // assignment counter
int nComparsionOperation = 0; // comparsion counter
// FUNCTIONS //////////////////////////////////////////////
int main(int argc, char* argv[])
{
printf("0: Original Sequence\n");
printf("1: Quick Sort\n");
printf("2: Insert Sort\n");
printf("3: Shell Sort\n");
printf("4: Insert Sort2\n");
printf("5: Heap Sort\n");
printf("6: Selection Sort\n");
printf("7: Bubble Sort\n");
printf("8: Bi-Bubble Sort\n");
printf("-1: Exit\n");
int cat = 0;
while (cat != -1)
{
// clear counter
nAssignmentOperation = 0;
nComparsionOperation = 0;
//int array[N] = {600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,
//600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1,600, 64,6,78,246,445,345,445,7,4885,1};
int array[N] = {600, 64,6,78,246,445,345,445,7745,4885,1};
printf("\nPlease select sort method:");
scanf("%d", &cat);
printf("-------------------------------------------------\n");
switch(cat)
{
case 0:printf("No Sort. The Original Sequence is\n");
break;
case 1:printf("Quick Sort\n"); QuickSort(array, N);
break;
case 2:printf("Insert Sort\n"); InsertSort(array, N);
break;
case 3:printf("Shell Sort\n"); ShellSort(array, N);
break;
case 4:printf("Insert Sort2\n"); InsertSort2(array, N);
break;
case 5:printf("Heap Sort\n"); HeapSort(array, N);
break;
case 6:printf("Selection Sort\n"); SelectionSort(array, N);
break;
case 7:printf("Bubble Sort\n"); BubbleSort(array, N);
break;
case 8:printf("Bi-Bubble Sort\n"); BiBubbleSort(array, N);
break;
default:printf("Exit...\n");
return 0;
}
for(int i = 0; i < N; i++)
{
printf("int = %d\n", array[i]);
}
printf("Count of comparsion operation = %d\n", nComparsionOperation);
printf("Count of assignment operation = %d\n", nAssignmentOperation);
printf("-------------------------------------------------\n");
}
return 0;
}
inline void Swap(int *pCurrPost, int *pCurrKey)
{
nAssignmentOperation += 3;
int temp;
//swap value
temp = *pCurrPost;
*pCurrPost = *pCurrKey;
*pCurrKey = temp;
}
////////////////////////////////////////////////////////////////////////////////
// Quick Sort algorithm. (By SoRoMan, 2006.7.31)
// 快速排序的基本思想是基于分ȝ略的。对于输入的子序列L[p..r]Q如果规模够小则直接进行排序（比如用前q的冒、选择、插入排序均可）Q否则分三步处理Q?br />// 1.分解(Divide)Q将待排序列L[p..r]划分Z个非I子序列L[p..q]和L[q+1..r]QL[p..q]中Q一元素的g大于L[q+1..r]中Q一元素的倹{具体可通过q样的途径实现Q在序列L[p..r]中选择数据元素L[q]Q经比较和移动后QL[q]处于L[p..r]中间的适当位置Q得数据元素L[q]的值小于L[q+1..r]中Q一元素的倹{?
// 2.递归求解(Conquer)Q通过递归调用快速排序算法，分别对L[p..q]和L[q+1..r]q行排序?
// 3.合ƈ(Merge)Q由于对分解出的两个子序列的排序是就地进行的Q所以在L[p..q]和L[q+1..r]都排好序后不需要执行Q何计L[p..r]已排好序，卌然合q?
// q个解决程是符合分L的基本步骤的。因此，快速排序法是分L的经典应用实例之一?br />// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void QuickSort(int *seq, int length)
{
if(length <= 1)
{
return;
}
else
{
int post = *seq; // set post
int *pCurrPost = seq; // set current position of post
int *pCurrKey; // current position of key
for(int j = length - 1, i = 1; i <= j;)
{
// handle the right sub-sequence
while(i <= j)
{
pCurrKey = seq + j;
if(*pCurrKey < post)
{
Swap(pCurrPost, pCurrKey);
pCurrPost = pCurrKey;
break;
}
else
{
j--;
}
nComparsionOperation ++;
}
// handle the left sub-sequence
while(i <= j)
{
pCurrKey = seq + i;
if(*pCurrKey > post)
{
Swap(pCurrPost, pCurrKey);
pCurrPost = pCurrKey;
break;
}
else
{
i++;
}
nComparsionOperation ++;
}
}
// handle two sub sequences recursively
int lleng = pCurrPost - seq; // left sub sequence
int rleng = length - lleng - 1; // right sub sequence
QuickSort(seq, lleng);
QuickSort(seq + lleng + 1, rleng);
}
}
////////////////////////////////////////////////////////////////////////////////
// Insert Sort algorithm (A special increment insert sort, increment = 1). (By SoRoMan, 2006.7.31)
//插入排序的基本思想是，l过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅L[i]插入L[1..i-1]的适当位置Q得L[1..i]又是排好序的序列。要辑ֈq个目的Q我们可以用序比较的方法。首先比较L[i]和L[i-1]Q如果L[i-1]?L[i]Q则L[1..i]已排好序Q第i遍处理就l束了；否则交换L[i]与L[i-1]的位|，l箋比较L[i-1]和L[i-2]Q直到找到某一个位|j(1≤j≤i-1)Q得L[j] ≤L[j+1]时ؓ止?br />//a?插入排序是每一步都一个待排数据按其大插入到已经排序的数据中的适当位置Q直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两U，q里只介l直接插入排序，折半插入排序留到“查䏀内容中q行
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void InsertSort(int *seq, int length)
{
IncrementInsertSort(seq, length, 1);
}
void InsertSort2(int *seq, int length)
{
for(int i = 1; i < length; i++)
{
for (int j = 0; j < i; j++)
{
if(*(seq + i) < *(seq + j))
{
int temp = *(seq + i);
nAssignmentOperation ++;
// insert, move (i-j) items
for(int k = i; k > j; k-- )
{
*(seq + k) = *(seq + k - 1);
nAssignmentOperation ++;
}
*(seq + k) = temp;
nAssignmentOperation ++;
nComparsionOperation ++;
break;
}
}
}
}
void IncrementInsertSort(int *seq, int length, int increment)
{
for(int k = 0; k < increment; k++)
{
for (int i = increment + k; i < length; i+=increment + k)
{
int temp = *(seq + i);
for (int j = i; j > increment - 1;)
{
nComparsionOperation ++;
if(temp > *(seq + j - increment))
{
*(seq + j) = *(seq + j - increment);
nAssignmentOperation ++;
j-=increment;
}
else
{
break;
}
}
*(seq + j) = temp;
nAssignmentOperation ++;
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Shell Sort algorithm (Increment insert sort, increment = increment/3 + 1.). (By SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void ShellSort(int *seq, int length)
{
for(int increment = length; increment > 1;)
{
increment = increment/3 + 1;
IncrementInsertSort(seq, length, increment);
}
}
////////////////////////////////////////////////////////////////////////////////
// Heap Sort algorithm. (SoRoMan, 2006.7.31)
//
//1.堆的概念Q?br />//堆是一个关键字序列{k1,k2,?kn},它具有如下特性：
//ki ≤k2i, ki ?k2i+1
//或ki ?k2i,ki ?k2i+1(i=1,2,? └n/2?
//堆的Ҏ在完全二叉树中解释为：完全二叉树中Ml点的关键字都小于等于（或大于等于）它的左右孩子的关键字?br />//如下列关键字序列均是堆： {5,23,16,68,94,72,71,73} (顶? {96,83,27,38,11,9} Q大堆Q?由堆的定义可知：若关键字序列{k1,k2,?kn}是堆Q则堆顶元素是n个元素序列中的最（或最大）元素?/p>
//2.基本思想Q?br />//首先初始待排序记录序列建堆Q则堆顶元素必ؓ含最大关键字或最关键字的记录，输出该记录，然后剩余记录再调整为堆Q如此反复，直至排序l束?br />//在堆排序主要需解决两个问题Q?br />//?如何建堆Q?在完全二叉树中，所有序号i>└n/2┘的l点都是叶子Q因此，以这些结点ؓ根的子树均已是堆Q这样只需以序号为└n/2? └n/2?1, └n/2?2,?1的结点ؓ栏V的子树都调整ؓ堆即可。在按此ơ序调整每个l点Ӟ其左、右子树均已是堆?br />//?若ki的左、右子树已经是堆Q如何将以ki为根的完全二叉树也调整ؓ堆？ 因ki的左、右子树已经是堆Q所以必dki 和它的左、右孩子中选出最（或最大）的结Ҏ到ki的位|上Q不妨设k2I关键字最，ki与k2I交换位置Q而交换之后有可能D以k2I为根的子树不再ؓ堆，于是可重复上q过E，以k2I为根的子树调整ؓ堆，…?如此逐层下去Q最多可能一直调整到树叶Q此ҎUCؓ"{选法"?/p>
//3.性能分析Q?br />//堆排序的旉主要由徏立初始堆和不断重复徏堆这两部分的旉开销构成。其中：建立初始堆时Qd需q行的关键字比较ơ数 ?4n =O(n) ;排序q程中进行n-1ơ重建堆所q行的L较次C过下式Q?2*(?log2(n-1) ??log2(n-2) ?? ?log22 ? < 2n ?log2n ?O(n log2n)因此堆排序ȝ旉复杂度是 O(n+ n log2n)= O(n log2n)?br />//堆排序在最坏情况下的时间复杂度也是O(nlog2n)Q相对于快速排序来_q是堆排序的最大优炏V?br />//另外Q堆排序仅需一个记录大供交换用的辅助I间。由于徏初始堆所需的比较次数较多，所以堆排序不适宜于记录较的文gQ但对n较大的文件还是很有效的?br />// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void HeapSort(int *seq, int length)
{
for(int n = length; n > 0; n--)
{
for(int j = n/2; j > 0; j--)
{
AdjustHeap(seq, j, n);
}
Swap(seq, seq+n-1);
}
}
void AdjustHeap(int *seq, int startIndex, int endIndex)
{
while(2*startIndex <= endIndex)
{
int i = startIndex - 1;
startIndex = startIndex*2;
nComparsionOperation ++;
if (startIndex < endIndex && *(seq + startIndex -1) < *(seq + startIndex))
{
startIndex++;
}
nComparsionOperation ++;
if(*(seq + startIndex -1) > *(seq + i))
{
Swap(seq + startIndex - 1, seq + i);
}
else
{
break;
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Selection Sort algorithm. (SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void SelectionSort(int *seq, int length)
{
for(int i = 0; i < length; i++)
{
int k = i;
for(int j = i+1; j < length; j++)
{
nComparsionOperation ++;
if (*(seq + j) < *(seq + k))
{
k = j;
}
}
Swap(seq + k, seq + i);
}
}
////////////////////////////////////////////////////////////////////////////////
// Bubble Sort algorithm. (SoRoMan, 2006.7.31)
// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void BubbleSort(int *seq, int length)
{
for(int i = 0; i < length; i++)
{
for(int j = length-1; j > i; j--)
{
nComparsionOperation ++;
if (*(seq + j) < *(seq + j - 1))
{
Swap(seq + j, seq + j - 1);
}
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Bi-Directinal Bubble Sort algorithm. (SoRoMan, 2006.7.31)
//思想Q?br />//Z在一排序中Q位于最后一ơ交换关键字的的后面的关键字序列已经是有序的Q所以不用再排序?br />//相对于一般的冒排序Q可以减关键字比较ơ数Q但交换ơ数不变?br />// Input Parameters: seq: pointer variable that identifies which sequence will be sorted.
// length: int that identifies the length of the sequence.
// Output Parameters: None.
// Return: None.
////////////////////////////////////////////////////////////////////////////////
void BiBubbleSort(int *seq, int length)
{
int k,low,up;
low = 0;
up = length-1;
while (up > low)
{
k = low;
for(int i = low; i < up; i++)
{
nComparsionOperation ++;
if (*(seq + i) > *(seq + i + 1))
{
Swap(seq + i, seq + i + 1);
k = i;
}
}
up = k;
for(int j = up; j > low; j--)
{
nComparsionOperation ++;
if (*(seq + j) < *(seq + j - 1))
{
Swap(seq + j, seq + j - 1);
k = j;
}
}
low = k;
}
}
]]>
Tool
Maya Basic
Maya Rendering Basic
Maya API/SDK
Library
OpenGL Basic
Theory
Computering Geometry
Real-Time Rendering
Graphic Algorithm
Draw
Draw Line
Draw Circle
Clip
Object Space
Image Space
Linear Math
To be continued...
]]>
]]>