最主要的是冒泡排序、选择排序、插入排序以及快速排序
1、冒泡排序
冒泡排序是一个比较简单的排序方法。在待排序的数列基本有序的情况下排序速度较快。若要排序的数有n个，则需要n-1轮排序，第j轮排序中，从第一个数开始，相邻两数比较，若不符合所要求的顺序，则交换两者的位置；直到第n+1-j个数为止，第一个数与第二个数比较，第二个数与第三个数比较，......，第n-j个与第n+1-j个比较，共比较n-1次。此时第n+1-j个位置上的数已经按要求排好，所以不参加以后的比较和交换操作。
例如：第一轮排序：第一个数与第二个数进行比较，若不符合要求的顺序，则交换两者的位置，否则继续进行二个数与第三个数比较......。直到完成第n-1个数与第n个数的比较。此时第n个位置上的数已经按要求排好，它不参与以后的比较和交换操作；第二轮排序：第一个数与第二个数进行比较，......直到完成第n-2个数与第n-1个数的比较；......第n-1轮排序：第一个数与第二个数进行比较，若符合所要求的顺序，则结束冒泡法排序；若不符合要求的顺序，则交换两者的位置，然后结束冒泡法排序。
共n-1轮排序处理，第j轮进行n-j次比较和至多n-j次交换。
从以上排序过程可以看出，较大的数像气泡一样向上冒，而较小的数往下沉，故称冒泡法。
public void bubbleSort(int a[])
{
int n = a.length
for(int i=0i<n-1i++)
{
for(int j=0j<n-i-1j++)
{
if(a[j] >a[j+1])
{
int temp = a[j]
a[j] = a[j + 1]
a[j + 1] = temp
}
}
}
}
2、选择排序
选择法的原理是先将第一个数与后面的每一个数依次比较,不断将将小的赋给第一个数,从而找出最小的,然后第二个数与后面的每一个数依次比较,从而找出第二小的,然后第三个数与后面的每一个数依次比较,从而找出第三小的.....直到找到最后一个数。
public void sort(int x[])
{
int n=x.length
int k,t
for(int i=0i<n-1i++)
{
k=i
for(int j=i+1j=nj++)
{
if(x[j]>x[k])k=j
if(k!=i)
{
t=x[i]
x[i]=x[k]
x[k]=t
}
}
}
}
3、插入排序
插入排序的原理是对数组中的第i个元素，认为它前面的i-1个已经排序好，然后将它插入到前面的i-1个元素中。插入排序对少量元素的排序较为有效.
public void sort(int obj[])
{
for(int j=1j<obj.lengthj++)
{
int key=obj[j]
int i=j-1
while(i>=0&&obj[i]>key)
{
obj[i+1]=obj[i]
i--
}
obj[i+1]=key
}
}
4、快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此大道整个数据变成有序序列。
public void quickSort(int obj[],int low,int high)
{
int i=low
int j=high
int keyValue=obj[i]
while(i<j)
{
int temp=0
while(i<j&&obj[j]>=keyValue)
{
j=j-1
}
temp=obj[j]
obj[j]=obj[i]
obj[i]=temp
while(i<j&&obj[i]<=keyValue)
{
i=i+1
}
temp=obj[j]
obj[j]=ojb[i]
obj[i]=temp
}
obj[i]=keyValue
if(low<i-1)
{
quickSort(obj,low,i-1)
}
if(high>i+1)
{
quickSort(obj,i+1,high)
}
}
直接插入排序比较效率高基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序
2, 归并排序(merge sort)体现了分治的思想，即将一个待排序数组分为两部分，对这两个部分进行归并排序，排序后，再对两个已经排序好的数组进行合并。这种思想可以用递归方式很容易实现。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。实现代码如下：
#include <stdio.h>
#include "common.h"
void merge(int data[], int p, int q, int r)
{
int i, j, k, n1, n2
n1 = q - p + 1
n2 = r - q
int L[n1]
int R[n2]
for(i = 0, k = pi <n1i++, k++)
L[i] = data[k]
for(i = 0, k = q + 1i <n2i++, k++)
R[i] = data[k]
for(k = p, i = 0, j = 0i <n1 &&j <n2k++)
{
if(L[i] >R[j])
{
data[k] = L[i]
i++
}
else
{
data[k] = R[j]
j++
}
}
if(i <n1)
{
for(j = ij <n1j++, k++)
data[k] = L[j]
}
if(j <n2)
{
for(i = ji <n2i++, k++)
data[k] = R[i]
}
}
void merge_sort(int data[], int p, int r)
{
if(p <r)
{
int q = (p + r) / 2
merge_sort(data, p, q)
merge_sort(data, q + 1, r)
merge(data, p, q, r)
}
}
void test_merge_sort()
{
int data[] = {44, 12, 145, -123, -1, 0, 121}
printf("-------------------------------merge sort----------------------------\n")
out_int_array(data, 7)
merge_sort(data, 0, 6)
out_int_array(data, 7)
}
int main()
{
test_merge_sort()
return 0
}
4.对于有n个结点的线性表（e0，e1，…，en-1），将结点中某些数据项的值按递增或递减的次序，重新排列线性表结点的过程，称为排序。排序时参照的数据项称为排序码，通常选择结点的键值作为排序码。
若线性表中排序码相等的结点经某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。
在排序过程中，线性表的全部结点都在内存，并在内存中调整它们在线性表中的存储顺序，称为内排序。在排序过程中，线性表只有部分结点被调入内存，并借助内存调整结点在外存中的存放顺序的排序方法成为外排序。
下面通过一个表格简单介绍几种常见的内排序方法，以及比较一下它们之间的性能特点。
排序方法
简介
平均时间
最坏情况
辅助存储
是否稳定
简单排序
选择排序
反复从还未排好序的那部分线性表中选出键值最小的结点，并按从线性表中选出的顺序排列结点，重新组成线性表。直至未排序的那部分为空，则重新形成的线性表是一个有序的线性表。
O( )
O( )
O(1)
不稳定
直接插入排序
假设线性表的前面I个结点序列e0，e1，…，en-1是已排序的。对结点在这有序结点ei序列中找插入位置，并将ei插入，而使i+1个结点序列e0，e1，…，ei也变成排序的。依次对i=1，2，…，n-1分别执行这样的插入步骤，最终实现线性表的排序。
O( )
O( )
O(1)
稳定
冒泡排序
对当前还未排好序的范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调整，让键值大的结点往下沉，键值小的结点往上冒。即，每当两相邻比较后发现它们的排列顺序与排序要求相反时，就将它们互换。
O( )
O( )
O(1)
稳定
希尔排序
对直接插入排序一种改进，又称“缩小增量排序”。先将整个待排序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
kn ln n
O( )
O(logn)
不稳定
快速排序
对冒泡排序的一种本质的改进。通过一趟扫视后，使待排序序列的长度能大幅度的减少。在一趟扫视后，使某个结点移到中间的正确位置，并使在它左边序列的结点的键值都比它的小，而它右边序列的结点的键值都不比它的小。称这样一次扫视为“划分”。每次划分使一个长序列变成两个新的较小子序列，对这两个小的子序列分别作同样的划分，直至新的子序列的长度为1使才不再划分。当所有子序列长度都为1时，序列已是排好序的了。
O(nlogn)
O( )
O(logn)
不稳定
堆排序
一种树形选择排序，是对直接选择排序的有效改进。一个堆是这样一棵顺序存储的二叉树，它的所有父结点（e[i]）的键值均不小于它的左子结点（e[2*i+1]）和右子结点（e[2*i+2]）的键值。初始时，若把待排序序列的n个结点看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换，并对少了一个结点后的n-1结点重新作调整，使之再次成为堆。这样，在根结点得到结点序列键值次最大值。依次类推，直到只有两个结点的堆，并对它们作交换，最后得到有序的n个结点序列。
O(nlogn)
O(nlogn)
O(1)
不稳定
归并排序
将两个或两个以上的有序子表合并成一个新的有序表。对于两个有序子表合并一个有序表的两路合并排序来说，初始时，把含n个结点的待排序序列看作有n个长度都为1的有序子表所组成，将它们依次两两合并得到长度为2的若干有序子表，再对它们作两两合并……直到得到长度为n的有序表，排序即告完成。
O(nlogn)
O(nlogn)
O(n)
稳定
后面根据各种排序算法，给出了C语言的实现，大家在复习的时候可以做下参考。
u 选择排序
void ss_sort(int e[], int n)
{ int i, j, k, t
for(i=0 i< n-1 i++) {
for(k=i, j=i+1 j<n j++)
if(e[k]>e[j]) k=j
if(k!=i) {
t=e[i] e[i]=e[k] e[k]=t
}
}
}
u 直接插入排序
void si_sort(int e[], int n)
{ int i, j, t
for(i=0 i< n i++) {
for(t=e[i], j=i-1 j>=0&&t<e[j] j--)
e[j+1]=e[j]
e[j+1]=t
}
}
u 冒泡排序
void sb_sort(int e[], int n)
{ int j, p, h, t
for(h=n-1 h>0 h=p) {
for(p=j=0 j<h j++)
if(e[j]>e[j+1]) {
t=e[j] e[j]=e[j+1] e[j+1]=t
p=j
}
}
}
u 希尔排序
void shell(int e[], int n)
{ int j, k, h, y
for(h=n/2 h>0 h=h/2)
for(j=h j<n j++) {
y=e[j]
for(k=j-h k>0&&y<e[k] k-=h)
e[k+h]=e[k]
e[k+h]=y
}
}
u 堆排序
void sift(e, n, s)
int e[]
int n
int s
{ int t, k, j
t=e[s]
k=s j=2*k+1
while(j<n) {
if(j<n-1&&e[j]<e[j+1])
j++
if(t<e[j]) {
e[k]=e[j]
k=j
j=2*k+1
}else break
}
e[k]=t
}
void heapsorp (int e[], int n)
{ int i, k, t
for(i=n/2-1 i>=0 i--)
sift(e, n, i)
for(k=n-1 k>=1 k--) {
t=e[0] e[0]=e[k] e[k]=t
sift(e, k, 0)
}
}
u 快速排序
void r_quick(int e[], int low, int high)
{ int i, j, t
if(low<high) {
i=low j=high t=e[low]
while(i<j) {
while (i<j&&e[j]>t) j--
if(i<j) e[I++]=e[j]
while (i<j&&e[i]<=t) i++
if(I<j) e[j--]=e[i]
}
e[i]=t
r_quick(e,low,i-1)
r_quick(w,i+1,high)
}
}
另外，外排序是对大型文件的排序，待排序的记录存储在外存中，在排序过程中，内存只存储文件的一部分记录，整个排序过程需进行多次的内外存间的交换。
*** 查找
查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的结点。
按查找的条件分类，有按结点的关键码查找、关键码以外的其他数据项查找或其他数据项的组合查找等。按查找数据在内存或外存，分内存查找和外存查找。按查找目的，查找如果只是为了确定指定条件的结点存在与否，成为静态查找；查找是为确定结点的插入位置或为了删除找到的结点，称为动态查找。
这里简单介绍几种常见的查找方法。
u 顺序存储线性表的查找
这是最常见的查找方式。结点集合按线性表组织，采用顺序存储方式，结点只含关键码，并且是整数。如果线性表无序，则采用顺序查找，即从线性表的一端开始逐一查找。而如果线性表有序，则可以使用顺序查找、二分法查找或插值查找。
u 分块查找
分块查找的过程分两步，先用二分法在索引表中查索引项，确定要查的结点在哪一块。然后，再在相应块内顺序查找。
u 链接存储线性表的查找
对于链接存储线性表的查找只能从链表的首结点开始顺序查找。同样对于无序的链表和有序的链表查找方法不同。
u 散列表的查找
散列表又称杂凑表，是一种非常实用的查找技术。它的原理是在结点的存储位置和它的关键码间建立一个确定的关系，从而让查找码直接利用这个关系确定结点的位置。其技术的关键在于解决两个问题。
I. 找一个好的散列函数
