插入排序好比抓牌,一副牌是待排序的数组,拿一张牌,跟手里的牌从右到左一张张比较,插入到合适的位置。
优点:适应小数据量排序,空间消耗小。
缺点:当数据量比较大时,排序效率不高。
代码结构:
Sort:排序接口
AbstractSort:排序抽象类
InsertSort:排序算法。
Sort:
public interface Sort<T> {
/**
* 返回排序后的数组
* @return
*/
public T[] sort(T[] array);
public T[] sort();
}
AbstractSort:
import java.util.Arrays;
import java.util.Comparator;
public abstract class AbstractSort<T> implements Sort<T> {
/**
* 待排序数组
*/
protected T[] array;
/**
* 用于比较数组元素大小
*/
protected Comparator<? super T> comp;
public void init(T[] array,Comparator<? super T> comp){
this.array = array;
this.comp = comp;
}
public void print(){
System.out.println(Arrays.toString(array));
}
public void swap(int i ,int j){
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
InsertSort:
import java.util.Arrays;
import java.util.Comparator;
public class InsertSort<T> extends AbstractSort<T> {
public InsertSort(T[] array, Comparator<? super T> comp) {
init(array, comp);
}
@Override
public T[] sort() {
T[] a = array;
return sort(a);
}
@Override
public T[] sort(T[] array) {
for (int i = 1; i < array.length; i++) {
T current = array[i];
int j = i - 1;
/*
* 如果array[j]前一个元素大于current,将array[j]移到下一个位置
*/
for (; j > -1 && comp.compare(current, array[j]) < 0; j--) {
array[j + 1] = array[j];
}
//将current设置到j+1位置
array[j + 1] = current;
}
return array;
}
@Override
public String toString() {
return "InsertSort";
}
public static void main(String[] args) {
Integer[] temp = null;
temp = new Integer[] { 16, 14, 8, 7, 9, 3, 2, 4, 1 };
Comparator<Integer> comp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
};
Sort<Integer> sort = new InsertSort<Integer>(temp, comp);
Integer[] clone = temp.clone();
Arrays.sort(clone);
boolean equals = Arrays.equals(clone, sort.sort());
assert equals;
System.out.println(Arrays.toString(temp));
}
}
分享到:
相关推荐
MIT算法导论——算法顶尖经典教材MIT算法导论——算法顶尖经典教材MIT算法导论——算法顶尖经典教材MIT算法导论——算法顶尖经典教材MIT算法导论——算法顶尖经典教材
计算机系的教材,算法导论————————————————————————————————
算法导论——中文版
算法导论英文版的教师用书 算法导论教师手册.pdf
CLRS for Instructor 《算法导论——教师用书》(有部分习题答案) Computer Algorithms - Introduction to Design and Analysis 3rd - Sara Baase Solutions for CLRS (算法导论部分习题解答)
有助算法入门的同学,对于想在acm程序设计上有所提高的同学是必选手册 。
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867026
算法导论,关于算法最权威最全面最深入的书籍,分享给大伙儿~
所有代码都是在我学习这本书时亲手敲出来的,并且调试正确了,包括:第三部分到第六部分(即10-26章),外加第七部分31和32章所有的算法和数据结构以及编程习题还有思考题的C++实现源代码; 第一、二部分学习的较早...
插入排序: * 始终定义第一个元素为有序, 将无序元素 * 逐个插入到有序排列之中,不断的移动数据, * 空出一个适当的位置,把待插入的元素放到里 * 面去。
算法界巨著《算法导论》的习题解答,来自于该书著者Cormen博士,包含了对每一章的概括总结和其上课笔记
pdf文件,算法导论中文版,一本风靡全球的书。适合广大大学生使用。项目经验不是关键,缺少的是算法思想。
《算法导论》原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高纳德(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美《算法导论》自第一...
算法导论是编程领域提升编程境界的必备书籍,他能让你的编程思维突然间变得开阔起来,绝对的好书啊
就是传说中的MIT的算法导论啊,英文原版第二版,很不错的
供大家阅读。算法导论是一本很好的书。其课后思考题更是启发人的思想
这个是关于RandomizedAlgorithms的,英文版
《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。
CLRS 算法导论 课后解答 教师用书