C++实现插入排序对整数数组排序

2024-09-27 15:23:02

利用插入排序，对整数数组排序

根据如下插入排序基本思想编程：

一个数显然是有序的，因此规模为1的排序问题能够求解；
如果能够为n-1个数排序，那么当有n个数时，只需先将前n-1个数排好序，再将最后一个数插入前面这n-1个有序数列中的合适位置即可。

例如：

要对3，6，2，4从小到大排序：

1、考虑规模为1的问题，即数字3，一个数显然是有序的；
2、规模为1的问题求解完毕后，加入新的数字6，将其放在3后面，得到序列3，6，从而解决了规模为2的问题；
3、规模为2的问题求解完毕后，加入新的数字2，将其放在3前面，得到序列2，3，6，从而解决了规模为3的问题；
4、规模为3的问题求解完毕后，加入新的数字4，将其放在2和3中间，得到序列2，3，4，6，从而解决了规模为4的问题，排序过程结束。

适用于初学者

#include <iostream>

using namespace std;

int main() {
  int i, j, num, temp;
  int intarray[10] = {2, 5, 1, 9, 10, 0, 4, 8, 7, 6};
  int new_intarray[10] = {0};
  //第一个数不用排序
  new_intarray[0] = intarray[0];
  for (i = 1; i < 10; ++i) {
    //开始排序第i个数，把它储存在一个临时变量
    num = intarray[i];
    //判断第i个数和第i-1个数的大小，如果比第i-1个数大，则把第i个数放在新数组的第i位
    if (num >= new_intarray[i - 1])new_intarray[i] = num;
      //如果不是的话，依此从大到小交换位置，直到大小顺序符合
    else {
      new_intarray[i] = new_intarray[i - 1];
      new_intarray[i - 1] = num;
      //交换大小顺序错误的两个
      for (j = i - 1; j > 0; --j) {
        if (new_intarray[j] < new_intarray[j - 1]) {
          temp = new_intarray[j];
          new_intarray[j] = new_intarray[j - 1];
          new_intarray[j - 1] = temp;
        } else break;
      }
    }
  }
  for (i = 0; i < 10; ++i)cout << new_intarray[i] << '\t';
  return 0;
}

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

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

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

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

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

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

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

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

利用插入排序,对整数数组排序根据如下插入排序基本思想编程: 一个数显然是有序的,因此规模为1的排序问题能够求解: 如果能够为n-1个数排序,那么当有n个数时,只需先将前n-1个数排好序,再将最后一个数插入前面这n-1个有序数列中的合适位置即可. 例如: 要对3,6,2,4从小到大排序: 1.考虑规模为1的问题,即数字3,一个数显然是有序的: 2.规模为1的问题求解完毕后,加入新的数字6,将其放在3后面,得到序列3,6,从而解决了规模为2的问题: 3.规模为2的问题求解完毕后,加入新的数字2,将
php插入排序法实现数组排序实例

本文实例讲述了php插入排序法实现数组排序的方法.分享给大家供大家参考.具体分析如下: 插入排序法的基本思路:同样以案例来说明,还是以$arr = array(2,6,3,9),由大到小排序. 实现原理:假设(并不实际创建)有一个有序数组$arr = array(2),用$arr[1]=6来与它进行比较,如果6>2,由把$arr[0]后移到$arr[1]位置,而6插入到$arr[0]位置.接着,$arr[2]=3与$arr[1]=2比较,3>2,则$arr[1]=2继续后移到$arr[2]位置
C语言数据结构经典10大排序算法刨析

1.冒泡排序 // 冒泡排序 #include <stdlib.h> #include <stdio.h> // 采用两层循环实现的方法. // 参数arr是待排序数组的首地址,len是数组元素的个数. void bubblesort1(int *arr,unsigned int len) { if (len<2) return; // 数组小于2个元素不需要排序. int ii; // 排序的趟数的计数器. int jj; // 每趟排序的元素位置计数器. int itmp
C#实现快速排序算法

快速排序是应用最广泛的排序算法,流行的原因是它实现简单,适用于各种不同情况的输入数据且在一般情况下比其他排序都快得多. 快速排序是原地排序(只需要一个很小的辅助栈),将长度为 N 的数组排序所需的时间和 N lg N 成正比. 1.算法快速排序也是一种分治的排序算法.它将一个数组分成两个子数组,将两部分独立地排序. 快速排序和归并排序是互补:归并排序是将数组分成两个子数组分别排序,并将有序数组归并,这样数组就是有序的了:而快速排序将数组通过切分变成部分有序数组,然后拆成成两个子数组,当两个子数
C语言中数组排序浅析

目录前言一.插入排序 1.思路 2.具体步骤 3.代码实现 4.复杂度二.冒泡排序 1.思路 2.具体步骤 3.代码实现 4.复杂度三.选择排序 1.思路 2.具体步骤 3.代码实现 4.复杂度四.希尔排序 1.思路 2.具体步骤 3.代码实现 4.复杂度例题及其解答题目描述输入描述输出描述示例1 示例2 解答结语前言本文介绍了几种c语言中对乱序数组的排序方式. 具体的内容有: 插入排序: 冒泡排序: 选择排序: 希尔排序: 具体内容详见下文. 一.插入排序 1.思路
Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

本文实例讲述了Go语言实现冒泡排序.选择排序.快速排序及插入排序的方法.分享给大家供大家参考.具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法.排序算法有许多种,这里介绍4中排序算法:冒泡排序,选择排序,快速排序和插入排序,以从小到大为例. 一.冒泡排序冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数.经过第一次遍历之后,最大的数就在最右侧了:第二次遍历之后,第二大的数就在右数第二个位置了:以此类推. 复制代码代码如下:
浅谈插入排序算法在Python程序中的实现及简单改进

Python实现插入排序的一般范例为: #coding=cp936 #coding=cp936 #插入排序算法 def InsertionSort(A): for j in range(1,len(A)): key = A[j] i = j-1 #向前查找插入位置 while i>=0 and A[i]>key: A[i+1] = A[i] i = i-1 A[i+1] = key #初始化输入数据 A = [] input = raw_input('please input some num
array_multisort实现PHP多维数组排序示例讲解

array_multisort - 对多个数组或多维数组进行排序说明 bool array_multisort ( array ar1 [, mixed arg [, mixed ... [, array ...]]] ) array_multisort (PHP 4, PHP 5) 如果成功则返回 TRUE,失败则返回 FALSE. array_multisort() 可以用来一次对多个数组进行排序,或者根据某一维或多维对多维数组进行排序. 关联(string)键名保持不变,但数字键名会被重
php对数组排序代码分享

复制代码代码如下: <?php class='pingjiaF' frameborder='0' src='http://www.jb51.net' scrolling='no'> 对数组排序 usort() 函数使用用户自定义的函数对数组排序. */ function cmp($a, $b) //用户自定义回调函数 { if($a==$b) //如果两个参数相等 { return 0; //返回0 } return($a>$b)?-1:1; //如果第1个参数大于
php对数组排序的简单实例

复制代码代码如下: <?php class='pingjiaF' frameborder='0' src='http://www.jb51.net' scrolling='no'> 对数组排序 usort() 函数使用用户自定义的函数对数组排序. */ function cmp($a, $b) //用户自定义回调函数 { if($a==$b) //如果两个参数相等 { return 0; //返回0 } return($a>$b)?-1:1; //如果第1个参数大于

C++实现插入排序对整数数组排序

相关推荐

随机推荐