Chinaunix首页 | 论坛 | 博客
  • 博客访问: 314612
  • 博文数量: 130
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 554
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-19 19:24
文章分类

全部博文(130)

文章存档

2016年(31)

2015年(16)

2014年(13)

2013年(70)

分类: C/C++

2016-02-29 13:59:54

1.直接插入排序

1) 定义

直接插入排序( straight insertion sort )是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为 m (假设)的有序表中,使之仍保持有序,从而得到一个新的长度为 m 1 的有序表。

2)  算法思路

设有一组关键字{ K 1 K 2 ,…, K n };排序开始就认为 K 1 是一个有序序列;让 K 2 插入上述表长为 1 的有序序列,使之成为一个表长为 2 的有序序列;然后让 K 3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列;依次类推,最后让 K n 插入上述表长为 n-1 的有序序列,得一个表长为 n 的有序序列。

【例】设有一组关键字序列{ 55 22 44 11 33 },这里 n=5 ,即有 5 个记录。请将其按由小到大的顺序排序。排序过程如图9.1所示。

第一趟: [55]   22   44  11  33 

第二趟: [22     55]   44   11  33

第三趟: [22     44   55]   11  33

第四趟: [11     22     44    55] 33

结果:   [11     22      33   44   55 

     

3)具体算法

template

 void stinsort (T r[],int n)

  { int i,j;

    for (i=2;i<=n;i++)          //共进行n-1趟插入

      { r[0]=r[i];              //r[0]为监视哨,也可作下边循环结束标志

        j=i-1;

        while (r[j].key>r[0].key) { r[j+1]=r[j]; j--;}

        r[j+1]=r[0];        //r[0]即原r[i]记录内容,插到r[j]后一位置

      }

  }    //sinsort

4) 算法时间复杂度

此算法外循环 n-1 次,在一般情况下内循环平均比较次数的数量级为O(n) ,所以算法总时间复杂度为O(n2)

5)直接插入排序的稳定性

直接插入排序是稳定的排序方法

 

2.折半插入排序

1) 定义

当直接插入排序进行到某一趟时,对于 r[i].key 来讲,前边 i-1 个记录已经按关键字有序。此时不用直接插入排序的方法,而改为折半查找,找出 r[i].key 应插的位置,然后插入。这种方法就是折半插入排序( Binary insertion sort )。

2) 具体算法

template

 void binasort(T r[],int n)

  { int i,j,l,h,mid;

    for (i=2;i<=n;i++)

      { r[0]=r[i];

        l=1;h=i-1;           //认为在r[1]r[i-1]之间已经有序

        while(l<=h)          //对有序表进行折半查找

       { mid=(l+h)/2;

        if(a[0].key

        else l=mid+1;

       }        //结果在1位置

     for(j=i-1;j>=1;j--)a[j+1]=a[j];

        a[1]=a[0];

        }

  }  //binasort

3) 折半插入排序的时间复杂度

折半插入排序,关键字的比较次数由于采用了折半查找而减少,数量级为O (nlog 2 n) ,但是元素移动次数仍为O (n2 ) 。故折半插入排序时间复杂度仍为O (n2 ) 折半插入排序方法是稳定的。

3.希尔排序

1) 定义

希尔排序( shell sort )是 D .L.希尔( D.L.Shell )提出的“缩小增量”的排序方法。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。

2) 算法思路

①先取一个正整数 d1(d 1 <;n) ,把全部记录分成 d1个组,所有距离为 d1的倍数的记录看成一组,然后在各组内进行插入排序;

②然后取 d2( d2 < d1 )

③重复上述分组和排序操作;直到取 di=1(i>=1) ,即所有记录成为一个组为止。一般选 d1约为 n/2 d2 d 1 /2 d3 d 2 /2 ,…, d i =1

3) 具体算法

template

 void shell(T r[],int n)         //希尔排序

  { int i,j,k;

    k=n/2;//k值代表前文中的增量d

    while(k>=1)           //当增量k值变化到0,结束循环……

       { for(i=k+1;i<=n;i++)

           { r[0].key=r[i].key;j=i-k;

             while((r[j].key>r[0].key)&&(j>=0))

                 { r[j+k].key=r[j].key;j=j-k;}

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

            }

             k=k/2;

       }

  }

4) 算法分析

K=1时,此算法就等同于直接插入排序方法。由于前边大增量的处理,使关键字大体有序,因此最后一趟排序移动的记录少,处理速度快。

有人在大量实验基础上推出,它的时间复杂长为 O(n 1.3 ) 。如果对关键字序列 {6,7,5 1 ,2,5 2 ,8} 进行希尔排序,可以看出希尔排序是不稳定的。

阅读(530) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~