c++几种基本的插入排序(图文)

1.插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
时间复杂度:O(n^2);

算法描述:

1.从第一个元素开始,该元素可以认为已经被排序
2.取出下一个元素,在已经排序的元素序列中从后向前扫描
3.如果该元素(已排序)大于新元素,将该元素移到下一位置
4.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5

动画演示:

作者:Swfung8

算法演示:

/*
**直接插入排序
*/
void InsertSort(int a[], int len)
{
  int i, j, key;
  for(i = 1; i < len; ++i){
    key = a[i];
    for(j = i-1; j >=0; --j){
      if(a[j] > key)
        a[j+1] = a[j];
      else
        break;
    }
    a[j+1] = key;
  }
} 

2.折半插入排序

折半插入排序(binary insertion sort)是对插入排序算法的一种改进,所谓排序算法过程,就是不断的依次将元素插入前面已排好序的序列中。时间复杂度O(n^2);

算法描述:

在将一个新元素插入已排好序的数组的过程中,寻找插入点时,将待插入区域的首元素设置为a[low],末元素设置为a[high],则轮比较时将待插入元素与a[m],其中m=(low+high)/2相比较,如果比参考元素大,则选择a[low]到a[m-1]为新的插入区域(即high=m-1),否则选择a[m+1]到a[high]为新的插入区域(即low=m+1),如此直至low<=high不成立,即将此位置之后所有元素后移一位,并将新元素插入a[high+1]

算法演示:

/*
**折半插入排序
*/
void BinsertSort(int a[], int len)
{
  int i, j;
  int low, high, mid;
  int key;
  for(i = 1; i < len; i++){
    key = a[i];
    low = 1; high = i-1;
    while (low <= high){
      mid = (low+high)/2;
      if(key < a[mid])
        high = mid-1;
      else
        low = mid+1;
    }
    for(j = i-1; j >=high+1; --j)
      a[j+1] = a[j];
    a[high+1] = key;
  }
}

3.希尔排序

希尔排序,也称为递减增量排序算法,是插入排序的一种高效的改进版本。
希尔排序是一种稳定的排序算法,时间复杂度为O(n^3/2);
希尔算法是基于插入排序的一下两点性质而提出改进方法的:
*插入排序在对几乎已经排好的数据操作时,效率高,即可达到线性排序的效率;
*但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

算法描述:

1.先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序
2.然后取 d2(d2 < d1)
3.重复上述分组和排序操作;直到取 di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序。一般选 d1 约为 n/2,d2 为 d1 /2, d3 为 d2/2 ,…, di = 1。

动画演示:

1.假设有数组 a = [80, 93, 60, 12, 42, 30, 68, 85, 10],首先取 d1 = 4,将数组分为 4 组,如下图中相同颜色代表一组:

2.然后分别对 4 个小组进行插入排序,排序后的结果为:

3.然后,取 d2 = 2,将原数组分为 2 小组,如下图:

4.然后分别对 2 个小组进行插入排序,排序后的结果为:

5.最后,取 d3 = 1,进行插入排序后得到最终结果:

算法演示:

/*
**希尔排序
*/
void ShellSort(int a[], int n)
{
  int i, j, gap;

  for(gap = n/2; gap>0; gap /= 2) //步长
    for(i = 0; i < gap; ++i){
      for(j = i+gap; j<n;j+=gap){
        if(a[j] < a[j-gap]){
          int temp = a[j];
          int k = j-gap;
          while(k>=0 && a[k] > temp){
            a[k+gap] = a[k];
            k -= gap;
          }
          a[k+gap] = temp;
        }
      }
    }
}

4.example code:

int main()
{
  int i;
  int a[] = {80, 93, 60, 12, 42, 30, 68, 85, 10};
  InsertSort(a, sizeof(a)/sizeof(a[0]));
  for(i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
    printf("%d ", a[i]);
  printf("\n");
  BinsertSort(a, sizeof(a)/sizeof(a[0]));
  for(i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
    printf("%d ", a[i]);
  printf("\n");
  ShellSort(a, sizeof(a)/sizeof(a[0]));
  for(i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
    printf("%d ", a[i]);
  printf("\n");
  return 0;
} 
(0)

相关推荐

  • c++插入排序详解

    说一说插入排序 插入排序的基本操作就是将一个数据插入到已经排序好序的数据中,从而得到一个新的,个数加一的有序数据,算法适用与少量的数据的排序.时间复杂度O(n^2),是稳定的排序算法. 基本思想:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件的适当位置上去,直到全部插入完为止. 原理示意图: 函数段的c++代码实现: 全部代码如下: #include <iostream> using namespace std; void insert_sort(int* a,int b)/

  • C++ 排序插入排序实例详解

    排序--插入排序 插入排序的基本思想是每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止.常见的插入排序有插入排序(Insertion Sort),希尔排序(Shell Sort),二叉查找树排序(Tree Sort),图书馆排序(Library Sort),Patience排序(Patience Sort). 简单实例: #include <iostream> using namespace std; void InsertSort( i

  • C++实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

  • C++插入排序算法实例

    插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1

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

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

  • 使用Node.js实现ORM的一种思路详解(图文)

    ORM是O和R的映射.O代表面向对象,R代表关系型数据库.二者有相似之处同时也各有特色.就是因为这种即是又非的情况,才需要做映射的. 理想情况是,根据关系型数据库(含业务需求)的特点来设计数据库.同时根据面向对象(含业务需求)的特点来设计模型(实体类).然后再去考虑如何做映射.但是理想很骨jian感dan,现实太丰fu满za. 没见哪个ORM是这么做的,也没见哪位高手会这么做设计.那么实际情况是什么样子的呢?以.net的Entity Framework为例. DB frist,就是先设计好数据库

  • 新10种领带的打法 图文教程

    1.The Windsor Knot 温莎结 因温莎公爵而得名的领带结,是最正统的领系法,打出的结成正三角形,饱满有力,适合搭配宽领衬衫,用于出席正式场合.切勿使用面料过厚的领带来打温莎结.2.The four-in-hand Knot 四手结 通过四个步骤就能完成打结,故名为"四手结",它是最便捷的领带系法,适合宽度较窄的领带,搭配窄领衬衫,风格休闲,适用于普通场合. 3.The Half-Windsor Knot 半温莎结(十字结) 顾名思义,它是温莎结的改良版,较温莎结更为便捷,

  • 微信公众帐号开发教程之图文消息全攻略

    引言及内容概要 已经有几位读者抱怨"柳峰只用到文本消息作为示例,从来不提图文消息,都不知道图文消息该如何使用",好吧,我错了,原本以为把基础API封装完.框架搭建好,再给出一个文本消息的使用示例,大家就能够照猫画虎的,或许是因为我的绘画功底太差,画出的那只猫本来就不像猫吧-- 本篇主要介绍微信公众帐号开发中图文消息的使用,以及图文消息的几种表现形式.标题取名为"图文消息全攻略",这绝对不是标题党,是想借此机会把大家对图文消息相关的问题.疑虑.障碍全部清除掉. 图文消

  • JavaScript中九种常用排序算法

    笔试面试经常涉及各种算法,本文简要介绍常用的一些算法,并用JavaScript实现. 一.插入排序 1)算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间. 2)算法描述和实现 一般来说,插入排序都采

  • c语言实现的几种常用排序算法

    概述 最近重新回顾了一下数据结构和算法的一些基本知识,对几种排序算法有了更多的理解,也趁此机会通过博客做一个总结. 1.选择排序-简单选择排序 选择排序是最简单的一种基于O(n2)时间复杂度的排序算法,基本思想是从i=0位置开始到i=n-1每次通过内循环找出i位置到n-1位置的最小(大)值. 算法实现: void selectSort(int arr[], int n) { int i, j , minValue, tmp; for(i = 0; i < n-1; i++) { minValue

  • Java中七种排序算法总结分析

    目录 前言:对文章出现的一些名词进行解释 一.插入排序 1.基本思想 2.直接插入排序 3.希尔排序(缩小增量排序) 二.选择排序 1.基本思想 2.直接选择排序 3.堆排序 三.交换排序 1.基本思想 2.冒泡排序 3.快速排序(递归与非递归) 1.Hoare版 2.挖坑法 3.前后标记法(难理解) 4.快速排序优化 5.快速排序非递归 6.相关特性总结 四.归并排序(递归与非递归) 前言:对文章出现的一些名词进行解释 排序: 使一串记录,按照其中的某个或某些关键字的大小,递增或者递减排列起来

  • C语言深入浅出讲解直接插入排序算法的实现

    目录 直接插入排序 1.基本思想 2.算法实现 3.时间复杂度 插入排序分为两种:直接插入排序&希尔排序 直接插入排序 1.基本思想 直接插入排序是一种简单的插入排序算法,其基本思想是: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 . 说得通俗一点就是: 假设区间[0, end]有序,将end+1位置的值插入到[0, end]中,保持区间[0, end+1]依旧有序. 生活中我们玩扑克牌时,就用了插入排序的思想. 在这里,

  • C语言常见排序算法之插入排序(直接插入排序,希尔排序)

    目录 前言 一.直接插入排序 1.1 基本思想 1.2 算法思想 1.3 程序实现 1.4 直接插入排序的总结 二.希尔排序 2.1 算法思想 2.2 程序实现 2.3 希尔排序的特征总结 前言 本期为大家带来的是常见排序算法中的插入排序,主要有直接插入排序以及它的升级版——希尔排序,包您一看就会,快来试试吧~ 一.直接插入排序 1.1 基本思想 在生活当中,这种排序方式处处可见: 在玩扑克牌的时候我们就会采用插入排序的思想,当我们拿起第二张牌时,就会下意识的与第一张牌进行比较,如果比第一张牌小

  • Java实现折半插入排序算法的示例代码

    目录 排序算法介绍 折半插入排序 原理 代码实现 复杂度分析 算法实践 排序算法介绍 排序算法是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序.最终序列按照一定的规律进行呈现. 在排序算法中,稳定性和效率是我们经常要考虑的问题. 稳定性:稳定是指当两个相同的元素同时出现于某个序列之中,则经过一定的排序算法之后,两者在排序前后的相对位置不发生变化. 复杂度分析: (1)时间复杂度:即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量. (2)空

随机推荐