排序算法--插入排序
这个是我对插入排序的理解写的一个简单例子,可能和其他人的理解看法不同。
插入排序:
1,创建一个空的列表,用来保存排序后的列表,代号"有序列表"
2,从原列表中取出一个数,将其插入到"有序列表",并使"有序列表"保持有序状态
3,重复第2步直到原列表末尾
这种排序的平均时间复杂度是平方级的,效率不高,容易实现
/** * InsertionSort.java * * @author xieyan * @date 2013/06/20 * @version 1.0 */ package sort; import java.util.ArrayList; import java.util.List; /** * InsertionSort.java */ public class InsertionSort { /* * 插入排序: 1,创建一个空的列表,用来保存排序后的列表,代号"有序列表" * 2,从原列表中取出一个数,将其插入到"有序列表",并使"有序列表"保持有序状态 * 3,重复第2步直到原列表末尾 * * 这种排序的平均时间复杂度是平方级的,效率不高,容易实现 */ /** * insertionSortAsc * * <PRE> * 升序 * </PRE> * * @param arr */ public static List<Integer> insertionSortAsc(int[] arr) { if (arr == null) { return null; } List<Integer> result = new ArrayList<Integer>(); for (int i = 0; i < arr.length; i++) { int obj = arr[i]; if (i == 0) { result.add(obj); } else { for (int j = 0; j < result.size(); j++) { if (obj <= result.get(j)) { result.add(j, obj); break; } if (j == result.size() - 1) { result.add(obj); break; } } } } return result; } /** * insertionSortAsc * * <PRE> * 降序 * </PRE> * * @param arr */ public static List<Integer> insertionSortDesc(int[] arr) { if (arr == null) { return null; } List<Integer> result = new ArrayList<Integer>(); for (int i = 0; i < arr.length; i++) { int obj = arr[i]; if (i == 0) { result.add(obj); } else { for (int j = 0; j < result.size(); j++) { if (obj >= result.get(j)) { result.add(j, obj); break; } if (j == result.size() - 1) { result.add(obj); break; } } } } return result; } public static void main(String[] args) { int[] a = new int[] { 5, 7, 8, 3, 4, 2, 9, 1, 6 }; List<Integer> b = insertionSortAsc(a); for (int i = 0; i < b.size(); i++) { System.out.println(b.get(i)); } b = insertionSortDesc(a); for (int i = 0; i < b.size(); i++) { System.out.println(b.get(i)); } } }
相关推荐
详解Java常用排序算法-插入排序
基于python的排序算法-插入排序Insertion Sort
理解插入排序算法-讲解
经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
自己看书时写的排序算法:插入排序 CPP文件
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
C语言版的排序方法---插入排序,非常有用的代码,可以实际中使用。
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
算法-数据结构和算法-11-插入排序.rar
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现插入排序,包括详细的...
C语言实现常见排序算法。编译环境:VS2010。 包括: 冒泡排序 快速排序 直接插入排序 Shell排序 直接选择排序 堆排序 归并排序(递归和非递归两种) 桶式排序 基数排序:顺序和静态队列两种方法 索引排序(采用简单...
排序算法 —— 直接插入排序(图文超详细)
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
NULL 博文链接:https://hoxis.iteye.com/blog/2034252
十大经典排序算法 ... (2)排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部...常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。