今天是第一阶段最后一节课
今日内容:
一.排序算法
选择排序
对于n个无序的数列遍历n-1次, 每次选中剩余的数据的最小值, 放在对应的位置上
int data[5] = {9, 7, 3, 5, 1};
9 7 3 5 1
_ _ _ _ _
0 1 2 3 4 第一次遍历:从下标为1的数据, 找出数据最小的值的下标, 然后和下标为0的数据交换位置
1 7 3 5 9
_ _ _ _ _
0 1 2 3 4
最小的值为1, 下标是4
int tmp = data[0];
data[0] = data[4];
data[4] = tmp;
找到所有数据的最小值, 和下标为0的值做替换 第二次遍历 : 找出第二小的值, 和下标为1的位置做替换
1 3 7 5 9
_ _ _ _ _
0 1 2 3 4
最小的值为3, 下标为2
int tmp = data[1];
data[1] = data[2];
data[2] = tmp;
第三次遍历 : 找出剩余最小的值, 和下标为2的位置做替换
1 3 5 7 9
_ _ _ _ _
0 1 2 3 4
最下的值为5, 下标为3
int tmp = data[2];
data[2] = data[3];
data[3] = tmp;
第四次遍历 : 找出剩余最小的值, 和下标为3的位置做替换
1 3 5 7 9
_ _ _ _ _
0 1 2 3 4
最小的值为7, 下标为3 不再需要替换
1 5 3 2 7
1 5 3 2 7
1 2 3 5 7
1 2 3 5 7
快速排序 – 递归函数
例如:
0 10 80 30 60 50 40 70 20 90 100
思路 :
找出一个基准值, 其左边的数据小于他, 他右边的数据大于他
第一次实现 : 让数据50作为基准值, 进行依次分组,
把比50小的数据放在其左边, 把比50大的数据放在其右边
第二次实现:
对50左边的数据分组 对50右边的数据分组
对50左边的数据分组 -> 以30为基准
对50右边的数据分组 -> 以90为基准
第三次实现:
对30的左边分组 -> 10
对90的左边分组 -> 70
直到剩余最后一个或者没有 - 无需分组 以50为基准 : 0 10 30 40 20 <50> 80 60 70 90 100
30,90为基准 : 0 10 20 <<30>> 40 <50> 80 60 70 <<90>> 100
10,70为基准 : 0 <10> 20 <<30>> 40 <50> 60 <70> 80 <<90>> 100
0, 10, 20 – 看起来不需要 – 实际上需要
xx, xx, xx – 三个数据, 比30小
通过三个游标来实现:
定义三个游标来实现原地分组
pivot = 基准值
int i = 0;//左边界
int j = size – 1;//右边界
int pivot = data[p];//将基准值备份到pivot变量中, 基准值的下标为p
pivot = 50;//存储了基准值
0 10 80 30 60 50 40 70 20 90 100
i
p
j for(; !(i>=p || pivot < data[i]); i++); i >= p -> 假
pivot < data[i] -> 假
当ip || data[i] > pivot
data[i] > pivot -> 该条件成立
data[p] = data[i];
p = i;
0 10 80 30 60 80 40 70 20 90 100
i
p
j
当j>p, data[j] > pivot, j–
何时不j–, j
该条件成立
data[p] = data[j];
p = j;
0 10 20 30 60 80 40 70 20 90 100
i
p
j
当ip || data[i] > pivot
data[p] = data[i];
p = i;
0 10 20 30 60 80 40 70 60 90 100
i
p
j
当j>p, data[j] > pivot, j–
何时不j–, j
该条件成立
data[p] = data[j];
p = j;
0 10 20 30 40 80 40 70 60 90 100
i
p
j
i变化 – j变化 – i变化 ….
0 10 20 30 40 80 80 70 60 90 100
i
p
j
停止, 直到i=p=j, 此时就是基准值应该在的位置
data[p] = pivot;
0 10 20 30 40 50 80 70 60 90 100
i
p
j
i变化, j变化, i变化, j变化, …
0 10 20 30 40 50 80 70 60 90 100
0 1 2 3 4 5 6 7 8 9 10
l p r
left right
p - left > 1 -> 基准值p左边的数据大于1个 排序
right - p > 1 -> 基准值p右边的数据大于1个 排序 二.查找算法
线性查找
在数列中挨个匹配要查找的数据, 对于数据的有序性没有要求
mkdir find
vim find.h
vim find.c
vim sort.h
vim sort.c
vim main.c
折半查找 – 二分查找 – 递归函数
前提 – 数据必须有序, 无序则先排序
让数列对半分, 拿着目标值和中间值进行比较
相等 – 返回下标
目标值 > 中间值 -> 右侧继续二分查找
目标值 < 中间值 -> 左侧继续二分查找
10 20 30 40 50 60 70
0 1 2 3 4 5 6
l m-1 mid m+1 r
10 20 30 40 50
0 1 2 3 4
l m-1 mid m+1/r int recu_find(int data[], int left, int right, int key){
}
60 -> 中间值
