插入排序是一中经常使用的算法,特别适合于部分有序和小规模数组的排序。
相同情况下它比选择排序的速度要快一倍;在小规模数据集的排序中,也比快速排序要快。
插入排序是一种稳定的排序算法,其排序时间受待排序的数组中的元素顺序的影响较大。
其思想是:
将整个待排序的数组分为有序和无序的两部分,每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。
Java代码如下:
package org.test;
/**
* 经典的插入排序算法,特别适合于部分有序和小规模数组的排序
* 相同情况下它比选择排序的速度要快一倍;在小规模数据集的排序中,
* 也比快速排序要快
* @author JackyChen
*
*/
public class InsertSort{
public static void sort(Comparable[] a){
//按升序排序
int len = a.length;
for(int i =1;i < len;i++){
//将a[i]插入到a[i-1]、a[i-2]...之中
for(int j = 1;j >0 && less(a[j],a[j-1]);j--){
exch(a,j,j-1);
}
}
}
/*
* 将a[i]和a[j]交换顺序
*/
public static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/**
* 判断v1是否小于v2
* @param v1
* @param v2
* @return true:小于;false:不小于
*/
public static boolean less(Comparable v1,Comparable v2){
return v1.compareTo(v1) < 0;
}
}
分享到:
相关推荐
说一说插入排序 插入排序的基本操作就是将一个数据插入到已经排序好序的数据中,从而得到一个新的,个数加一的有序数据,算法适用与少量的数据的排序。时间复杂度O(n^2),是稳定的排序算法。 基本思想:每步将一个待...
排序算法-----插入算法
数据结构与算法中的直接插入排序实现,平均时间复杂度为n2亲测可用
主要为大家详细介绍了java简单插入排序实例,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。 算法描述: ⒈ 从第一个元素开始,该元素可以认为已经被排序 ⒉ 取出下一个元素,在已经排序的元素序列中...
主要为大家详细介绍了JavaScript实现经典排序算法之插入排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
此案例难度系数4,属于Scratch高级编程,插入排序相对而言比选择排序和冒泡排序理解起来要难一点,但是还是相对简单的排序,尤其是对少量元素排序的时候,效率较高;综合考查说话、随机数、无限循环(条件循环)、...
简单插入排序思想,将一个无序的数组,想象成由两部分组成,一部分为有序列,一部分为无序列,初始时,有序列为数组第一个元素,无序列为第一个元素之后的元素组成。每次从无序列中取第一个数插入到有序列中,有序列...