八大排序算法(一)—— 直接插入排序

概述


本系列博客一共8篇,讲解常用的8种排序算法:直接插入排序、希尔排序(最小增量排序)、简单选择排序、堆排序、冒泡排序、快速排序、归并排序、分配排序(基数排序)。8种排序方式的基本关系如下图所示:排序算法基本关系

8种排序方式的时间复杂度、空间复杂度、稳定性等如下图所示:排序算法基本信息

本篇博客主要讲解直接插入排序算法的基本思想和Java代码实现。

基本思想


将一个记录插入到已经排好序的序列中。先将序列的第一个记录看作是有序的子序列,再把第二个记录与第一个记录进行比较,然后再进行插入操作,以此类推,不断循环,直到最后一个记录插入,整个序列的排序工作就完成了。
如下图所示,先将49作为第一个有序子序列,与后一个记录38进行比较,然后插入,形成新的子序列(38 49),再把后一个记录,插入新的子序列中,又形成新的子序列,直到最后一个记录49插入到序列中,排序完成:直接插入排序基本思想

##Java 代码实现:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
* FileName:StraightInsertSort.java
* 创建一个直接插入排序类,实现一个直接插入排序方法和一个打印输出方法
* 直接插入排序:先将序列的第1个记录看成是一个有序的子序列,
* 再从第2个记录逐个进行插入,
* 直至整个序列有序为止
*
* @author kylezhang
* @date 2017/03/08
*
*
*/

public class StraightInsertSort {
public static void main(String[] args) {
//长度为10的数组
int[] c = new int[10];

Random rd = new Random(47);
//随机生成数组
for(int i = 0; i < c.length; i++) {
c[i] = rd.nextInt(10);
}

StraightInsertSort sis = new StraightInsertSort();
System.out.print("原序列:");
sis.print(c);
sis.straightInsertSort(c);
System.out.println();
System.out.print("排序后:");
sis.print(c);
}
/**
* 遍历数组,并打印输出
*
* @param a 需要打印输出的数组
*
*/

public void print(int a[]) {
for(int b : a) {
System.out.print(b + " ");
}
}
/**
* 实现直接插入排序操作
*
* @param a 需要进行直接插入排序操作的数组
*
*/

public void straightInsertSort(int a[]) {
//从第二个记录开始遍历数组,即 i = 1 处。
for(int i = 1; i < a.length; i++) {
//如果小于前一个记录,则插入到前一个记录前面,
//否则不用处理,直接插入前一个有序子数组的后面
if(a[i] < a[i-1]) {
int j;
int x; //用于插入
x = a[i];

//从后向前遍历前一个有序子数组
//,直到上一个有序子数组已经遍历完且
//找到合适的插入位置,跳出循环
for(j = i - 1; j >= 0 && x < a[j]; j--) {
a[j+1] = a[j]; //每次遍历都将数组后移一位
}
//当跳出循环时有两种可能,第一,当 a[j] >= x 时,
//则将 x 插入 a[j] 的后一个位置;第二,当 j < 0 时
//,此时上一个有序子数组已经遍历完,所有记录都大于
//需要插入的数,则直接将 x 插入到上一个数组的第一个
//位置。
a[j+1] = x;
}
}
}
}

运行结果


原序列:8 5 3 1 1 9 8 0 2 7
排序后:0 1 1 2 3 5 7 8 8 9

结果仅供参考,因为采用的随机数组,所以每个人运行的结果应该是不一样的。

总结


代码中的注释已经把代码解释的非常详细了,如果还有不理解的地方欢迎在文章下方评论或戳博客中的联系方式联系我。
注:以上解析均为个人理解,如有不妥或错误望指正。

评论