【数据结构笔记】排序（上）

1.插入排序

基本思想：对于P=1~N-1,假设前P-1个元素是已排序的，那么把P放到合适的位置，使得前P个元素也处于排序状态。

算法：

insert(A[],N)

{

    for(p=1;p

    {

        tmp=A[p];

        for(j=p-1;j>=0;j--)

        {

            if(A[j]>tmp)

               A[j+1]=A[j];

            else

               break;

        }

        A[j]=tmp;

    }

}

 

2.shell排序

基本思想：选取增量序列h1,h2,...hk...,只要h1=1，就一定可以完成排序，对于针对某个增量序列hk的排序是这样的：p=hk,hk+1,..N-1,对于每一个p，对0~p之间间隔为hk的序列进行插入排序。

算法：

shellsort(A[],N)

{

    for(inc=N/2;inc>0;inc=inc/2)

       for(i=inc;i

       {

            tmp=A[i];

            for(j=i-inc;j>=0;j=j-inc)

            {

                if(A[j]>tmp)

                   A[j+inc]=A[j];

                else

                   break;

            }

            A[j]=tmp;

        }

}

 

3.堆排序

基本思想：将N个元素构建成一个二叉堆，然后执行N次deletemin操作。

二叉堆的构建：从倒数第二层的最后一个元素开始，使以其为根结点的子堆处于有序状态，基本方法就是让这个根结点向下进行“下滤”操作，通过这种不断向上的递归“有序化”操作，将N个元素构建成一个有序的堆

buildheap（A,N）

{

    for(i=N/2;i>=0;i--)

        percdown(A,i,N);

}

 

percdown(A,i,N)

{

   int child;

   for(tmp=A[i];leftchild(i)

   {

        child = max(leftchild(i),rightchild(i));

        if(tmp>child)

           A[i]=A[child];

        else

           break;

   }

   A[i]=tmp;

}

 

阅读(733) | 评论(0) | 转发(0) |

0

上一篇：【数据结构笔记】优先队列，堆

下一篇：【c陷阱与缺陷笔记】chapter1-词法陷阱