引用
笔记--插入排序
1.插入排序类
package com.flysnow.chap03;
/**
* 插入排序
* @author 飞雪无情
* @since:2010-3-25
*/
public class ArrayInsert {
private long[] a;
private int nElems;
public ArrayInsert(int max){
a=new long[max];
nElems=0;
}
/**
* 插入元素
* @param value
*/
public void insert(long value){
a[nElems]=value;
nElems++;
}
/**
* 打印元素
*/
public void display(){
for(int i=0;i<nElems;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
/**
* 插入排序排序
*/
public void insertionSort(){//比较次数O(N^2),但是复制比交换的时间要少。比冒泡快一倍,比插入略快
int out,in;
for(out=0;out<nElems;out++){
long temp=a[out];//标记
in=out;
while(in>0&&a[in-1]>=temp){//大于标记值右移
a[in]=a[in-1];
--in;
}
a[in]=temp;
}
}
}
2.插入排序测试
package com.flysnow.chap03;
import java.util.Random;
/**
* 插入排序测试
* @author 飞雪无情
* @since:2010-3-25
*/
public class InsertSortApp {
public static void main(String[] args){
ArrayInsert insert=new ArrayInsert(100);
Random random=new Random();
for(int i=0;i<20;i++){//添加20个随机数
insert.insert((long)(random.nextFloat()*100));
}
insert.display();//未排序
insert.insertionSort();//排序
insert.display();//排序后
}
}
3.总结
算法思想:
- 选择第二个(1号)数据为标记,和其前面的数据(0号)比较,如果1号数据小于0,则0号后移变成1号,而原来的1号数据占据原来的0号位置。
- 选择第三个(2号)数据位标记,和其前面的数据(0号,1号)循环比较,如果前面的数据比标记大,则该数据后移。
- 依次类推,直到完成排序。。循环条件就是下标大于0并且前面的数据大于等于标记值。
- 描述: 插入排序
- 大小: 39.9 KB
- 描述: 几种简单算法的比较
- 大小: 70.9 KB
分享到:
相关推荐
用函数实现直接插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 ...
用函数实现折半插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 5...
直接插入排序的四种实现代码, 见博客 直接插入排序(Straight Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序...
* --插入排序-- * 假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大, * 则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止. * 这具算法在排完前k个数之后,可以...
/** 选择排序,每轮,第一个元素与每个元素比较,选择小的交换 */ public static void selectionSort(int[] ary){ for(int i=0; i; i++){ for(int j=i+1; j; j++){ if(ary[i]>ary[j]){ int t=ary[i]; ary[i]=ary...
折半插入排序(Binary Insertion Sort)是直接插入排序的一种改进版本,主要区别在于寻找插入位置的方式。在直接插入排序中,我们使用线性搜索来找到新元素应该插入的位置,而在折半插入排序中,我们使用二分搜索来...
第四种排序方法
使用插入排序算法对输入的n个整数,按照从小到大的顺序排序。 Input Description 第一行输入一个整数n(0)。 第二行输入n个整数。 Output Description 输出排序后的整数,每个整数之间以一个空格分隔。注意:最后...
插入排序算法C语言程序,算法思路:先对数组前两个数进行大小比较,将第三个数与前两个数比较,插入合适位置,再将第四个数与前三个数比较并插入,以此类推
2. (共12分)已知数据序列为(12,5,9,20,6,31,24),对该项数据序列进行排序,分别写出直接插入排序、简单选择排序、快速排序、堆排序、二路归并排序及基数排序第一趟升序排序结果(其中堆排序的第一趟指序列...
数据结构报告c++,简单选择排序,冒牌排序,插入排序,快速排序,两路合并排序,堆排序,几种排序方法的比较,有详细的源代码和实验报告
第四章 简单排序(C++)_PDF(2020.06.10).rar
1直接插入排序 * 基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序 2冒泡排序 * 基本...
常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显,一般使用递归方式实现,但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。本文搜集发布四种...
直接插入排序的算法: 1.从第一个元素开始,该元素可以认为已经被排序 2.取出下一个元素,在已经排序的元素序列中从后向前扫描 3.如果该元素(已排序)大于新元素,将该元素移到下一位置 4.重复步骤3,直到找到已...
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。 算法描述: ⒈ 从第一个元素开始,该元素可以认为已经被排序 ⒉ 取出下一个元素,在已经排序的元素序列中...
再来看第四个数字,这个数字是2,我们将2和它左边的数字相比,都比2大,所以就将2一路往左移动,一直移到2的左边是1,这时候排序变成了 “1,2,4,5,3 ” 最后,我们检查第五个数字,这个数字是3,3必须往左移,...
第三十四课:插入排序,快速排序 第三十五课:实验七 查找 第三十六课:选择排序,归并排序 第三十七课:实验八 排序实验 第三十八课:文件概念,顺序文件 第三十九课:索引文件 第四十课:总复习
例如:对2, 4, 3, 1, 6, 5进行插入排序。进行排序前,默认2是有序的,为有序区,而4, 3, 1, 6, 5是无序的,为无序区。将这五个无序的数按从小到大的顺序插入到有序区。 第一趟排序:将4与有序区的2比较,若小于2则插...
第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 第一行:初始建堆后的结果 其后各行输出交换堆顶元素并调整堆的结果,数据之间用一个空格分隔 Sample Input 10 5 4 8 0 9 ...