插入排序

Posted by 石玉军 on 2018-07-26

相信大家都有打扑克的经历,那么我们今天的插入排序就以拿牌为例开始讲(注意只是举例,不是按打牌的规则哦)

1.我们拿到了一张牌3,我们把它放手里,现在手里有牌[3]

2.我们拿到了一张牌1,拿它与手里最后一张牌也就是3比较,发现1比3小,所以我们把它插入到3的前面,现在手里有牌[1,3]

3.我们拿到了一张牌0,拿它与手里最后一张牌也就是3比较,发现0比3小,所以我们把它插入到3的前面,接着与3的上一张比较发现0比1还小,那么就把0在插入到1的前面,现在手里有牌[0,1,3]

4.我们拿到了一张牌2,拿它与手里最后一张牌也就是3比较,发现2比3小,所以我们把它插入到3的前面,接着与3的上一张比较发现2比1大,那么就不需要动了,现在手里有牌[0,1,2,3]

5.我们拿到了一张牌8,拿它与手里最后一张牌也就是3比较,8比3大,那么就不需要动了,现在手里有牌[0,1,2,3,8]

6.。。。

现在你明白什么叫做插入排序了么?

如果你不明白的话也没关系,我还专门画了一张图:

图片

接下来上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int []num=new int[]{3,1,0,2,8,4,2};
for (int i=1,n=num.length;i<n;i++){
if(num[i]<num[i-1]){
for (int j=i;j>0;j--){
if(num[j]<num[j-1]){
int temp=num[j];
num[j]=num[j-1];
num[j-1]=temp;
}
}
}
}
for (int i:num){
System.out.print(i+",");
}

插入排序讲完了。在这里温馨提示大家,学习算法时,我们没必要拘泥于代码的实现,那没有意义。我的建议就是深入理解步骤,当你理解步骤以后代码是随你怎么玩都可以的。