JAVA算法起步之插入排序实例
程序员文章站
2024-03-31 11:55:46
趁着过年这段时间,我将算法导论这本书看了一遍,感觉受益匪浅。着这里也根据算法导论中所涉及到的算法用java实现了一遍。第一篇我们就从排序开始,插入排序的原理很简单,就像我们...
趁着过年这段时间,我将算法导论这本书看了一遍,感觉受益匪浅。着这里也根据算法导论中所涉及到的算法用java实现了一遍。
第一篇我们就从排序开始,插入排序的原理很简单,就像我们玩扑克牌时一样。如果手里拿的牌比他前一张小,就继续向前比较,知道这张牌比他前面的牌打时候就可以插在他的后面。当然在计算机中我们相应的也需要将对比过的牌向后移一位才可以。
这里直接给出算法,相信很多程序员都感觉有些程序比我们的自然语言都要好理解。
复制代码 代码如下:
public class sort {
public void sort(int[] s){
if(s.length<1){
return ;
}
for (int i = 1; i < s.length; i++) {
int key =s[i];
int j=i-1;
while(j>=0&&s[j]>key){
s[j+1]=s[j];
j--;
}
s[j+1]=key;
}
}
public static void main(string[] args) {
sort s=new sort();
int[] st =new int[]{7,5,3,4,2,1};
s.sort(st);
for (int i = 0; i < st.length; i++) {
system.out.println(st[i]);
}
}
}
他的时间复杂度是o(n*n),是原址的(任何时候都需要常数个二外的元素空间存储数据而归并排序就是非原址的)
推荐阅读
-
JAVA算法起步之插入排序实例
-
Java排序算法之冒泡排序 博客分类: 算法common数据结构java java算法排序冒泡排序
-
Java排序算法之快速排序 博客分类: 数据结构commonjava算法more and more java算法快速排序
-
Java排序算法之简单选择排序 博客分类: 算法数据结构javacommon 算法java简单选择排序直接选择排序
-
求最大公约数之四部曲 博客分类: java 服务 java算法求最大公约数
-
聚类算法之MST算法 java实现版本 博客分类: java综合web算法 算法averagelinkmst最短距离
-
海量数据相似度计算之simhash短文本查找 博客分类: 算法架构创业java simhash局部敏感哈希海明距离海量数据相似度
-
Java简单算法之折半查找
-
高并发之Java实现一致性Hash负载算法
-
java数字签名算法之RSA