一、插入排序思想:
将位置为1(即下标为1)的元素取出复制到temp的临时变量,然后将它与位置1之前(当然这里只有0)的元素进行比较,如果temp中的值比位置0的值大,则直接将temp复制到位置1。如果它比位置0的值小,则将位置0的值向右移动一位,然后将temp复制到位置0。这样前两位元素就局部有序了。
接下来,取出位置2上的元素复制到temp临时变量,将它与2之前的两个元素进行比较,如果比它们都大,就将它放回位置2;如果比位置1上的小,而比位置0上的大,则将位置1复制到位置2,然后将temp复制到位置1;如果比它们两个都小,则将它们两分别向后移动一位,然后将temp复制到位置0。依次类推。
因此,可以发现插入排序是属于局部有序的,对于局部本来就有顺序的数组来说,插入排序无疑是一种很好的选择。
二、插入排序算法Java描述
package com.solid.array;
public class InsertSort {
//数组对象
private long[] arr;
//数组元素个数
private static int nElems;
/**
* 构造方法
* @param max
*/
public InsertSort(int max) {
arr = new long[max];
nElems = 0;
}
/**
* 插入元素
* @param value
*/
public void insert(long value) {
arr[nElems] = value;
nElems++;
}
/**
* 插入排序算法
*/
public void insertSort() {
int in, out;
for(out=1; out<nElems; out++) {
long temp = arr[out];
in = out;
while (in > 0 && arr[in-1] >= temp) {
arr[in] = arr[in-1];
--in;
}
arr[in] = temp;
}
}
/**
* 显示数组中的所有元素
*/
public void display() {
for(int i=0; i<nElems; i++) {
System.out.print("arr["+i+"]=" + arr[i] + " ");
}
System.out.println();
}
}
分享到:
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半插入排序 22、冒泡排序 23、快速排序 24...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
冒泡排序、快速排序、简单插入排序、希尔排序、简单选择排序、堆叠排序六种数据结构必考的排序方式理解
交换排序 选择排序 冒泡排序 插入排序
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
插入排序插入排序插入排序插入排序插入排序插入排序插入排序
冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
此案例难度系数4,属于Scratch高级编程,插入排序相对而言比选择排序和冒泡排序理解起来要难一点,但是还是相对简单的排序,尤其是对少量元素排序的时候,效率较高;综合考查说话、随机数、无限循环(条件循环)、...
c++ 选择排序 插入排序 快速排序 使用模板写的,感觉不错,哈哈,希望对大家有帮助
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
插入排序,比较常见的排序算法之一。这是一个例子,一个关于插入排序的例子。
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...