重走算法路之简单排序(插入)
程序员文章站
2022-07-14 08:47:09
...
今天继续排序之路,今天要贴出的是插入排序,也属于简单的排序,对于数量小的排序,它还是一个很有效的算法,
以下属于本人 粗暴讲解
原理:
它的工作方式很像人们打牌插牌一样,从起得第一张牌开始,然后接下来的到的牌如果比手里的牌大就放后面,如果比前面的牌小就放在前面,一样大的就和当前的牌搁一起就可以了,起完所有的牌,按照这样的方法就能把手里的牌排好序了。所以会从待排序的第二个元素开始,然后和前面的数进行比较。依次下去,直到最后一个元素。
时间复杂度:
和前面的冒泡排序有的一拼http://mntms.iteye.com/admin/blogs/2044246也是O(n2);所以当要处理的数据量很大的时候效率还是有那么低,当然,当处理少量数据的时候,它和冒泡排序一样是值得选择的,因为比较简单嘛,而且也容易理解。
图文理解:
代码:
package 插入排序; /** * 插入排序 * @author TMs * */ public class InsertionSort { private long[] array; private int count; public static void main(String[] args) { InsertionSort is = new InsertionSort(10); is.insert(34); is.insert(4); is.insert(3); is.insert(234); is.insert(334); is.insert(24); is.insert(0); is.insert(3224); is.insert(134); is.insert(0); is.getSize(); System.out.println("排序前:"); is.display(); is.insertionSort(); System.out.println("排序后:"); is.display(); } /** * 构造一个大小为max的数组大小 * @param max 数组的元素个数的最大值 */ public InsertionSort(int max) { array = new long[max]; count = 0; } /** * 向数组中插入一个值 * @param value 插入的值 */ public void insert(long value) { array[count] = value; count++; } /** * 打印 当前数组中的个数 */ public void getSize() { System.out.println("数组中当前元素的总数为:"+count); } /** * 打印数组中的元素 */ public void display() { for(int i = 0; i < count; i++) { System.out.println("array["+i+"]="+array[i]+" "); } System.out.println(); } /** * 对数组进行插入排序 */ public void insertionSort() { for(int i=count-1; i > 0; i--) { for(int j = count-i; j>0; j--) { if(array[j]<array[j-1]) { exchange(j,j-1); } } } } /** * 交换元素 * @param x 下标x * @param y 下标y */ public void exchange(int x,int y) { long temp; temp = array[x]; array[x] = array[y]; array[y] = temp; } }
输入输出结果:
数组中当前元素的总数为:10 排序前: array[0]=34 array[1]=4 array[2]=3 array[3]=234 array[4]=334 array[5]=24 array[6]=0 array[7]=3224 array[8]=134 array[9]=0 排序后: array[0]=0 array[1]=0 array[2]=3 array[3]=4 array[4]=24 array[5]=34 array[6]=134 array[7]=234 array[8]=334 array[9]=3224
PS:第二个简单的排序,希望自己能坚持每天能搞懂一个东西,然后贴出来(这可能是 最好的了)学 校的课也多,大二狗也只能每天在这个时候安安静静的写写blog,对一天的总结,也对自己的一个交 代,睡觉,晚上吃多了会长胖!
上一篇: Class.forName···关于Class. 的应用介绍
下一篇: Java 扑克发牌算法实现