By

Contents
  1. 1. 简单插入排序 (三种实现)
  2. 2. 希尔排序（俩种实现）

插入排序分为 简单插入排序 和 希尔排序

简单插入排序 (三种实现)

基本思想：
每次将一个待排序的记录，按其关键字大小插入到 前面已经排好序的子序列中 的适当位置，直到全部记录插入完成
为止。
设数组为 a[0…n-1]。

  1. 初始时，a[0]自成 1 个有序区，无序区为 a[1..n-1]。令 i=1

  2. 将 a[i]并入当前的有序区 a[0…i-1]中形成 a[0…i]的有序区间。

  3. i++并重复第二步直到 i==n-1。排序完成。

    按定义来比较麻烦,代码多

    public static void insertSort1(int[] data) {

    int i, j, k;
for (i = 1; i < data.length; i++) {
    // 为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
    for (j = i - 1; j >=0; j--) {
        if (data[j] < data[i])
            break;
    }
    // 如找到了一个合适的位置
    if (j != i - 1) {
        int temp = data[i];
        // 将比a[i]大的数据向后移
        for(k=i-1;k>j;k--)
        data[k+1] = data[k];                
        // 将a[i]放到正确位置上
        data[j+1] = temp;
    }
}
printSort(data);//封装好的一个函数用来打印数组

    }

将后移和搜索放在一起

public static void insertSort2(int[] data){
    int i,j;
    for(i=1;i<data.length;i++){
        int temp = data[i];
        if(data[i-1]>data[i]){
            for(j=i-1;j>=0 && data[j]>temp;j--){
                data[j+1]= data[j];
            }
            data[j+1] = temp;
        }
    }
    printSort(data);
}

用数据交换代替位置后移

public static void insertSort3(int[] data){
    int i,j;
    for(i=1;i<data.length;i++){
        for(j=i-1;j >=0 && data[j]>data[j+1];j--){
            swap(data, j, j+1);
        }
    }
    printSort(data);
}

希尔排序（俩种实现）

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因 DL．Shell于 1959 年提出而得名。

基本思想：

  • 先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，
  • 然后依次缩减增量再进行排序，
  • 待整个序列中的元素基本有序（增量足够小）时，
  • 再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是
  • 很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
static void  shellSort3(int[] data){
    int i,j,gap;
    for(gap = data.length;gap>0;gap /=2){  //步长  及其变化  直到变为0  最后变成直接插入排序
        for(i=0;i<gap;i++){   //按组排序
            for(j= i+gap;j<data.length;j+=gap){
                for(int k=j-gap;k>=0 && data[k]>data[k+gap];k-=gap)
                    swap(data, k, k+gap);
            }
        }
    }
}


static void shellSort4(int[] data){
    int i,j,gap;
    for (gap=data.length/2;gap>0;gap/=2){   
        for(i=gap;i<data.length;i++){    //变得是这里 从数组第gap个元素开始  
            for(j=i-gap;j>=0 && data[j]>data[j+gap];j-=gap){  //每个元素与自己组内的数据进行直接插入排序
                swap(data, j, j+gap);
            }
        }
    }
    printSort(data);
}
Contents
  1. 1. 简单插入排序 (三种实现)
  2. 2. 希尔排序（俩种实现）