数据结构-插入排序

插入排序算法理解与实现

插入排序

插入排序的基本思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的数据序列的适当位置,直到全部记录插入完成为止。

直接插入排序

基本思想

假设待排序的记录存放在数组data[0...n-1]中。初始时,data[0]自成1个有序区,无序区为data[1...n-1]。从i=1起直至i=n-1为止,依次将data[i]插入当前的有序区data[0...i-1]中,生成含n个记录的有序区。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] insertSort(int[] data){
//i=0时自成有序区
for(int i=1;i<data.length;i++){
if(data[i]<data[i-1]){
int tmp = data[i];
//找到合适的插入位置,并后移其他元素
int index = -1;
// 0 1 2 3 5 6 7 //4
for(int j=i-1;j>=0&&tmp<data[j];j--){
index = j;
data[j+1] = data[j];
}
data[index] = tmp;
}
}
return data;
}

时间复杂度:O(n2)

希尔排序

基本思想

对待排记录序列先做“宏观”调整,再做“微观”调整。所谓宏观调整,指的是“跳跃式”的插入排序。将记录序列data[0...n-1]分成若干子序列,每个子序列分别进行插入排序。关键是,这种子序列不是由相邻的记录构成的,而是从开头每隔d个元素取一个直到结束作为一组,共分为d组;等这d组分别完成排序之后,执行d--操作,继续分组和排序,直到d=1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] shellSort(int[] data){
int init = data.length/3;
for(int i = init;i>=1;i--){
int d = i; //d组
for(int j=d;j<data.length;j++){
if(data[j]<data[j-d]){
int temp = data[j];
int index = -1;
for(int k = j-d;k>=0&&temp<data[k-d];k-=d){
data[k+d] = data[k];
index = k;
}
data[index] = temp;
}
}
}
return data;
}
您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------