插入排序是一种简单的排序方法,因为的实现比较简单,所以在数据量较少时应用很广泛。插入排序根据其插入的不同方式,可以分为直接插入排序,折半插入排序,2-路插入排序,表插入排序和希尔排序。在这里我将一一写出各种插入排序的算法代码。
直接插入排序
template <class T>
void InsertSort(T a[], int len)
{
      int i, j;
      T temp;
      for (i=1; i<len; i++)
      {
            temp = a[i];
            for (j=i-1; j>=0 && a[j]>temp; j--)//元素后移
                  a[j+1] = a[j];
            a[j+1] = temp;  //插入
      }
}
      有些算法把a[0]设置为临时数据存放处(即原数组中a[0]未存储元素),这样就可以少进行一些判断,在数据量较大时可以节省一些时间,算法如下:
template <class T>
void InsertSort(T a[], int len)
{
      int i, j;
      for (i=1; i<len; i++)
      {
            a[0] = a[i];
            for (j=i-1; a[j]>temp; j--)
                  a[j+1] = a[j];
            a[j+1] = temp;
      }
}
折半插入排序法
      由于插入排序的基本操作是在一个有序表中进行查找和插入,则这个查找操作可以利用折半查找来实现。但是折半插入排序仅减少了元素间的比较次数,而元素的移动次数不变,因此折半插入排序法的时间复杂度仍为O(n^2)。算法如下:
template <class T>
void HalfInsertSort(T a[], int len)
{
      int i, j;
      int low, high, mid;
      T temp;
      for (i=1; i<len; i++)
      {
            temp = a[i];
            low = 0;
            high = i - 1;
            while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
            {
                  mid = (low + high) / 2;
                  if (a[mid] > temp)
                        high = mid - 1;
                  else
                        low = mid + 1;
            } //while
            
            for (j=i-1; j>high; j--)//元素后移
                  a[j+1] = a[j];
            a[high+1] = temp; //插入
      }//for
}

希尔排序法
      希尔排序法又称缩小增量排序法,它也是插入排序类的方法,但在时间效率上较前面几种插入排序算法有较大的改进。
      希尔排序法通过比较相距一定间隔的元素来工作,各趟比较所用的距离随着算法的进行而减小,直到比较相邻元素的最后一趟排序为止。算法如下:
template <class T>
void ShellSort(T a[], int len)
{
      for (int increment=len/2; increment>0; increment/=2)
      {
            for (int i=increment; i<len; i++)
            {
                  T temp = a[i];
                  int j = i;
                  for (; j>=increment; j-=increment)//元素后移
                  {
                        if (temp < a[j-increment])
                              a[j] = a[j-increment];
                        else
                              break;
                  }
                  a[j] = temp; //插入
            }//for
      }//for
}
注:缺2-路插入排序和表插入排序,有意者请补上!谢谢!
Posted on 2006-06-20 23:22 梦想飞扬 阅读(3314) 评论(1)  编辑 收藏 引用

Feedback

# re: 我所理解的插入排序算法  回复  更多评论   

2008-10-24 16:16 by 么样
你就是一个傻逼,要写就写全,就会写最简单的

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理