- it技术
- 插入排序
目录
要求代码复杂度时间复杂度空间复杂度
稳定性分析
要求
将数值数组按从小到大排序。
代码
public class Insertion {
public static void sort(Comparable
[] a
) {
for(int i
=1;i
< a
.length
;i
++) {
for(int j
=i
;j
>0;j
--) {
if (greater(a
[j
-1],a
[j
])) {
exch(a
, j
, j
-1);
}else {
break;
}
}
}
}
private static boolean greater(Comparable v
, Comparable w
) {
return v
.compareTo(w
) > 0;
}
private static void exch(Comparable
[] a
, int i
, int j
) {
Comparable t
= a
[i
];
a
[i
] = a
[j
];
a
[j
] = t
;
}
}
public class Test {
public static void main(String
[] args
) {
Integer
[] a
= {4,8,6,1,3,5,6};
Insertion
.sort(a
);
System
.out
.println(Arrays
.toString(a
));
}
}
[1, 3, 4, 5, 6, 6, 8]
复杂度
时间复杂度
O(n^2)
空间复杂度
O(1)
稳定性分析
稳定
