常用的算法和数据结构分析（查找和排序）

2011-11-10

查找

（1）线性表查找

顺序查找：顺序查找效率很低，但对于待查的结构没有任何要求，而且算法非常简单，当待查表中的记录个数较少时，采用顺序查找较好。

折半查找：

折半查找的平均查找长度小，查找速度快，但是它要求表中的记录是有序的，且只能用于顺序存储结构。对于不常变动的有序表，采用折半查找时较理想的。

分块查找：

分块查找又称为索引顺序查找，索引表采用（折半查找），块内（顺序查找）处理线性表既希望有较快的查找速度又需要动态的变化，则可以采用分块查找的方法。

（2）树表的查找

对于需要经常进行插入，删除和查找运算的表，适宜采用二叉查找树结构，在二叉查找树中无论是插入和删除，都需要在二叉树上进行查找，查找的效率取决于树的形态，二叉树越均匀，树的层次越小，平均查找深度越小，该树的查找效率就越高。（对坏的情况下，二叉树和单链表上的顺序查找一样，亦是（n+1）/2;在最好的情况下，二叉树是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是log2（n））

（3）哈希表查找

哈希法是一种直接计算地址的方法，通过对关键字进行某种运算来确定待查记录的存放地址。在查找过程中不需要进行比较，因此其查找时间与表中记录的个数无关。哈希表的查找效率主要取决于发生冲突的可能性和处理冲突的方法。

哈希表的构造方法：平方取中法，折叠法，除留取余法，直接定址法。

坚决冲突的方法：

开放定址法：Hi(H(key)+di ) MOD mdi=1,2,3…时称为线性探测再散列二次探测再散列，随机探测再散列链地址法：

排序内排序：（1）插入排序

直接插入排序：

每一次将一个待排序的记录按其关键字值的大小插入到已经排序的文件中的适当位置，直到全部插入完成。

折半插入排序

插入排序的基本操作是在一个有序表中进行查找和插入。而“查找”这个操作可利用“折半查找”来实现，因此进行的插入排序称之为二分法插入排序。

Void BinsertSort( Recordnode r[],int n){
   for(i=2;i<=n;++i)   {
       r[0]=r[i];
       low=1;
       high=i-1;
       while(low<=high)       {
          m=(low+high)/2;
           if(r[0]<r[m])high=m-1;
                   else low=m+1; 
      }               //跳出循环是low 〉high //插入的位置是r[high+1]     
   for(j=i-1;j>=high+1;--j){
      r[j+1]=r[j];
      r[high+1]=r[0];
    }
}

希尔排序 “缩小增量法排序”是对直接插入排序进行改进后的提出的。

（2）冒泡排序

如果进行冒泡排序后，没有记录交换的位置，这就表明此序列已经是一个有序序列，此时排序也可以结束。

Void Bubblesort(Recordnode r[],int n) {
       Int i,j,flag;
       Int temp;
       Flag=1;
     For(i=1;i<n &&flag=1;i++)     {
        Flag=0;        For(j=0;j<n-i;j++)        {
           If(r[j].key>r[j+1].key)            {
                Flag=1;
                Temp=r[j];
                R[j]=r[j+1];
                R[j+1]=r[j];
            }
        }
    }
}

快速排序算法是由冒泡排序算法改进而得的，是一种分区交换排序方法。一次快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的这个记录中任取一个记录，把该记录放入最终位置后，序列被这几记录分割成两部分，并把该记录排在这两部分的中间，这个过程称为一次快速排序。快速排序的算法：

Void quicksort(Recordlist &L,int low,int high){
    If(low<high){
        Partition(L,low,high);
        If(le_low<le_high) quicksort(L,low,le_high)

        If(Ri_low<Ri_high)quicksort(L,Ri_low,high);
    }
}

Int Partition(Recordnode r[],int low,int high){
   //进行一次快速排序，使记录到位   
    Int Le_low,Le_high,Ri_low,Ri_high;   
    Int x,I,j;   
    I=low;   
    J=high;

    While(i<j){
        While(i<j &&r[j].key>=r[0]){
            --j; 
            r[i]=r[j];
        }           
        while(i<j && r[i].key<=r[0]){
           ++i;       
           r[j]=r[i];
        }
    }
    L.r[i]=x;
    Le_low=low;
    Le_high=i-1;
    Re_low=j+1;
    Re_high=high;
}

在通常情况下，快速排序由非常好的时间复杂度，它优于各种算法，其平均时间复杂度为O（ nlog2（n））但是在原始数据有序的情况下，此算法就退化为冒泡排序O（n*n）。当记录个数n很小时，用快速排序的算法并不合算，一般n〉20以上才有考虑的必要。另外，快速排序是一种不稳定的排序方法。

（3）选择排序

直接选择排序，从待排序的所有记录中，选取关键字最小的记录并将它与原始序列的第一个记录交换位置……堆排序对在直接选择排序法的基础上利用完全二叉树结构形成的一种排序方法。堆排序是完全二叉树顺序结构一种应用。

（3）归并排序

将两个或两个以上的已排序的文件合并成一个有序文件的过程叫归并。归并排序就是用归并的方法来进行排序。

（4）基数排序前面的排序主要是利用比较和交换，而基数排序则是利用分配和收集两种基本操作，基数排序是一种按记录关键字的各位值逐步进行排序的一种方法，此种排序方法一般仅适用于所记录的关键字为整数类型的情况，所以对于字符串和文字的排序就不适用了。

总结：直接插入排序，折半插入排序，直接选择排序，归并排序，冒泡排序是稳定的；希尔排序，快速排序，堆排序是不稳定的；

点击查看评论

常用的算法和数据结构分析（查找和排序）

Blog

Webgl

Project