1.顺序表的查找
所谓顺序表，特点是相邻记录的物理位置也是相邻的。
1)顺序查找
算法思路：给定一个key值，在表中顺序对比，若存在k = key，则查找成功，返回记录序号，或者成功1，失败返回0；
2)折半查找
对于有序的顺序存储表来说，可以用这个方法挺高查找效率。
算法思路：
1>给定值key，逐步确定待查记录所在区间，每次将搜索空间减少一半，直到查找成功或者失败为止。
2>设两个指针（或者游标）low，high，分别表示头和尾，初始时low = 1，high = n令mid = (low+high)/2;
3>将mid指向的值与key值比较如果mid<key,则说明要找的值应该往high靠近，令low = mid+1；比较如果mid>key,则说明要找的值应该往low靠近，令high = high-1；当key = mid所指向的值或者low<=high不满足时返回。
简单代码举例：
#include <stdio.h>2.排序算法
#include <stdlib.h>
#define MAXSIZE 10
#define TRUE 1
#define FALSE 0
int bin_search(int *list, int len, int key);
int main (int argc, char *argv[])
{
int list[MAXSIZE] = {1,3,5,7,9,11,13,15,17,19};
int key = 18;
printf("%d\n",bin_search(list, MAXSIZE, key));
return 0;
}
int sqserch(int *list, int len, int key)//顺序查找
{
int i;
i = len;
while(list[i] != key && i>=0)i--;
return i;
}
int bin_search(int *list, int len, int key)//折半查找
{
int low = 0, hight = len-1, mid;
while(low <= hight){
mid = (low + hight) / 2;
if(list[mid] == key)
return TRUE;
if(list[mid] < key){
low = mid + 1;
}
else{
hight = mid - 1;
}
}
return FALSE;
}
1)插入排序
直接插入排序和折半插入排序
举例：设文件记录的key集合k = {50,36,66,76,95,12,25,36 }；
[50],36
[36, 50], 66
[36,50,66], 76
[36,50,66,76], 95
[36,50,66,76,95] ,12
[12,36,50,66,76,95]25
[12,25,36,50,66,76,95]36
[12,25,36,36,50,66,76,95]
算法思路：将第一个看成是一个有序的子文件，然后从第二个开始，在前面有序的子文件中寻找插入的位置，在寻找的过程中可以折半的查找来提高寻找的效率。
2)交换排序
冒泡排序和快速排序
快速排序是对冒泡排序的一种改进，目的是提高排序效率
快速排序算法思路：
这待排序文件的key集合k={k1,k2,k3,k4,k5,k6,...,kn}，对k中的k1，称作枢轴或基准。
1>逆序比较：j指向表尾，每次k1与kj，若k1<kj，则k1不可能在kn位置，j-1，直到k1>kj为止，交换k1与kj。
2>正序比较：i指向表头，每次k1与ki比较，若k1>ki,则k1不可能在ki左边，i+1,直到k1<ki为止，交换k1与ki。
3>第一次遍历完后，k1的左边都是小于k1的，右边都是大于k1的。
套用上述排序过程（可递归），直到每个子表只含有一项时，排序结束。
程序举例：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define TRUE 1
#define FALSE 0
void insert_sort(int *list, int len);
void quick_sort(int *list, int start, int end);
int main (int argc, char *argv[])
{
int i = 0;
int list[MAXSIZE+1] = {0,2,5,3,8,4,9,7,6,1,11};
insert_sort(list, MAXSIZE);
quick_sort(list, 1, 10);
for(i = 1; i <= MAXSIZE; i++)
printf("%d,",list[i]);
putchar('\n');
return 0;
}
void insert_sort(int *list, int len)//直接插入排序
{
int i, j;
for(i = 2; i <= MAXSIZE; i++){
list[0] = list[i];
for(j = i-1; list[j] > list[0]; j--){
list[j+1] = list[j];
}
list[j+1] = list[0];
}
}
void quick_sort(int *list, int start, int end)//快速排序
{
int i = start, j = end;
if(start < end){
list[0] = list[start];
while(i < j){
while(i < j && list[0] < list[j]){
j--;
}
list[i] = list[j];
while(i < j && list[0] > list[i]){
i++;
}
list[j] = list[i];
}
list[i] = list[0];
quick_sort(list, start, i-1);
quick_sort(list, i+1, end);
}
}