注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mihooke's blog

IT之恋

 
 
 

日志

 
 

排序算法汇总  

2014-08-13 20:13:48|  分类: 学习录 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

       看了一周的排序算法,终于把它的骨架摸清了,先总结如下。最后还有基排序没总结,留到下文中。

       排序一般有插入排序、选择排序、交换排序、归并排序和分配排序。前面有讲过查找,其实排序就是查找的前序工作。本质上是将无序的序列通过关键字的移动和比较,使得序列有序。排序算法有稳定性之说,一般来讲,在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,那么称该算法是不稳定的。本文讨论排序算法,是假设无序序列是线性表保存的,并且关键字是int类型的数字,定义如下:

#define MAX 100

typedef struct 

{

   int key;

   othertype other;

}DataType;

typedef struct

{

   DataType r[MAX+1]; //r[0]充当前哨

   int lenght;

}Sqlist;

一、插入排序

插入排序是将待排序列的数据依次插入已经排好的序列中的相应位置。插入排序有直接插入排序、二分法(折半)插入排序、希尔排序。

1、直接插入排序

      它的实质就是将待排子序列元素逐步插入有序子序列的过程,是排序算法中最基本的思想。具体实现过程是:首先把整个序列看作是两个序列,一个是以第一个关键字为元素的有序子序列,另一个是其余所有关键字为元素的无序子序列;从无序子序列的关键字开始逐个与第一个有序子序列中的关键字作比较,然后按照顺序插入到第一个子序列中,直到无序子序列中所有元素都插入到有序子序列中为止,算法结束。

设序列S={74,87,67,91,87,61,76,95,79,71},可以看作是{74}{87,67,91,87,61,76,95,79,71}两个子序列,其中{74}是有序子序列,然后从第二个序列中的87关键字开始逐个与{74}中的关键字作比较。整个过程如下图所示

 排序算法汇总 - mihooke - mihooke的博客

到第九次的时候,就已经排序完毕了。算法代码如下:

void straightsort(Sqlist *S)

{

   int i,j;

   for(i=2;i<=S->length;i++)

   {

      r[0]=r[i];//把待插入的元素放入前哨r[0]

      j=i-1;

      while(r[0]<r[j])

      {//前哨值和有序子序列比较

 r[j+1]=r[j];

 j--;

      }

      r[j+1]=r[0];//最终把前哨值插入到正确的位置

   }

}

在空间效率上,仅用户了一个辅助单元r[0],因此辅助空间就是O(l)。在时间效率上,最好的情况是序列已经有序,但是仍要作n-1次比较,所以时间复杂度就是O(n)。最坏的情况每趟移动次数n+1,比较次数也是n+1,总的比较次数就是n^2/2,时间复杂度就是O(n^2)。一般情况时间复杂度也是O(n^2),它是稳定的排序算法。

2、折半插入排序

      折半法其实是在直接插入排序的基础上一种优化。基本思想是:将待插入元素和有序子序列的中间元素进行比较,利用折半查找的思想去寻找待插入元素的正确位置。即若待查元素大于mid元素,则在mid后面的子序列中查找,反之,则在mid前面的子序列中查找,直到找到正确的位置。下面是算法代码:

 void BinarySort(Sqlist *S)

 {

     int low,mid,high;

     for(i=2;i<=S->length;i++)

     {

       r[0]=r[i];

       low=1;

       high=i-1; //初始位置

       while(low<=high)

      {

         mid=(low+high)/2;

         if(r[0]>=r[mid])

           low=mid+1;

        else

           high=mid-1;

      }

  //注意:折半查找完毕后,lowmidhigh三个是指在同一个位置的,也就是说,插入位置是low/mid/high+1.

  //下面的for循环就是后移元素并插入前哨的值

     for(j=i-1;j>=high+1;j--)

        r[j+1]=r[j];

     r[high+1]=r[0];

   }

 }

 虽然总的比较次数是n*log2n,但当n很大时,移动次数就和比较次数差不多相等了,因此时间复杂度就是O(n^2),辅助空间是O(1),它是一个稳定的算法。

 3、希尔排序

       希尔排序的基本思想是:先将待排序列根据步长将整个序列分成若干个子序列,并对这几个子序列直接插入排序;待整个序列基本有序时,再对全体序列进行一次直接插入排序。

 这里关键是要选个步长序列,即把整个序列分成多少个元素子序列。

 先来看个例子,序列S={74  87  67  91  87  61  76  95  79  71  100  20  38  45}。先选步长为5,如下排整:

 排序算法汇总 - mihooke - mihooke的博客

 那么子序列就是{74 61 100}{87 76 20}{67 95 38}{91 79 45}{87 71}现在将这5个无序子序列进行直接插入排序,排序后就{61 74 100}{20 76 87}{38 67 95}{45 79 91}{71 87}得到第一趟排序结果。

 接着选步长为3,排整如下:

 排序算法汇总 - mihooke - mihooke的博客

 那么子序列就是{74 91 76 71 38}{87 87 95 100 45}{67 61 79 20}直接插入排序后为{38 71 74 76 91}{45 87 87 95 100}{20 67 61 79}得到第二趟排序结果。

 接着选步长为1此时序列基本是有序的,对其进行直接插入排序,最后便可得到有序的序列。通过逐步缩小步长来较少比较的次数。假设把步长也存放在一个序列里,t1,t2,...,tk,其中tk=1,按步长对序列进行k趟排序。下面是算法代码

 void ShellInsert(Sqlist *S,int gap)

 {//一趟增量为gap的插入排序

     int i,j;

     for(i=gap+1;i<=S->length;i++)

    {

       if(r[i]<=r[i-gap])

       {//这条if语句里面其实就是直接插入排序

          r[0]=r[i];//前哨

          for(j=i-gap;j>0&&r[0]<r[j];j=j-gap)

             r[j+gap]=r[j];//后移并为待插元素留空位

         r[j+gap]=r[0];

      }

   }

 }

 void ShellSort(Sqlist *S,int gap[],int t)

 {//对序列进行全部步长的排序

    int k;

    for(k=0;k<t;k++)

    {

       ShellInsert(S,gap[k]);

    }

 }

 希尔排序的时效分析很难,但显然优于直接插入排序,它是一个不稳定算法。

 

 二、交换排序

 交换排序的基本思想是通过两两比较待排序列的关键字,并通过交换元素使之成为有序序列,是个不断比较和交换的过程。主要有冒泡排序、快速排序。

 1、冒泡排序

 冒泡排序是交换排序最基本的方法,通过两两比较每趟找出一个无序子序列中的最大值或最小值,并放到序列最后。

 假设无序序列S={74,87,67,91,87,61,76,95,79,71}按照升序排列,整个冒泡过程如下图所示:

 排序算法汇总 - mihooke - mihooke的博客

 可以看到每趟都从前面的无序序列中冒出一个最大值,这样循环下去,直到冒出所有的元素,即排序完毕。可以说,冒泡排序思想比直接插入排序算法思想还简单,算法代码如下:

 void BubbleSort(Sqlist *S)

 {

    int i,j;

    for(i=1;i<S->length;i++)//进行n-1趟循环

      for(j=2;j<S->length-i;j++)//找出最大值

        if(r[j]<r[j-1])

        {//设置前哨、元素依次交换,插入最大值

          r[0]=r[j];

    r[j]=r[j-1];

    r[j-1]=r[0];

        }

 }

 冒泡排序用户了一个辅助空间,因此它的空间复杂度是O(1)再来分析它的时间复杂度,时间主要消耗在两个for循环上,第一个要进行n-1趟排序,这是必须的;第二个for循环,其中还有比较次数,交换次数,最坏的情况下,都是n-i次,那么就是O(n^2)

 我们可以对冒泡排序进行改进,有三种改进方法。

   NO.1  原先的算法思想中,不管序列状态怎样,都要进行n-1趟排序,如果在每趟中未发现气泡位置交换,那说明顺序是对的,因此可以在这样扫描完后就结束该趟排序,从而使得效率提高。可以在每趟排序前加个标志,冒泡后再改变此标志,如果标志不变,那说明元素没发生交换,则结束该趟排序。代码如下:

 void BubbleSort_imp1(Sqlist *S)

 {

    bool flag=true;

    int i,j;

    for(i=1;i<S->length;i++)

    {

       flag=flase;

       for(j=2;j<S->length-i;j++)

         if(r[j]<r[j-1])

  {

     r[0]=r[j];

     r[j]=r[j-1];

     r[j-1]=r[0];

     flag=true;

        }

        if(!flag)

          break;

    }

 }

 这种改进方法时间复杂度还是O(n^2),但是在效率上要比原来的冒泡算法快。

  NO.2 第二种改进方法思想是,在每趟冒泡排序的扫描中,记住最后一次交换元素的位置,使得下趟循环的时候扫描到该位置,那么可以明显减少比较的次数。算法代码如下:

 void BubbleSort_ipm2(Sqlist *S)

 {

    int i,j,lastpos=S->length-1;

    for(i=1;i<S->length;i++)

       for(j=2;j<lastpos;j++)

         if(r[j]<r[j-1])

        {

  r[0]=r[j];

  r[j]=r[j-1];

  r[j-1]=r[0];

  lastpos=j;

       }

 }

 这样可以很有效地减少扫描区间,这样的时间复杂度仍然是O(n^2),但是减少了比较的次数,从而提高了效率。

  NO.3 第三种方法就是时间上的提高了,思想是在每趟排序时,交替改变扫描方向,即先从前往后扫描,再从后往前扫描,这两次扫描都是在一次循环中完成的,所以在时间效率上应该低于上述几种算法。算法代码如下:

 void BubbleSort_ipm3(Sqlist *S)

 {

    int low,high,index,i;

    low=1;

    high=S->length;

    index=low;

    while(low<high)

    {

       for(i=low;i<highli++)

         if(r[i]>r[i+1])

         {

     r[0]=r[i+1];

     r[i+1]=r[i];

     r[i]=r[0];

     index=i;

         }

     }

     high=index;

     for(i=high;i>low;i++)

        if(r[i]<r[i-1])

        {

    r[0]=r[i-1];

    r[i]=r[i-1];

    r[i-1]=r[0];

    index=i;

       }

 }

 2、快速排序

    快速排序实际上是冒泡排序的一种改进,基本思想是通过一趟排序将待排子序列分成独立的两部分,其中一部分记录的关键字比另一部分记录的关键字小,然后分别对这两部分继续使用该方法排序,直到最终使得整个序列有序。

 将待排序列S任意选择一个元素K作为轴值,小于K的关键字保存在子序列R中,大于K得关键字保存在子序列L中,对子序列R和L进行递归排序,直到比较完毕,算法结束。

 序列r={49 14 38 74 96 65 8 49 55 27},假设取轴值为第一个元素49,并存放到r[0]中,用于作比较,用lowhigh分别表示序列首元素和末元素下标,首先从high处进行与r[0]比较,若大于r[0],则末元素不移动,high1,继续比较;若小于r[0],则把high处的元素放到low处,那么low1,继续与r[0]比较......如此循环下去。

排序算法汇总 - mihooke - mihooke的博客
 排序算法汇总 - mihooke - mihooke的博客

一趟排序算法代码如下:

 void QuickSort_pre(Sqlist *S,int low,ing high)

 {//交换序列low-high之间的元素,最后lowhigh相等时,交换完毕,返回lowhigh其中一个值

    int key;

    r[0]=r[low];

    key=r[low];//轴值

    while(low<high)

    {

       while(r[high]>=key)

         high--;//high处值大于key,则不交换

       r[low]=r[high];

       while(r[low]<=key)

         low++;//low处值小于key,不交换

      r[high]=r[low];

    }

    r[low]=r[0];

    return low;//返回轴点

 }

 快排就是上述一趟操作的递归操作,因此:

 void QuickSort(Sqlist *S,int low,int high)

 {

    int divide;

    if(low<high)

    {

       divide=QuickSort_pre(S,low,high);//分为两部分,即进行第一趟排序,返回轴值位置

      QuickSort(S,low,divide-1);

      QuickSort(S,divide+1,high);

    }

 }

    快速排序可以用二叉树来理解轴值相当于二叉树的根节点左右子树相当于分出来的RL子序列,...,依次这样分下去的结构。因此快排的空间复杂度就是树的深度O(log2n),接近于平衡二叉树。在一趟排序中,要进行n次比较,那么递归下去,时间复杂度就是O(nlog2n),快排是排序算法中平均性能最好的方法,但如果序列基本有序情况下,则效率不是很好。它是不稳定的排序。


 三、选择排序

 选择排序就是从每趟中选取剩下无序子序列中的最小关键字,直到整个序列选取完毕为止。

 1、简单选择排序

简单选择排序思想是,第一趟,从n个元素中选取最小值元素,与r[1]交换;第二趟,从n-1个元素中选取最小值元素,与r[2]交换,...,如此循环下去,直到交换到最后一个元素。思想很简单,看算法代码:

void SelectSort(Sqlist *S)

{

   int i,j,t;

   for(i=1;i<S->length;i++)

   {

      for(j=i+1,t=i;j<=S->length;j++)

      {

if(r[t]>r[j])

   t=j;//t中存放最小关键字的下标

      }

     r[0]=r[t];//r[i]交换

     r[t]=r[i];

     r[i]=r[0];

   }

}

简单选择排序算法时间主要消耗在两个for循环中,因此时间复杂度就是O(n^2)。它是不稳定的排序。

2、堆排序

首先要明白数据结构中的堆是什么,和内存中的堆有什么区别。

首先说一下内存中的堆,我们知道malloc函数分配内存的时候是在堆中分配的,这就是取得堆中地址的唯一办法,堆得访问结构是从低地址到高地址的,也就是说堆分派内存是动态的,一般系统可用的堆内存是4G左右。而栈正好相反,一般系统可用栈内存仅仅是几M,但是速度上要比堆快好多。

那数据结构中的堆呢,它是一个完全二叉树,完全二叉树就是一棵与满二叉树序号对应的二叉树,一棵完全二叉树如下如所示:

 排序算法汇总 - mihooke - mihooke的博客

那么堆满足完全二叉树的什么要求呢?每个结点的孩子结点值都比父亲结点大(),那么便称这棵完全二叉树为堆,按照这个大小关系堆分为大根堆和小跟堆。大根堆和小跟堆如下图所示:

 排序算法汇总 - mihooke - mihooke的博客

为了说明清楚,本文里采用大根堆来讲

,小跟堆和大根堆是相反的。完全二叉树中,一个结点下标为k的孩子结点的下标2k2k+1

堆排序的基本思想是,先将所有元素建成一个堆,那么每个结点的值都大于它的孩子结点的值,根节点就是序列中最大的值,我们取出根节点,此时,堆就不完整了,再次调整剩余元素成为一个堆,取出根节点,...,直到取完所有的元素,堆排序完毕。那么整个算法中最关键的是怎样建立一个堆和取出根结点后,剩余元素怎么建立成堆。

建立堆最关键要明白堆得父亲结点永远大于两个孩子结点就可以了,然后遍历结点1---n/2,因为从n/2+1之后的结点都是叶子结点了,已经符合堆结构了。先从结点n/2开始,如果发现不符合堆结构,则和它的父亲结点交换,这样比较操作直到根结点结束本趟比较;再遍历结点n/2-1...,直到遍历完结点1,堆建立完成。下面是一个大根堆生成过程:

 排序算法汇总 - mihooke - mihooke的博客

首先从第n/2个结点开始,也就是第四个结点91,经过几步比较,91到达根节点,但是,左子树中就不满足堆了,那么便继续调整左子树,结点85上去,53下来,直到36调到最下面,结束第一趟比较。接下来比较第三个结点30,由于符合堆,所以继续第二个结点85,也符合,再比较根节点91,两个孩子结点都小于91,故满足堆,建立完毕。算法代码如下:

void BuildHeap(Sqlist *S,int n,int m)

{//对序列的n-m元素进行建大根堆

   int i,j;

   int rc;//rc为中间变量,保存本趟作比较的结点

   rc=r[n];

   i=n;

   for(j=i*2;j<m;j=j*2)

   {//注意这里的j=j*2,意思是找到j的孩子结点,并与之相比较,并把其中的最大值放入父亲结点中

      if(j<m && r[j]<r[j+1])

         j++;//每趟结束第一次换位后,继续比较它的孩子结点是否符合堆

      if(rc>r[j])

         break;

      r[i]=r[j];//满足之后交换元素

      i=j;

   }

   r[i]=rc;//把作比较的结点插入到i位置

}

堆建立完毕,那么接下来要考虑的就是如何调整取出根结点后的n-1个结点。此时,根结点的左子树和右子树还分别满足堆的结构,如果直接将堆底元素往上推的话,那么就会破坏左子树和右子树。办法就是把堆底结点放入根结点,再对全部结点进行建堆操作,建立完毕,取出根结点,如此循环下去,直到取完结点为止。算法代码如下:

void HeapSort(Sqlist *S)

{

   int i;

   for(i=S->length/2;i>0;i--)//进行i/2趟,建立堆

      BuildHeap(S,i,S->length);

   for(i=S->length;i>1;i--)

   {

      r[1] <=> r[i];//堆底元素和根结点交换,这样排序完成后,从堆顶到堆底就是升序序列了

      BuildHeap(S,1,i-1);//r[1...i-1]重新调整成堆

   }

}

堆排序在序列元素多的情况下非常有效,它的时间复杂度为O(nlog2n),在初始建堆时比较耗时间,但在以后的排序过程中效率就高了,它是不稳定排序。


四、归并排序

      归并排序借助一种分治法的思想,即将长序列分成两个子序列,递归每个子序列再分成两个子序列,加入最后分的子序列有两个元素,那么比较两个元素大小,最后把每个子序列归并到一起。第一趟将两个有序序列归并到一起的算法代码如下:

void Merge(int r[],int rf[],int u,int v,int t)

{//将有序的r[u...v]r[v+1...t]归并为rf[u...t]

   int i,j,k;

   for(i=u,j=v+1,k=u;i<v && j<t;k++)

   {

      if(r[i]<=r[j])

     { rf[k]=r[i];

i++;

     }

     else

     {

        rf[k]=r[j];

j++;

     }

   }

   while(i<=v)

       rf[k++]=r[i++];

   while(j<=t)

       rf[k++]=r[j++];

}

排序算法代码如下:

 void MSort(int p[],int p1[],int n,int t)

 {

    int m;

    int p2[MAX+1];

    if(n==t)

      p1[n]=p[n];

    else

    {

       m=(n+t)/2;

       MSort(p,p2,n,m);//进行两次归并有序操作

       MSort(p,p2,m+1,t);

       Merge(p2,p1,n,m,t);

    }

 }

 void MergeSort(Sqlist *S)

 {

    MSort(r[],r[],1,S->length);

 }

 归并排序时间复杂度为O(nlog2n),不随待排序列的初始状态改变而改变,因此是个稳定的算法。

  评论这张
 
阅读(345)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017