这次直入主题,我今天要复习的是插入排序!插入排序分为“直接插入”和“Shell排序”,Shell排序就是希尔排序,可以看做是直接插入排序从成熟体进化为完全体~
好的直接来看插入排序:
直接插入排序
我们先说一下插入排序的原理:
通过对未排序的数据执行逐个插入到合适的位置完成排序工作。
- 1.首先对数组前两个数据进行从小到大排序
- 2.将第三个数据与排好序的两个数据比较,插入合适的位置。
- 3.第四个同样方式插入到他们三个中。
- 4.不断重复,直到结束。
- 时间复杂度: 平均:O(n^2) 最佳:O(n) 最坏:O(n^2)
- 空间复杂度: O(1)
- 稳定性: 稳定
这个听起来比冒泡难一些,但是其实想象力丰富一些,就会觉得这个这个很简单~给个图片就懂了!
我又去百科盗图了:
图片的简单明了吧?就是从第二个值开始依次去取。然后每次都比较,然后把每次取的数字,放到该放的位置上。
直接看代码吧:手敲代码:
/**
* Created by AceCream on 2017/3/20.
*
* 插入排序(Insertion Sort)
* 原理:通过对未排序的数据执行逐个插入到合适的位置完成排序工作。
* 1.首先对数组前两个数据进行从小到大排序
* 2.将第三个数据与排好序的两个数据比较,插入合适的位置。
* 3.第四个同样方式插入到他们三个中。
* 4.不断重复,直到结束。
*
* 时间复杂度: 平均:O(n^2) 最佳:O(n) 最坏:O(n^2)
* 空间复杂度: O(1)
* 稳定性: 稳定
*
*/
public class InsertSort {
public static void main(String[] args) {
int value[] = {12,15,9,20,6,31,24};
InsertSort insertSort = new InsertSort();
insertSort.insertSort(value);
System.out.print("最终结果 ");
for (int result : value) {
System.out.print(result+" ");
}
}
private void insertSort(int[] value) {
//temp值待命
int temp;
for (int i=1;i<value.length;i++){
//从第二个数据开始取 每轮的检测数据都先放temp里
temp = value[i];
int j = i-1;
while (j>=0 && temp<value[j]){
//如果比较的值,比temp大,就让这个值往后去。temp继续比较。。。碰到比它小的,就在其后面落下(后面这句是循环外放下的)
value[j+1]=value[j];
j--;
}
//没有比它小的就放回去,有的话就放到应该在的位置
value[j+1]=temp;
}
}
}
我都注释的比较详细了~虽然我自己也总忘这个排序。
好的吃完甜点,我们开始今天的主菜——Shell排序
希尔排序
希尔排序是理论上效率最高的排序。但是!但是仅仅是理论上,因为在实践中的使用,希尔排序还是被快排击败了,两种排序都不太稳定,但是整体的试验中,快排还是略胜一筹~
希尔排序,也叫做缩小增量排序,其执行方式,我个人觉得还是很变态的。
还是看步骤吧:
- 1.将n个元素的数组分为n/2个数字序列:第一个数据和第n/2+1个数据为一对...
- 2.一次循环使每个序列对排好
- 3.变为n/4个序列,再次排序。
- 4.不断重复,周而复始,随着序列变为1,排序完成
看这个图,应该是可以理解的,它是分来,然后一一对应,然后比较,单独排序,直到最后,排列整齐。。。
当初觉得这个思想好强!但是!我觉得简单了解其原理就足够了。当然,想手敲也是可以的,但觉得必要性不是那么强,因为应用情况下,我宁可选择快排。
/**
* Created by AceCream on 2017/3/22.
* 希尔排序(ShellSort)
* 希尔排序效率很高!所以也是很常用的一种排序。
* 基于插入排序的思想:缩小增量排序
* 步骤:
* 1.将n个元素的数组分为n/2个数字序列:第一个数据和第n/2+1个数据为一对...
* 2.一次循环使每个序列对排好
* 3.变为n/4个序列,再次排序。
* 4.不断重复,周而复始,随着序列变为1,排序完成
*
* 时间复杂度: 平均:O(n^1.3) 最佳:O(n) 最坏:O(n^2)
* 空间复杂度: O(1)
* 稳定性: 不稳定
*
*/
public class ShellSort {
public static void shellSort(int a[]){
int gap;
int lenth = a.length;
for (gap=lenth/2;gap>0;gap/=2){ //从数组的第gap个元素开始 分出来循环几次
for (int i=0;i<gap;i++){ //分出来有多少组
//直接插入排序
for (int j=i+gap;j<lenth;j+=gap){
if (a[j]<a[j-gap]){
int temp = a[j];
int k = j-gap;
while (k>=0&&temp<a[k]){
a[k+gap]=a[k];
k -= gap;
}
a[k+gap]=temp;
}
}
}
}
}
public static void main(String[] args) {
int value[] = {49,27,46,55,4,13,38,65,97,26};
shellSort(value);
System.out.print("最终结果 ");
for (int result : value) {
System.out.print(result+" ");
}
}
}
这一次我没有选择在线手敲,私下每次我需要使用的时候我会回来看看毕竟学习不是背诵,最主要的是:了解其思想!
网友评论