- 1 数学模型
- 1.1 O (天花板！嘿嘿)
- 1.1.1 o(永远够不到的天花板！)
- 1.2 Ω (地板砖！嘿嘿)
- 1.2.1 ω (永远踩不到的地板砖)
- 1.3 Θ (夹在中间)
- 2 插入排序法
- 3 代码实现
- 3.1 对int型数组排序
- 3.1.1 实现
- 3.1.2 测试例程
- 3.2 泛型编程
- 3.2.1 排序算法主体
- 3.2.2 添加对int的支持
- 3.2.3 添加对float的支持
- 3.2.4 测试例程
O mathrm{O} O 的作用，对一个多项式：
- （1）去掉低阶项和常数，仅保留最高阶这一项；
- （2）去掉最高阶的系数；
数学定义：
f
(
n
)
=
O
[
g
(
n
)
]
⟹
f
(
n
)
∈
O
[
g
(
n
)
]
f(n)=mathrm{O}[g(n)] Longrightarrow f(n) in mathrm{O}[g(n)]
f(n)=O[g(n)]⟹f(n)∈O[g(n)]
∃ c > 0 , n 0 > 0 , 使 得 : ∀ n ≥ n 0 , 有 0 ≤ f ( n ) ≤ c ⋅ g ( n ) exist c>0, n_0>0, 使得: forall n ge n_0, 有 0 le f(n) le c·g(n) ∃c>0,n0>0,使得:∀n≥n0,有0≤f(n)≤c⋅g(n)
这里的
O
[
g
(
n
)
]
mathrm{O}[g(n)]
O[g(n)] 是个函数集！跟不定积分
∫
f
(
x
)
d
x
=
F
(
x
)
+
C
int f(x)dx=F(x)+C
∫f(x)dx=F(x)+C
是一个道理！
数学定义：
f
(
n
)
=
o
[
g
(
n
)
]
⟹
f
(
n
)
∈
o
[
g
(
n
)
]
f(n)=mathrm{o}[g(n)] Longrightarrow f(n)inmathrm{o}[g(n)]
f(n)=o[g(n)]⟹f(n)∈o[g(n)]
∃
n
0
>
0
,
使
得
:
∀
n
≥
n
0
,
∀
c
>
0
,
有
0
≤
f
(
n
)
<
c
⋅
g
(
n
)
exist n_0>0, 使得: forall n ge n_0, color{red} forall c>0color{end}, 有 0 le f(n) color{red} 数学定义：
∃
c
>
0
,
n
0
>
0
,
使
得
:
∀
n
≥
n
0
,
有
0
≤
c
⋅
g
(
n
)
≤
f
(
n
)
exist c>0, n_0>0, 使得: forall n ge n_0, 有 0 le c·g(n) le f(n)
∃c>0,n0>0,使得:∀n≥n0,有0≤c⋅g(n)≤f(n) 数学定义：
∃
n
0
>
0
,
使
得
:
∀
n
≥
n
0
,
∀
c
>
0
,
有
0
≤
c
⋅
g
(
n
)
<
f
(
n
)
exist n_0>0, 使得: forall n ge n_0, color{red} forall c>0color{end}, 有 0 le c·g(n) color{red} 数学定义：
f
(
n
)
∈
O
[
g
(
n
)
]
⋂
Ω
[
g
(
n
)
]
f(n)in mathrm{O}[g(n)] bigcap Omega[g(n)]
f(n)∈O[g(n)]⋂Ω[g(n)]
∃
c
1
>
0
,
c
2
>
0
,
n
0
>
0
,
使
得
:
∀
n
≥
n
0
,
有
c
1
⋅
g
(
n
)
≤
f
(
n
)
≤
c
2
⋅
g
(
n
)
exist c_1>0, c_2>0, n_0>0, 使得: forall n ge n_0, 有 c_1·g(n) le f(n) le c_2·g(n)
∃c1>0,c2>0,n0>0,使得:∀n≥n0,有c1⋅g(n)≤f(n)≤c2⋅g(n)
f
(
n
)
=
Ω
[
g
(
n
)
]
⟹
f
(
n
)
∈
Ω
[
g
(
n
)
]
f(n)=Omega[g(n)] Longrightarrow f(n)in Omega[g(n)]
f(n)=Ω[g(n)]⟹f(n)∈Ω[g(n)]
f
(
n
)
=
ω
[
g
(
n
)
]
⟹
f
(
n
)
∈
ω
[
g
(
n
)
]
f(n)=omega[g(n)] Longrightarrow f(n)in omega[g(n)]
f(n)=ω[g(n)]⟹f(n)∈ω[g(n)]
f
(
n
)
=
Θ
[
g
(
n
)
]
⟹
f
(
n
)
∈
Θ
[
g
(
n
)
]
f(n)=Theta[g(n)] Longrightarrow f(n)in Theta[g(n)]
f(n)=Θ[g(n)]⟹f(n)∈Θ[g(n)]typedef enum _tagSortDirection{
DIR_UP,
DIR_DOWN,
}SortDirTypeDef;
void intArray_InsertionSort(int *arr, int len, SortDirTypeDef dir)
{
if(dir == DIR_UP){
for(int j = 1; j < len; j++){ // outer-loop, 目的：实现已排序部分的增量！
int key = arr[j];
int i = j; // 如果将 i 定位到 j-1，下面这个循环体，会使得最差情况 i 降到 -1
while(i>0 && arr[i-1]>key){ // 要差要测试到arr[0]>key上，所以 i 最小会到 -1
arr[i] = arr[i-1];
i--;
}
arr[i] = key; // 确保了 i>0
}
}else{
for(int j = 1; j < len; j++){ // outer-loop, 目的：实现已排序部分的增量！
int key = arr[j];
int i = j;
while(i>0 && arr[i-1]
3.1.2 测试例程
int i_arr[] = {32, 33, 2, 1, 0, 8, -52, -9, -100, 65, 0, 25, -98};
void intArrayPrint(int *arr, int len)
{
int i;
printf(">>> data is: rn");
for(i = 0; i < len; i++){
printf("|%-6d", arr[i]);
if((i+1) % 8 == 0){
printf("|rn");
}
}
if(i % 8 != 0){
printf("|rn");
}
}
int main(int argc, char *argv[])
{
intArrayPrint(i_arr, sizeof(i_arr)/sizeof(int));
intArray_InsertionSort(i_arr, sizeof(i_arr)/sizeof(int), DIR_UP);
intArrayPrint(i_arr, sizeof(i_arr)/sizeof(int));
intArray_InsertionSort(i_arr, sizeof(i_arr)/sizeof(int), DIR_DOWN);
intArrayPrint(i_arr, sizeof(i_arr)/sizeof(int));
return 0;
}
3.2 泛型编程
3.2.1 排序算法主体
void InsertionSort(void *arr, int len, int elemSize, int (*cmpFn)(void *, void*, SortDirTypeDef), SortDirTypeDef dir)
{
int j; // outer-loop control variable
int i; // inner-loop control variable
void *key; // 开辟实体空间，保存待插入有序列表的数据
void *elemAddr; // 记录: 遍历inner(有序列表)时候，与key比较的元素的地址！
void *elemNextAddr; // 记录: 遍历inner(有序列表)时候，与key比较的元素的后一位的地址
void *insertAddr; // 记录: 有序列表中，待插入的位置的地址
key = malloc(elemSize); // 必须要开辟“实体空间”，存储数据
for(j = 1; j < len; j++){
// void *key = (char *)arr + j * elemSize; // 这是有问题的！指针，指向一块存储空间，它本身并没有实体！保存不了数据
memcpy(key, (char *)arr + j * elemSize, elemSize); // 待插入前部分有序列表的元素的地址 ==> key = arr[j]
i = j;
elemAddr = (char *)arr + (i-1) * elemSize; // inner-loop 遍历过程中每个元素的地址 ==> arr[i-1]
while (i>0 && (cmpFn(elemAddr, key, dir) > 0)){ // 升序 cmpFn() >= 1 执行循环体，否则不执行
elemNextAddr = (char *)arr + i * elemSize; // arr[i]
memcpy(elemNextAddr, elemAddr, elemSize); // ==> arr[i] = arr[i-1]
i--; // 向前，向前，向前！
elemAddr = (char *)arr + (i-1) * elemSize; // arr[i-1]
}
insertAddr = (char *)arr + i * elemSize; //计算有序列表中的插入地址
memcpy(insertAddr, key, elemSize);
}
free(key);
}
3.2.2 添加对int的支持
int Insertion_IntCmp(void *elem1, void *elem2, SortDirTypeDef dir)
{
int *ip1 = (int *)elem1;
int *ip2 = (int *)elem2;
if(dir == DIR_UP){
return (*ip1 - *ip2);
}else{
return (*ip2 - *ip1);
}
}
3.2.3 添加对float的支持
int Insertion_FloatCmp(void *elem1, void *elem2, SortDirTypeDef dir)
{// 保留2位有效数字即可！
float *fp1 = (float *)elem1;
float *fp2 = (float *)elem2;
if(dir == DIR_UP){
return (int)(*fp1 - *fp2 + 0.999); // +0.999 实现小数向上取整，这样才能可以！ 0.2-0.1 = 0.1 --> 1 // -0.5-(-0.6) = 0.1 --> 1 // -0.6 - (-0.5) = -0.1 --> 0
}else{// 注意 +0.5 是四舍五入
return (int)(*fp2 - *fp1 + 0.999);
}
}
3.2.4 测试例程
float f_arr[] = {
0.01, 0.05, 0.15, 0.16, 6.25,
2.25, 2.0, 0.5, -5.2, -8.0,
-52.2, 0.7, -100.0, 65.2, 0,
25.2, -98.2};
void floatArrayPrint(float *arr, int len)
{
int i;
printf(">>> data is: rn");
for(i = 0; i < len; i++){
printf("|%-6.2f", arr[i]);
if((i+1) % 8 == 0){
printf("|rn");
}
}
if(i % 8 != 0){
printf("|rn");
}
}
int main(int argc, char *argv[])
{
floatArrayPrint(f_arr, sizeof(f_arr)/sizeof(float));
InsertionSort(f_arr, sizeof(f_arr)/sizeof(float), sizeof(float), Insertion_FloatCmp, DIR_UP);
floatArrayPrint(f_arr, sizeof(f_arr)/sizeof(float));
InsertionSort(f_arr, sizeof(f_arr)/sizeof(float), sizeof(float), Insertion_FloatCmp, DIR_DOWN);
floatArrayPrint(f_arr, sizeof(f_arr)/sizeof(float));
return 0;
}
