来自：http://blog.csdn.net/tulun/article/details/6739962
临近找工作了，我也开始看看已经快忘记的书本，复习以前学得很扎实的知识，但是经常不用或用的很少，这些知识只是零星记得。所以说，早点准备对找工作相当有好处。尽管我觉得学生应该注重解决问题的能力或是思维方式的活跃、多变，但是公司招人的时候只能通过一些基础知识比如算法、数据结构、网络等方面，来录取人才。这就导致我们很多人去强记这些算法等知识，因为，毕竟有些知识很复杂的，一般只能掌握其思想，指望短时间内写出算法感觉难度很大。但是基础知识的掌握还是很有必要的，这个都搞不定就说不过去了。
如下是我结合网上及书本上的资料，针对常见笔试题目的要求，总结的关于排序和查找方面的基础知识，希望可以帮助到某些人，呵呵！！
// 查找
typedef int eletype;// 默认设置元素类型为int
int n;// 默认元素个数为n
// 简单顺序查找
// 平均查找长度(n+1)/2
int seq_search(eletype A[n+1],eletype x)
{
int i = n;
A[0] = x;// 充当监视哨
while( A[i]!=x )
i--;
return i;
}
// 有序表的二分查找
// 等概率下，平均查找长度为(n+1)/n*log(n+1)-1
int bin_search(eletype A[n],eletype x)
{
int mid,low = 0,high = n-1;
while (low <= high)
{
mid = (low+high)/2;
if (x == A[mid])
return mid;
else
if(x < A[mid])
high = mid -1;
else
low = mid + 1;
}
return -1;
}
int bin_search(eletype A[n],int low, int high, eletype x)// 递归形式
{
if(low>high)
return -1;
else
{
int mid = (low+high)/2;
if (x == A[mid])
return mid;
else
if(x < A[mid])
return bin_search(A,low,mid-1,x);
else
return bin_search(A,mid+1,high,x);
}
}
// 分治法(divide and conquer)
// 对于一个规模为n的问题，若该问题可以容易地解决，则直接解决，否则将其分解为k个规模较小
// 的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的
// 解合并，得到原问题的解。
// 分治法在每一层递归上由三个步骤组成：
// 划分：将原问题分解为若干规模较小、互相独立、与原问题形式相同的子问题
// 解决：若子问题规模较小，则直接求解；否则递归求解各子问题
// 合并：将各子问题的解合并为原问题的解
// 二叉排序树的查找
// 二叉排序树的中序序列是递增序列，二叉排序树中某节点的查找长度等于该节点的层次数
struct Bnode
{
eletype data;
Bnode *lchild;
Bnode *rchild;
};
Bnode *bst_serch(Bnode*T,eletypex)
{
Bnode *p = T;
while (p != NULL)
{
if(x == p->data)
return p;
else
if(x < p->data)
p = p->lchild;
else
p = p->rchild;
}
return p;
}
Bnode *bst_serch(Bnode*T,eletypex)// 递归形式
{
if(T == NULL || x == T->data)
return T;
else
if(x < T->data)
return bst_serch(T->lchild,x);
else
return bst_serch(T->rchild,x);
}
void insert(Bnode *&T, Bnode *s)
{
if(T == NULL)
T = s;
else
if(s->data < T->data)
insert(T->lchild,s);
else
insert(T->rchild,s);
}
// 排序定义：将数据表调整为按关键字从小到大或从大到小的次序排列的过程
// 分类：增排序、减排序；内部排序、外部排序；稳定排序、不稳定排序
// 大多数的排序算法都有两个基本的操作：比较两个关键字的大小；改变指向记录的指针或移动记录本身。
// 评价标准：执行时间和所需的辅助空间；算法本身的复杂度。
// 存储方式：
// 顺序表：通过关键字之间的比较判定，将记录移动到合适的位置
// 链表：无需移动记录，仅需修改指针
// 顺序表+辅助表：只需对辅助表的表目进行物理重排。适用于难于在链表上实现，且仍需避免排序过程中移动记录的排序方法
typedef int eletype;// 默认设置元素类型为int
int n;// 默认元素个数为n
// 插入排序
// 基本思想：将待排序表看做是左右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的元素逐个插入到左边的
// 有序区中，以构成新的有序区。
// 分类：直接插入排序和希尔排序
// 直接插入排序
// 稳定排序
// 一般是o(n*n)；当序列为正序或基本有序时，时间复杂度为o(n)；
void insert_sort(eletype A[n+1])
{
eletype temp;
int j;
for (int i=2;i<n+1;i++)
{
temp = A[i];
j = i-1;
while (A[j]>temp)
{
A[j+1] = A[j];
j = j-1;
}
A[j+1] = temp;
}
}
void insert_sort(eletype A[n+1])// 采用监视哨
{
int j;
for (int i=2;i<n+1;i++)
{
A[0] = A[i];
j = i-1;
while (A[j]>A[0])
{
A[j+1] = A[j];
j = j-1;
}
}
}
// 希尔排序
// 将待排序列划分为若干组，在每组内进行直接插入排序，以使整个序列基本有序，然后再对整个序列进行直接插入排序。
// 步长的选择很关键
// 不稳定排序，o(nlogn)
void shell_sort(eletype A[n])
{
int j,d = n/2;
eletype x;
while (d>=1)
{
for (int i=d;i<n;i++)
{
x = A[i];
j = i-d;
while (j>=0&& A[j]>x)
{
A[j+d] = A[j];
j = j-d;
}
A[j+d] = x;
}
d = d/2;
}
}
// 交换排序
// 基本思想：两两比较待排列的元素，发现倒序即交换
// 分类：冒泡排序和快速排序
// 冒泡排序
// 基本思想：从一端开始，逐个比较相邻的两个元素，发现倒序即交换
// 稳定排序，时间复杂度为o(n*n)
void bubble_sort(eletype A[n+1])
{
for (int i=1;i<n;i++)
{
for (int j=n;j>=i+1;j--)
{
if (A[j]<A[j-1])
A[j] <-->A[j-1];
}
}
}
void bubble_sort(eletype A[n+1])// 改进的冒泡排序
{
int i=1;
bool exchanged;
do
{
exchanged = false;
for (int j=n;j>=i+1;j--)
{
if (A[j]<A[j-1])
{
A[j] <-->A[j-1];
}
exchanged = true;
}
i++;
} while (i<n && exchanged==true);
}
// 快速排序
// 基本思想：首先，选定一个元素作为中间元素，然后将表中所有元素与该中间元素做比
// 较，将表中比中间元素小的元素调到表的前面，将比中间元素大的元素调到后面，再将
// 中间元素放在这两个部分之间以作为分界点，这样便得到一个划分。然后再对左右两部
// 分分别进行快速排序（即对所得到的两个子表再采用相同的方式来划分和排序，直到每
// 个子表仅有 一个元素或为空表为止。此时便得到一个有序表）
// 不稳定排序，时间复杂度o(k*n*logn)
// 从平均时间性能来说，快速排序是目前被认为最好的一种内部排序算法
void partition(eletype A[n],int s,int t,int *cutpoint)
{
eletype x = A[s];
int i=s,j=t;
while (i != j)
{
while(i<j && A[j]>x) j--;
if(i<j)
{
A[i] = A[j];
i = i+1;
}
while(i<j && A[i]<x) i++;
if(i<j)
{
A[j] = A[i];
j = j-1;
}
}
A[i] = x;
*cutpoint = i;
}
void quick_sort(eletype A[n],int s,int t)
{
int *i = NULL;
if (s<t)
{
partition(A,s,t,*i);
quick_sort(A,s,*i-1);
quick_sort(A,*i+1,t);
}
}
// 选择排序
// 基本思想：在每一趟排序中，在待排序子表中选出关键字最小或最大的元素放在其最终 // 位置上。
// 分类：直接选择排序和堆排序
// 直接选择排序
// 基本思想：在待排序子表中完整地比较一遍以确定最大（小）元素，并将该元素放在子表的最前（后）面。
// 不稳定排序，时间复杂度是o(n*n)
void select_sort(eletype A[n])
{
int min;
for (int i=0;i<n-1;i++)
{
min = i;
for (int j=i+1;j<n;j++)
{
if(A[j] < A[min])
min = j;
}
if(min != i)
A[min]<--> A[i];
}
}
// 堆排序
// 不稳定排序，时间复杂度是o(nlogn)
void sift(eletype A[n+1],int k,int m)
// 调整数组中下标为-n的元素中的序号不大于m的以k为根的子序列
// 假设以k和k+1为根的左右子树均是堆
{
eletype x = A[k];
bool finished = false;// 临时保存当前根值，空出位置，并设未结束标志
int i,j;
i = k;
j = 2*i;// i指示空位，j先指向左孩子节点
while (j<=m && !finished)// 确定i节点不是叶子且搜索未结束
{
if(j<m && A[j]<A[j+1])// 让j指向左右孩子中的最大者
j = j+1;
if( x>=A[j] )// 原根为最大，置结束筛选标志
finished = true;
else
{
A[i] = A[j];// 值大的孩子节点上移
i = j;
j = 2*j;// 继续往下筛选：i指向新的空位，j相应改变
}
}
A[i] = x;// 将原根值填充到所搜索到的当前的空位置中
}
void heap_sort(eletype A[],int n)
// 对数组中下标为-n的元素用堆排序算法实现排序
{
int i;
for (i=n/2;i>=1;i--)
sift(A,i,n);// 建初始堆
for(i=n;i>=2;i--)// 控制排序过程
{
A[i]<-->A[1];// 输出根
sift(A,1,i-1);// 调整子序列A[1]-A[i-1]为堆
}
}
// 归并排序
// 基本思想：是一种基于归并的排序，所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。
// 归并
void merge(eletype A[],eletype B[],eletype C[],int la,int lb,int lc)
{
int ia=1,ib=1,ic=1;
while(ia<=la &&ib<=lb)
if (A[ia]<=B[ib])
C[ic++] = A[ia++];
else
C[ic++] = B[ib++];
while(ia<=la)
C[ic++] = A[ia++];
while(ib<=lb)
C[ic++] = B[ib++];
}
// 归并排序
// 需要原表等量的辅助存储空间，时间复杂度为o(nlogn)
// 实现：首先将整个表看成是n个有序子表，每个子表的长度为。然后两两归并，得到n/2个长度为的有序子表。然后再两两归并，
// 得到n/4个长度为的有序子表。以此类推，直至得到一个长度为n的有序表为止。