浅析直接插入排序与折半插入排序

2013-11-17  来源:本站原创  分类:C 语言  人气:1 

这篇文章主要介绍了直接插入排序与折半插入排序,有需要的朋友可以参考一下

首先看一下例子,将数据一个个的插入到一个列表中,插入后这个列表就排序好了

注意:这个列表是递增的,而且内存空间已分配好,只是没有填充真正的数据,如下代码:

int InsertSort(MergeType *L, int data)
{
 int j;
 if (!L->len)
 {
  L->elem[++L->len] = data;
  return 0;
 }
 for (j = L->len-1; j >= 0; --j)
 {
  if (data < L->elem[j])
  {
   L->elem[j+1] = L->elem[j];/*数据后移*/
  }
  else
  {
   L->elem[j+1] = data;
   L->len++;
   break;
  }
 }
 return 0;
}

测试用例的代码如下:

冒泡算法的改进

直接插入排序

核心思想:是将一个记录插入到已排序好的有序表中,从中得到一个新的、记录数增1的有序表,也就是说递增的次序排列每一个数据,将每一个数据插入到前面已经排序好的位置中。看下面的代码

复制代码 代码如下:

int InsertSort(MergeType* L)
{
 int i, j = 0;
 int nCompKey;
 if (!L->elem || !L->len) return -1;

 if (L->elem && (L->len==1)) return 0;
 for ( i = 1; i < L->len; i++) /*递增的顺序排列*/
 {
  if (L->elem[i] < L->elem[i-1])  /*第二个数据比第一个数据小*/
  {
   nCompKey = L->elem[i];
   L->elem[i] = L->elem[i-1];
   //move elements back
   for (j = i-2; j >= 0 && nCompKey < L->elem[j]; --j) /*在>=退出当前循环*/
   {
    L->elem[j+1] = L->elem[j];
   }
   L->elem[j+1] = nCompKey;
  }
 }
 return 0;
}

这里从第二个数据开始,比较当前的数据是否小于前面的一个数,如果小于前面一个数据,就将当前数据插入到前面的队列中,在插入到前面数据中的过程,要移动数据

这里要注意时间的复杂度:

总的比较次数=1+2+……+(i+1-2+1)+……+(n-2+1)= n*(n-1)/2= O(n^2)

总的移动次数=2+3+……+(2+i-1)+ …… + n = (n+2)*(n-1)/2=O(n^2)

当然还要考虑空间复杂度:其实这里使用了一个变量的存储空间作为移动数据的临时空间

这里在移动的过程中,可以减少代码理解的复杂度,但会在每一个数据比较的过程中增加一次比较的次数,如下代码:

复制代码 代码如下:

 ...
 if (L->elem[i] < L->elem[i-1])  /*第二个数据比第一个数据小*/
 {
  nCompKey = L->elem[i];
  /*move elements back, compare count add once*/
  for (j = i-1; j >= 0 && L->elem[j] > nCompKey; --j) /*从较大的数往较小的数的方向*/
  {
   L->elem[j+1] = L->elem[j];
  }/*在>=退出当前循环*/
  L->elem[j+1] = nCompKey; /*此时val[j]<nCompKey,说明当前插入的位置应该在j之后*/
 }
 ...

在插入数据的过程中,其实前面的数据都已经排序好了,这时候一个个的进行查找,必定查找次数较多,如果采用折半查找算法可以减少次数,如下

复制代码 代码如下:

/*折半插入排序算法*/
int BInsertSort(MergeType *L)
{
 int i, j;
 int low, high, mid;
 int nCompKey;
 for (i = 1; i <= L->len - 1; i++ )
 {
  nCompKey = L->elem[i];
  low = 0;
  high = i - 1;

  /*当low=high时,此时不能判断插入的位置是在low=high的
   *前面还是后面,会进入下面的判断*/
  while(low <= high)
  {
   mid = (low + high)/2;
   if ( nCompKey > L->elem[mid] )
   {
    low = mid + 1;/*当(low=mid+1)>high的时候,跳出循环*/
   }
   else
   {
    high = mid -1;/*当(high=mid-1)<low的时候,跳出循环*/
   }
  }/*low>high的时候,退出循环*/
  /*移动nCompKey之前的所有数据,这里使用high+1是因为high<low
   *的时候,按理数据应该放在high的位置,但是此时high的位置可
   *能已经有排列好的数据或者不存在的位置,所以移动为后一个位置*/
  for (j = i-1; j >= high+1; j-- ) /*high是否可以使用low代替??*/
  {
   L->elem[j+1] = L->elem[j];
  }
  /*当没有元素的时候 high=-1*/
  L->elem[high+1] = nCompKey;
 }
 return 0;
}

具体什么原因,请看上面的注释,这里为什么用high+1,但是此时high与low的位置只相差一个位置,才会跳出while循环,请看下面的改进

复制代码 代码如下:

#if 0
  for (j = i-1; j >= high+1; j-- ) /*high或许可以使用low代替*/
  {
   L->elem[j+1] = L->elem[j];
  }
  L->elem[high+1] = nCompKey;
#else
  for (j = i-1; j >= low; j-- ) /*使用low代替high+1*/
  {
   L->elem[j+1] = L->elem[j];
  }
  L->elem[low] = nCompKey;
#endif
...
相关文章
  • 浅析直接插入排序与折半插入排序 2013-11-17

    这篇文章主要介绍了直接插入排序与折半插入排序,有需要的朋友可以参考一下 首先看一下例子,将数据一个个的插入到一个列表中,插入后这个列表就排序好了 注意:这个列表是递增的,而且内存空间已分配好,只是没有填充真正的数据,如下代码: int InsertSort(MergeType *L, int data) { int j; if (!L->len) { L->elem[++L->len] = data; return 0; } for (j = L->len-1; j >= 0

  • C#折半插入排序算法实现方法 2014-10-19

    这篇文章主要介绍了C#折半插入排序算法实现方法,实例分析了C#排序的技巧,具有一定参考借鉴价值,需要的朋友可以参考下 本文实例讲述了C#折半插入排序算法实现方法.分享给大家供大家参考.具体实现方法如下: public static void BinarySort (int[] list) { for (int i = 1; i < list.Length; i+ +) { int low = 0; int high = i - 1; int Temp = list [i]; //Find whi

  • C++线性时间的排序算法分析 2014-04-21

    这篇文章主要介绍了C++线性时间的排序算法分析,是非常经典的非比较排序算法,对于C++程序员有很大的借鉴价值,需要的朋友可以参考下 前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序(可以参考前一篇文章:各种内部排序算法的实现)等,这些排序算法都有一个共同的特点,就是基于比较. 本文将介绍三种非比较的排序算法:计数排序,基数排序,桶排序.它们将突破比较排序的Ω(nlgn)下界,以线

  • java中常用的排序方法 2014-09-19

    今天给大家介绍一下,java中常用的排序方法. package com.test; import java.util.Random; /** * 排序测试类 * * 排序算法的分类如下: 1.插入排序(直接插入排序.折半插入排序.希尔排序): 2.交换排序(冒泡泡排序.快速排序): * 3.选择排序(直接选择排序.堆排序): 4.归并排序: 5.基数排序. * * 关于排序方法的选择: (1)若n较小(如n≤50),可采用直接插入或直接选择排序. * 当记录规模较小时,直接插入排序较好:否则因为

  • 基于C++实现的各种内部排序算法汇总 2015-02-17

    这篇文章主要介绍了基于C++实现的各种内部排序算法,非常经典,需要的朋友可以参考下 提起排序算法相信大家都不陌生,或许很多人已经把它们记得滚瓜烂熟,甚至随时可以写出来.是的,这些都是最基本的算法.这里就把各种内部排序算法总结归纳了一下,包括插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序.(另:至于堆排序算法,前面已经有一篇文章针对堆排序的算法实现做了详细的描述) C++实现代码如下: /*************

  • C++实现各种排序算法类汇总 2015-03-31

    这篇文章主要介绍了C++实现各种排序算法类,需要的朋友可以参考下 C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 te

  • java数组排序算法详解(转载) 2012-05-02

    import java.util.Random; /** * 排序测试类 * * 排序算法的分类如下: * 1.插入排序(直接插入排序.折半插入排序.希尔排序): * 2.交换排序(冒泡泡排序.快速排序): * 3.选择排序(直接选择排序.堆排序): * 4.归并排序: * 5.基数排序. * * 关于排序方法的选择: * (1)若n较小(如n≤50),可采用直接插入或直接选择排序. * 当记录规模较小时,直接插入排序较好:否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜. * (

  • java排序 2014-05-11

    Java排序算法:概述 排序是程序开发中一种非常常见的操作,对一组任意的数据元素(或记录)经过排序操作后,可以把它们变成一组按关键字排序的有序队列.有序的数据可以提高搜索和归并的效率,而且在之前的学习中发现有些算法需要在有序列表,数组等情况下才能使用,因此,给出未排序的数据集合,将这些数据用某种算法按某种方式重新排列,这就是排序. 对一个排序算法来说,一般从下面3个方面来衡量算法的优劣: 时间复杂度:主要分析关键字的比较次数和记录的移动次数. 空间复杂度:分析排序算法中需要多少辅助内存或者是磁盘

  • java插入排序 Insert sort实例 2014-02-22

    java插入排序 Insert sort实例代码,需要的朋友可以参考一下 //直接插入排序 void DirectInsertionSort(int* arr, int nLen) { int i, j; for (i=1; i<nLen; i++) { int temp = arr[i]; for (j=i-1; j>=0; j--) { if (temp < arr[j]) arr[j+1] = arr[j]; else break; } if (j+1 != i) arr[j+1]

  • c++几种基本的插入排序(图文) 2014-10-26

    这篇文章主要介绍了c++几种基本的插入排序(图文),需要的朋友可以参考下 1.插入排序 插入排序(Insertion Sort)是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间. 时间复杂度:O(n^2); 算法描述: 1.从第一个元素开始,该元素可以认为已

  • 二分插入排序 2013-06-25

    二分插入排序也称折半插入排序,基本思想是:设数列[0....n]分为两部分一部分是[0...i]为有序序列,另一部分是[i+1.....n]为无序序列,从无序序列中取一个数 x ,利用二分查找算法找到 x 在有序序列中的插入位置并插入,有序序列还是有序的,接下来重复上述步骤,直到无序序列全部插入有序序列 ,这是整个序列只剩下有序序列即有序了. void BinaryInsertSort(int *pArray, int len) { //刚开始设有序序列只有一个元素 pArray[0],无序序列

  • 学习javascript,实现插入排序实现代码 2014-09-19

    首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表").从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态. 插入排序 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表"). 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态. 重复2号步骤,直至原数列为空. 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现.它借助了"

  • PHP算法:直接插入排序 2011-07-11

    直接插入排序(Straight Insertion Sort)是一种最为简单的排序方法,因此也被称为简单插入排序. 直接插入排序的基本思想是:第i趟排序将序列中的第i+1个元素Ki+1插入到一个已经按值有序的子序列(k1,k2,...,ki)中合适的位置,使得插入后的序列依然保持按值有序. void insert_sort(ElemType a[],int n) //待排序元素用一个数组a表示,数组有n个元素 { int i,j; ElemType t; for ( i=1; i<n; i++)

  • 简单排序--冒泡排序,选择排序,插入排序,对象排序 2014-01-02

    1)冒泡排序 package sort; /** * 冒泡排序,每次把数组最大值送到未排序部分的最末端 * @author Administrator * */ public class BubbleSort { /** * 输入:无序数组 * 输出:有序数组 * length代表数组的实际长度 */ public int[] bubbleSort(int[] arrayNum,int length) { for(int i = length - 2 ; i >= 0; i --) for(in

  • 插入排序的算法分析 2014-08-05

    插入排序的算法分析 插入排序:对于少量元素的排序,他是一个有效的算法. 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下: 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素,在已经排序的元素序列中从后向前扫描 如果该元素(已排序)大于新元素,将该元素移到下一位置 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5 插入排序使用C实现: //插入排序 #include<stdio.h> int main(){ int

  • 常见排序算法:插入排序 2015-03-16

    插入排序是一种(或者一类)简单的排序算法.之所以说它是一类算法,是因为插入排序可以有变种,例如二分查找插入排序. 本文先讨论直接插入排序(简单插入排序). 算法概述/思路 直接插入排序的思路很容易理解,它是这样的: 1.把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的. 2.从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置. 3.重复上述过程直到最后一个元素被插入有序子数组中. 4.排序完成. 下面是插入排序的示意图(图片来自维基百科): 思

  • java实现折半排序算法 2014-11-12

    折半插入排序法,又称二分插入排序法,是直接插入排序法的改良版,也需要执行i-1趟插入,不同之处在于,第i趟插入,先找出第i+1个元素应该插入的的位置,假定前i个数据是已经处于有序状态. 折半插入排序(binary insertion sort)是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中.由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度. public static void halfSo

  • C++中十种内部排序算法的比较分析 2014-05-11

    本文给大家分享的是个人写的一段对C++中十种内部排序算法的比较分析的代码,主要在于测试10种排序方法的性能,给大家参考下吧. C++中十种内部排序算法的比较分析 #include<iostream> #include<ctime> #include<fstream> using namespace std; #define MAXSIZE 1000 //可排序表的最大长度 #define SORTNUM 10 //测试10中排序方法 #define max 100 //

  • Java实现常用的6种排序算法 2012-06-14

    1.插入排序 插入排序是一种通过不断地把新元素插入到已排好序的数据中的排序算法,常用的插入排序算法包括直接插入排序和shell排序. (1)直接插入排序 直接插入排序实现比较简单,但是直接插入没有充分的利用已插入的数据已经排序这个事实,因此有很多针对直 接插入排序改进的算法,例如折半插入排序等,下边是直接插入排序的Java实现: public static void insertSort(int[] elements){ for(int i = 1;i <elements.length; i++

  • 经典排序算法 2015-04-01

    冒泡排序:O(N*N) void bublesort(int a[],int n){ for(int i = 1;i < n;i++) { for(int j = 0; j < n - i;j++){ if(a[j] > a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } 直接插入: O(N*N) void insert_sort(int *arr,int n) { int i,j; for(i = 1 ; i