哈希表：

通过要查找的K找到对应的位置。

在存储位置和关键码之间建立一个确定的对应关系。如图：

利用取余也可以构造哈希表（哈希散列）

如例题：

已知连续的地址区间为0～6，给定关键字k的序列{20，30，70，12，18}。若将k％7的值作为k的存储地址，则可以构造出以下存储结构。

上例中k％7为散列(哈希)函数，构造出的存储结构称为散列表。若添加新的关键字“14”，则其散列函数值（14%7=0）将与关键字“70”的存储地址相同，我们称这种关键字不同但是散列函数值相同的现象为冲突。在构造散列表的时候我们须同时设计某种散列函数和某种处理冲突的方法。

如果关键码通过函数的指向得到的是重复的数，产生冲突，则可以往后移存储。

为了避免哈希表的冲突：有如下方法：

 

 

 

 适应情况：事先知道关键码，关键码集合不是           很大且连续性较好。 优点：不会产生冲突 缺点：占用连续空间，空间效率低

 平方取中法：适应情况：事先不知道关键码的分布，且关键码的位数不是很大。

折叠法：将关键字分割成位数相同的几部分，然后取叠加和(舍去进位)作为哈希地址。

适应情况：事先不知道关键码的分布，且关键码的位数很多。

 除留余数法：

思想：H(key)=  key  MOD   p

余数作为位置数，当产生冲突的时候，往后移一位。

数字分析法：使用该方法前应事先知道关键字的集       合，然后选取关键字的若干位来构成哈       希函数值。

随机数法：取关键字的随机函数为哈希地址，即 H(key)=random(key)。

处理冲突的方法：

开放定址法

线性探查法

平方探查法

双散列函数探查法

链地址法

同义词：关键字不同而散列函数值相同的关键字 冲突：待插入元素的散列地址单元已被占用，该元素无法直接存入到此单元中。 冲突原因：散列地址区间小于关键字的取值区间 装填因子α α是已存入元素与散列空间大小的比例 一般取值为0.6-0.9时产生冲突的可能性较小 例如，若有元素600个，则选取表长为667~1000较为合适。

线性探查法 di= 1,2,3,…,m-1 平方探查法 di= i2     （0 ≤ i ≤ m-1) 双散列函数探查法     di= d0+h2(k) （0 ≤ i ≤ m-1, d0=h(k))

 

 

 

 链接法：

 

 

 

链地址法：

排序： 

插入排序（直接插入排序、希尔排序） 直接选择排序 交换排序(起泡排序、快速排序） 归并排序 内部排序方法的比较

插入排序：

把第i个记录Ri插入到有序区{R1, R2, …, Ri-1};将关键字ki依次与关键字ki-1, ki-2, …, k1进行比较，从而找到应该插入的位置，然后将ki插入。

INSERTSORT(rectype R[])   // 对数组R按递增序进行插入排序 
                                                  //  R[0]是监视哨 */
{int i, j;    
 for (i=2; i<=n; i++)         	/* 依次插入R[2], …, R[n] */
 {	R[0]=R[i]; 
	j=i1; 
 	while (R[0].key<R[j].key)       /* 查找R[i]的插入位置 */
 	{R[j+1]=R[j]; j--;}      // 将关键字大于R[i].key的记录后移
 	R[j+1]=R[0];          		/* 插入R[i] */
	}
}   					/* INSERTSORT */

算法采用的是查找比较操作和记录移动操作交替进行的方法 具体做法是：               将待插入记录R[i]的关键字依次与有序区中记录R[j](j=i1, i2, …, 1)的关键字进行比较，若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。因为关键字比R[i]大的记录均已后移，故只要将R[i]插入该位置即可。 附加记录R[0]，其作用有两个： 进入查找循环之前，它保存了R[i]的副本，使得不致于因记录的后移而丢失R[i]中的内容； 在while循环中“监视”下标变量j是否越界，以避免循环内每次都要检测j是否越界。因此，我们将R[0]称为“监视哨”，这使得测试循环条件的时间大约减少一半。

 直接插入排序的算法分析：         整个排序过程只有两种运算，即比较关键字和移动记录。外循环：n1趟插入排序； 内循环：每一趟排序所需进行的关键字的比较和记录的后移。 文件正序时：   每趟排序的关键字比较次数为1，总的比较次数Cmin=n1；   每趟记录移动次数是2次，总的移动次数Mmin=2(n1)； 文件逆序时：关键字的比较次数和记录移动次数均取最大值。      每趟进行i次比较:与前i1个记录及“监视哨” 进行比较      每趟排序中除了上面提到的两次移动外，还需将关键字大 于R[i]的记录后移一个位置。 因此，总的比较次数和记录的移动次数为:

 在随机情况下关键字各种排列出现的概率相同，则可取上述两种情况的平均值作为比较和记录移动的平均次数，约为n2/4。由此，直接插入排序的时间复杂度O(n2)，空间复杂度为O(1)。直接插入排序是稳定的排序方法。

希尔排序：

希尔排序（Shell’s method）又称为“缩小增量排序”（Diminishing Increment Sort）。 基本思想：先取一个小于n的整数d1并作为第一个增量，将文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2<d1，重复上述的分组和排序，直至所取的增量dt=1(dt<dt1<…<d2<d1)为止，此时，所有的记录放在同一组中进行直接插入排序。      

 算法设计：如何设置监视哨？        设某一趟希尔排序的增量为h，则整个文件被分成h组：(R1, Rh+1, R2h+1, …), (R2, Rh+2, R2h+2, …), …，(Rh, R2h, R3h, …)，因为各组中记录之间的距离均是h，故第1组至第h组的哨兵位置依次为1h, 2h, …, 0。 如果像直接插入排序算法那样，将待插入记录Ri(h+1≤i≤n)在查找插入位置之前保存到监视哨中，那么必须先计算Ri属于哪一组，才能决定使用哪个监视哨来保存Ri。为了避免这种计算，我们可以将Ri保存到另一个辅助记录x中，而将所有监视哨R1h, R2h, …, R0的关键字设置为小于文件中任何关键字即可。因为增量是变化的，所以各趟排序中所需的监视哨数目也不同，但是我们可以按最大增量d来设置监视哨。具体算法描述如下：

rectype R[n+d];     	/* R[0]～R[d1]为d个监视哨 ，d=d[0] */
int d[t];       		/* d[0]～d[t1]为增量序列 */
SHELLSORT(rectype R[ ], int d[ ])
{   int i, j, k, h;   	rectype temp; 
     int maxint=32767;       		     /* 机器中的最大整数 */
     for (i=0; i<d[0]; i++)  R[i].key= maxint;   /* 设置哨兵 */
     k=0 ; 
    do {  	h=d[k];      		   /* 取本趟增量 */
      	for (i=d+h; i<n+d; i++)    /* R[h+d]～R[n+d1]插入当前有序区 */
      	{  temp=R[i];      		/* 保存待插入记录 */
        	    j=ih; 
       	    while (temp.key<R[j].key)     	/* 查找正确的插入位置 */
         	    {  R[j+h]=R[j];    	              /* 后移记录 */
       	        j=jh;      		/* 得到前一记录位置 */
                   }
                   R[j+h]=temp;           	/* 插入R[i] */
     	}    	               	/* 本趟排序完成 */
      	k++; 
          } while (h!=1);     	/* 增量为1排序后终止算法 */
}   					/* SHELLSORT

分析：实质是一种插入排序，比直接插入排序快，但不稳定； 主要特点： 每一趟以不同的增量进行排序。例如第一趟增量为5，第二趟增量为3，第三趟增量为1。在前两趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，由于此时增量取值较大，所以关键字较小的记录在排序过程中就不是一步一步地向前移动，而是作跳跃式的移动。 开始时，增量取值较大，每组中记录较少，故排序比较快； 随后，增量值变小，每组中记录变多，但此时记录已基本有序了，因次在进行最后一趟增量为1的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。 如何选择增量序列？  希尔本人最初提出取d1=n/2，di+1=di/2，dt=1，t=log2n。后来又有人提出其他选择增量序列的方法，如di+1=(di1)/3，dt=1，t=log3n1 以及di+1=(di1)/2，dt=1，t=log2n1。

选择排序（Select Sort）：

基本思想：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录排完为止。     直接选择排序和堆排序都归属于此类排序。

直接选择排序基本思想： 第一趟排序是在无序区R[0]～R[n1]中选出最小的记录，将它与R[0]交换； 第二趟排序是在无序区R[1]～R[n1]中选关键字最小的记录，将它与R[1]交换； 第i趟排序时R[0]～R[i2]已是有序区，在当前的无序区R[i1]～R[n1]中选出关键字最小的记录R[k]，将它与无序区中第1个记录R[i1]交换，使R[1]～R[i1]变为新的有序区。              因为每趟排序都使有序区中增加了一个记录，且有序区中的记录关键字均不大于无序区中记录的关键字，所以，进行n1趟排序后，整个文件就是递增有序的。其排序过程所示。

 

 

直接选择排序的算法如下：
SELECTSORT(rectype R[ ]) //对R[0]～R[n1]进行直接选择排序
{  int i, j, k; 
   rectype temp; 
   for (i=0; i<n1; i++)    // 进行n1趟选择排序 
   {  k=i; 
      for (j=i+1; j<n; j++) // 在当前无序区选关键字最小的记录R[k]
   	if (R[j].key<R[k].key)  // 稳定性 <=？
                  k=j; 
	if (k!=i)     		/* 交换R[i]和R[k] */
   	{  temp=R[i]; 
     	    R[i]=R[k]; 
     	    R[k]=temp; 
   	}
    }
}    			/* SELECTSORT */

   直接选择排序的比较次数与关键字的初始排列状态无关，第一趟找出最小关键字需要进行n1次比较，第二趟找出次小关键字需要进行n2次比较……。因此，总的比较次数为

 交换排序 两两比较待排序记录的关键字，发现两个记录逆序时即进行交换，直至没有逆序的记录为止。 两种方法：起泡排序和快速排序

起泡排序（Bubble method）

具体算法如下：
BUBBLESORT(rectype R[ ])    /* 从下往上扫描的起泡排序 */
{ int i, j, nowsap; 
  rectype temp; 
  for (i=0; i<n1; i++);     	/* 进行n1趟排序 */
  { noswap=TRUE;      			/* 置未交换标志 */
     for (j=n1; j>i; j--)      		/* 从下往上扫描 */
         if (R[j－1].key>R[j].key)    	/* 交换记录 */
         {  temp=R[j－1]; 
            R[j－1]=R[j]; 
            R[j]=temp; 
            noswap=FALSE; 
          }
     if (noswap) break;   /* 本趟排序中未发生交换，则终止算法
  }
}    				/* BUBBLESORT */

容易看出： 若文件按关键字递增有序，则只需进行一趟排序，比较次数为n1，记录移动次数为0，即比较次数和记录移动次数均为最小值； 若文件按关键字递减有序，则需进行n1趟排序，比较次数和记录移动次数均为最大值，分别为：

 快速排序（Quick Sort）：

基本思想: 任取待排序记录序列中的某个记录 (例如取第一个记录) 作为枢轴(pivot)，以该记录的关键字作为基准，将整个记录序列划分为左右两个子序列：  左侧子序列中所有记录的关键字都小于或等于枢轴记录的关键字  右侧子序列中所有记录的关键字都大于枢轴记录的关键字 枢轴记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的记录都按关键字有序排在相应位置上为止。

快速排序算法 采用快速排序方法对n个记录排序，只须调用QuickSort(R,1,n)，即可完成对R[1..n]的排序。快速排序算法如下： void  QUICKSORT(rectype R[ ],int s1,int t1);    //对R[s1]到R[t1]做快速排序 {      int i;      if (s1<t1) // 只有一个记录或无记录时无须排序      { i=PARTITION(R,s1,t1);                 // 对R[s1]到R[t1]做划分，i作为枢轴的位置                 QUICKSORT(R,s1,i1);   // 递归处理左区间               QUICKSORT(R,i+1,t1);   // 递归处理右区间      } }

快速排序（Quick Sort）：

基本思想:             任取待排序记录序列中的某个记录 (例如取第一个记录) 作为枢轴(pivot)，以该记录的关键字作为基准，将整个记录序列划分为左右两个子序列：  左侧子序列中所有记录的关键字都小于或等于枢轴记录的关键字  右侧子序列中所有记录的关键字都大于枢轴记录的关键字 枢轴记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的记录都按关键字有序排在相应位置上为止。

void  QUICKSORT(rectype R[ ],int s1,int t1);  
 //对R[s1]到R[t1]做快速排序 
{     int i;     if (s1<t1) // 只有一个记录或无记录时无须排序      { i=PARTITION(R,s1,t1);    
            // 对R[s1]到R[t1]做划分，i作为枢轴的位置      
          QUICKSORT(R,s1,i1);   // 递归处理左区间    
          QUICKSORT(R,i+1,t1);   // 递归处理右区间      }}

int PARTITION(rectype R[ ],int l,int h) 
//对无序区R[1..h]做划分，返回划分后被定位的基准记录(枢轴）的位置 
{  int i,j;
   rectype temp;i=l;j=h;temp=R[i]; //初始化，temp为基准
   do{ //从右向左扫描，查找第一个关键字小于temp.key的记录 
       while((R[j].key>=temp.key)&&(i<j)) j;
       if(i<j) R[i++]=R[j]; //交换R[i]和R[j] 
       while((R[i].key<=temp.key)&&(i<j)) i++;
       // 从左向右扫描，查找第一个关键字大于temp.key的记录 
       if(i<j) R[j]=R[i]; //交换R[i]和R[j] 
    }while(i!=j);  R[i]=temp; // 基准temp已被最后定位 
    return i;
}