插入排序

发布时间:2017-1-22 22:17:02 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"插入排序 ",主要涉及到插入排序 方面的内容,对于插入排序 感兴趣的同学可以参考一下。

插入排序分为直接插入排序和希尔排序

直接插入排序:

直接插入排序原理就是,假设前面n-1(n>=2)个元素已经排好序,现在要把第n个元素找到正确的位置并插入。

import java.util.Arrays;

public class Main {
    static  int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2,10,-3};
    public static void main(String[] args) throws InterruptedException {
        System.out.println(Arrays.toString(array));
        insertionSort(array);
        System.out.println(Arrays.toString(array));
    }

    //插入排序
    public static void insertionSort(int[] array){
        int len = array.length;
        int counter = 1;
        for(int i=1;i<len;i++){
            int temp = array[i];  //存储待排序的元素值
            int insertPoint = i-1;  //与待排序元素值作比较的元素的下标

            while(insertPoint>=0 && array[insertPoint]>temp){ //当前元素比待排序元素大
                array[insertPoint+1]= array[insertPoint];  //当前元素后移一位
                insertPoint--;
            }
            array[insertPoint+1]= temp;  //找到了插入位置,插入待排序元素
            System.out.print("第"+counter+"轮排序结果:");
            display(array);
            counter++;
        }
    }

    private static void display(int[] array){
        System.out.println(Arrays.toString(array));
    }
}
[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2, 10, -3]
第1轮排序结果:[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2, 10, -3]
第2轮排序结果:[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2, 10, -3]
第3轮排序结果:[6, 7, 8, 9, 1, 4, 3, 2, 5, 0, -1, -2, 10, -3]
第4轮排序结果:[1, 6, 7, 8, 9, 4, 3, 2, 5, 0, -1, -2, 10, -3]
第5轮排序结果:[1, 4, 6, 7, 8, 9, 3, 2, 5, 0, -1, -2, 10, -3]
第6轮排序结果:[1, 3, 4, 6, 7, 8, 9, 2, 5, 0, -1, -2, 10, -3]
第7轮排序结果:[1, 2, 3, 4, 6, 7, 8, 9, 5, 0, -1, -2, 10, -3]
第8轮排序结果:[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, -1, -2, 10, -3]
第9轮排序结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -2, 10, -3]
第10轮排序结果:[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -2, 10, -3]
第11轮排序结果:[-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -3]
第12轮排序结果:[-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -3]
第13轮排序结果:[-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
View Code

希尔排序:实质就是分组插入排序,该方法又称缩小增量排序

原理:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

比如一个长度为12的数组,

第一步就是分成增量为6的小数组,一共6个,每一个都含有2个元素,对每一个小数组都进行直接插入排序

第二步就是将数组分成增量为3的小数组,一共有4个,每个都含有3个元素,对每个小数组都进行直接插入排序

第三步就是将整个数组进行直接插入排序。

分别是12/2=6,6/2=3,3/2=1,增量为1时,其实就是对整个数组进行操作。

==========================================

如果是奇数怎么办呢?

比如一个长度为13的数组

第一步还是分成增量为6的小数组,一共6个,但是第一个小数组会有3个元素,其他的分别有两个,然后对每个小数组进行直接插入排序

第二步分成增量为3的小数组,一共有4个,但是第一个小数组有5个元素,其他的分别有4个元素,然后对每个小数组进行直接插入排序

第三步就是将整个数组进行直接插入排序。

============================================

import java.util.Arrays;

public class Main {
    static  int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2,-3};
    public static void main(String[] args) throws InterruptedException {
        System.out.println(Arrays.toString(array));
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }

    static void shellSort(int a[])
    {
        int n=a.length;
        int i, j, gap;

        for (gap = n / 2; gap > 0; gap /= 2) //步长
        {
            for (i = 0; i < gap; i++)        //直接插入排序
            {
                for (j = i + gap; j < n; j += gap) {
                    if (a[j] < a[j - gap]) {
                        int temp = a[j];
                        int k = j - gap;
                        while (k >= 0 && a[k] > temp) {
                            a[k + gap] = a[k];
                            k -= gap;
                        }
                        a[k + gap] = temp;
                    }
                }
                System.out.print("增量:"+gap+"     ");
                for(int k=i;k<n;k+=gap){
                    System.out.print(a[k]+"\t");
                }
                System.out.println("");
            }

上一篇:Maven:mirror和repository 区别
下一篇:Java中并发问题整理

相关文章

关键词: 插入排序

相关评论