C++实现折半插入排序（BinaryInsertSort）

本文实例为大家分享了C++实现折半插入排序的具体代码，供大家参考，具体内容如下

一、思路：

较插入排序，减少了比较的次数，但是插入时间还是一样。

（1）按二分查找的方法，查找V[i]在V[0],V[1]…V[i-1]中插入的位置；

（2）将插入位置的元素向后顺移。

二、实现程序：

// 二分插入：较插入排序，减少了比较的次数，但是插入时间还是一样
// 时间复杂度还是:O(n*n)
#include <iostream>
using namespace std;

const int maxSize = 20;

template <class T>
void BinInsertSort(T arr[], const int left, const int right) {
 int i, j, low, high, mid;
 T temp;

 for(i = left+1; i <= right; i++) {
  temp = arr[i]; // 暂存arr[i]
  low = left;
  high = i-1; // low、high作为折半查找的上、下界
  while(low <= high) { // 用折半查找的方法，查找arr[i]的插入位置
   mid = (low + high) / 2;
   if(temp < arr[mid])
    high = mid - 1;
   else
    low = mid + 1;
  } // while
  for(j = i-1; j >= low; j--)
   arr[j+1] = arr[j]; // 顺序后移
  arr[low] = temp; // 回填
 } // for
} // BinInsertSort

int main(int argc, const char * argv[]) {
 int i, n, arr[maxSize];

 cout << "请输入要排序的数的个数：";
 cin >> n;
 cout << "请输入要排序的数：";
 for(i = 0; i < n; i++)
  cin >> arr[i];
 cout << "排序前：" << endl;
 for(i = 0; i < n; i++)
  cout << arr[i] << " ";
 cout << endl;
 BinInsertSort(arr, 0, n-1);
 cout << "排序后：" << endl;
 for(i = 0; i < n; i++)
  cout << arr[i] << " ";
 cout << endl;
 return 0;
}

测试结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

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

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

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

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

    本文实例为大家分享了C++插入排序算法实例的具体代码,供大家参考,具体内容如下 基本思想 每次将一个待排序的元素,按其大小插入到已经排好序的子序列的适当位置,知道全部元素插入完成为止. 直接插入排序 1.排序思路 arr[0...i-1]为有序区(刚开始时i=1,有序区只有arr[0]一个元素),arr[i...size]为待排序区,每次将待排序区的第一个元素arr[i]插入到有序区中的适当位置,每趟操作都使有序区增加一个元素,待排序区减少一个元素. 2.排序算法 void InsertSort

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

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

  • C++排序算法之插入排序

    本文实例为大家分享了C++排序算法之插入排序的具体代码,供大家参考,具体内容如下 1.基本思想:将未排序的数据元素按大小顺序插入到已排好序数据序列中,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入. 例如:对2, 4, 3, 1, 6, 5进行插入排序.进行排序前,默认2是有序的,为有序区,而4, 3, 1, 6, 5是无序的,为无序区.将这五个无序的数按从小到大的顺序插入到有序区. 第一趟排序:将4与有序区的2比较,若小于2则插到2前面,大于2插到2后面.操作后有序区为:{2,

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

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

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

  • c++插入排序详解

    c++插入排序详解

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

  • 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++实现折半插入排序（BinaryInsertSort）

    本文实例为大家分享了C++实现折半插入排序的具体代码,供大家参考,具体内容如下 一.思路: 较插入排序,减少了比较的次数,但是插入时间还是一样. (1)按二分查找的方法,查找V[i]在V[0],V[1]-V[i-1]中插入的位置: (2)将插入位置的元素向后顺移. 二.实现程序: // 二分插入:较插入排序,减少了比较的次数,但是插入时间还是一样 // 时间复杂度还是:O(n*n) #include <iostream> using namespace std; const int maxSi

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

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

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

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

    首先看一下例子,将数据一个个的插入到一个列表中,插入后这个列表就排序好了 注意:这个列表是递增的,而且内存空间已分配好,只是没有填充真正的数据,如下代码: 复制代码 代码如下: 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 <

  • JS折半插入排序算法实例

    本文实例讲述了JS折半插入排序算法.分享给大家供大家参考,具体如下: function pushArrayWithIndex(arr, index, value) { // 将元素添加到数组的指定位置 var temArr = arr.slice(0, index); temArr.push(value); return temArr.concat(arr.slice(index)); } /* test for pushArrayWithIndex var arr = [1, 2, 3, 4,

  • 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 while (low <= high) { int mid = (low + high) / 2; IF (Temp &l

  • Java实现直接插入排序和折半插入排序算法示例

    Java实现直接插入排序和折半插入排序算法示例

    直接插入排序​ 1 排序思想: 将待排序的记录Ri插入到已经排好序的记录R1,R2,--,R(N-1)中. 对于一个随机序列而言,就是从第二个元素开始,依次将这个元素插入到它之前的元素中的相应位置.它之前的元素已经排好序. 第1次排序:将第2个元素插入到前边的有序列表(此时前边只有一个元素,当然是有序的),之后,这个序列的前2个元素就是有序的了. 第2次排序:将第3个元素插入到前边长度为2的有序列表,使得前2个元素是有序的. 以此类推,直到将第N个元素插入到前面长度为(N-1)的有序列表中. 2

  • Java实现直接插入排序与折半插入排序的示例详解

    Java实现直接插入排序与折半插入排序的示例详解

    目录 1.直接插入排序 2. 折半插入排序 1.直接插入排序 插入排序的基本思想: 主要分为两个区间, 无序区间和有序区间, 每次选择无序区间的第一个元素, 在有序区间内选择合适的位置进行插入操作. 插入过程如下图所示: 代码: public class InsertSort { public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int

  • java数据结构与算法之插入排序详解

    本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

  • Ruby实现插入排序算法及进阶的二路插入排序代码示例

    基础 将一个记录插入到一个已经排序好的表中,以得到一个记录增一的有序表.并且最关键的一点就是它把比当前元素大的记录都往后移动,用以空出"自己"该插入的位置.当n-1趟插入完成后该记录就是有序序列. def insertSort(tarray) i=1 while(i < tarray.size) do if tarray[i] < tarray[i-1] j=i-1 x=tarray[i] #puts x.class #puts tarray[i].class tarray

  • 详解直接插入排序算法与相关的Java版代码实现

    详解直接插入排序算法与相关的Java版代码实现

    直接插入排序 直接插入排序的思路很容易理解,它是这样的: 1.把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的. 2.从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置. 3.重复上述过程直到最后一个元素被插入有序子数组中. 4.排序完成. 示例: 思路很简单,但代码并非像冒泡排序那么好写.首先,如何判断合适的位置?大于等于左边.小于等于右边?不行,很多边界条件需要考虑,而且判断次数太多.其次,数组中插入元素,必然需要移动大量元素,如何控制它们

随机推荐