排序算法之插入排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法之插入排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1842字,纯文字阅读大概需要3分钟。
内容图文
排序算法-插入排序
基本介绍
插入排序属于内部排序,是对要排序的元素以插入的方式寻找该元素的适当位置,以达到排序的目的
算法思想
把n个待排序的元素看成一个有序表和一个无序表
开始时,有序表只含有一个元素,无序表中有n-1个元素
排序过程中每次从无序表取出第一个元素,把它的排序码依次和有序表元素的排序码进行比较
将它插入到有序表中的适当位置,使之称为新的有序表
代码实现
package cn.imut.sort;
import com.sun.org.apache.xpath.internal.SourceTree;
import java.util.Arrays;
//插入排序
public class InsertSort {
public static void main(String[] args) {
int[] arr = {101, 34, 119, 1};
insertSort(arr);
}
//插入排序
public static void insertSort(int[] arr) {
for(int i = 1; i < arr.length; i++) {
int insertVal = arr[i]; //要插入的数(第二个列表的首位)
int insertIndex = i - 1; //要插入数的前一个数的下标(第一个列表的末尾的编号)
//注:第一个列表是有序的
//insertIndex > 0 保证 插入的位置不越界
//insertVal < arr[insertIndex] 说明 要插入的数还没有找到插入的位置,否则它正常加入到最后即可
//接着将 arr[insertIndex] 后移
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//退出while循环时,说明插入的位置找到,insertIndex + 1
arr[insertIndex + 1] = insertVal;
System.out.println("第" + i + "轮插入");
System.out.println(Arrays.toString(arr));
}
}
}
插入排序速度测试
public static void main(String[] args) {
int[] arr = new int[80000];
for(int i = 0; i < 80000; i++) {
arr[i] = (int)(Math.random() * 8000000); //生成一个[0,8000000) 数
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format = simpleDateFormat.format(date1);
System.out.println("排序前的时间是:" + format);
insertSort(arr);
Date date2 = new Date();
String format1 = simpleDateFormat.format(date2);
System.out.println("排序后的时间是:" + format1);
}
插入排序测试八万个数据,只需1秒
内容总结
以上是互联网集市为您收集整理的排序算法之插入排序全部内容,希望文章能够帮你解决排序算法之插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。