文档章节

排序--插入排序

蔡佳娃
 蔡佳娃
发布于 2017/08/17 23:57
字数 984
阅读 17
收藏 0

算法原理

1. 数组x,长度为n(n>1),即x[0],x[1], ..., x[n-1]。

2. 选取标记位:pos(1<pos<n)=1,pos将数组x分为两部分,左边是有序数组。

3. 将标记值:x[pos]与有序数组的元素(x[pos-1]~x[0],从右向左)依次比较,如果有小于有序数组的某个元素,将其插入到该元素的前面,否则退出本轮循环。

4. pos=pos+1,重复3步骤,直到pos=n-1结束。

算法实现

package com.cjw.sort;

import java.util.Arrays;

/**
 * 使用插入排序对整型数组进行排序
 *
 * Created by cjw on 2017/8/17 0017.
 */
public class InsertSortUtil {

    /**
     * 插入排序算法实现
     *
     * @param x 待排序的数组
     */
    public static void sort(int[] x) {
        if (x == null || x.length < 2) {
            return;
        }
        int len = x.length;
        //pos为标记值的索引,pos左侧为有序部分
        for (int pos = 1; pos < len; pos++) {
            int finalPos = pos; //最终标记值的索引 
            int curValue = x[pos]; //标记值
            //向左侧查找,从后往前逐一比对
            for (int i = pos-1; i >= 0; i--) {
                //如果标记值小于x[i], x[i]则进行右移
                if (x[i] > curValue) {
                    x[i+1] = x[i];
                    finalPos--; //标记值左移
                } else {
                    //左侧为有序部分,一旦标记值大于x[i],i左边其余元素都会小于标记值
                    break;
                }
            }
            x[finalPos] = curValue; //将标记值插入
            debugPrint(pos, x);
        }
    }

    /**
     * 调试输出排序过程中数组中的数据
     *
     * @param time  排序次数
     * @param x     数组
     */
    private static void debugPrint(int time, int[] x) {
        System.out.println("第" + time + "次排序结果:" + Arrays.toString(x));
    }

    public static void main(String[] args) {
        int[] x = { 87, 12, 34, 39, 134, 4, 45, 8, 99 };
        sort(x);
    }
}

    测试结果:

第1次排序结果:[12, 87, 34, 39, 134, 4, 45, 8, 99]
第2次排序结果:[12, 34, 87, 39, 134, 4, 45, 8, 99]
第3次排序结果:[12, 34, 39, 87, 134, 4, 45, 8, 99]
第4次排序结果:[12, 34, 39, 87, 134, 4, 45, 8, 99]
第5次排序结果:[4, 12, 34, 39, 87, 134, 45, 8, 99]
第6次排序结果:[4, 12, 34, 39, 45, 87, 134, 8, 99]
第7次排序结果:[4, 8, 12, 34, 39, 45, 87, 134, 99]
第8次排序结果:[4, 8, 12, 34, 39, 45, 87, 99, 134]

    既然每次选取标记值后,数组的左侧部分都是有序数组,那么在查找标记值的插入位时,就不必逐一比较,使用2分查找可以更快的定位到插入位。

    程序改进:

/**
 * 改进后的插入算法(对标记值左边的有序数组进行二分查找)
 *
 * @param x 待排序的数组
 */
public static void optimizedSort(int[] x) {
    if (x == null || x.length < 2) {
        return;
    }
    int len = x.length;
    int low, mid, high;
    for (int pos = 1; pos < len; pos++) {
        int curValue = x[pos];
        low = 0;
        high = pos - 1;
        //通过二分法获取标记值要插入的位置
        while (low <= high) {
            mid = (low + high) >>> 1;
            if (curValue < x[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        //low后面元素右移
        for (int i = pos; i > low; i--) {
            x[i] = x[i-1];
        }
        x[low] = curValue;
        //debugPrint(pos, x);
    }
}

/**
 * 生成长度为len,范围为0-len的随机整型数组
 * 
 * @param len   数组长度
 * @return 随机数组
 */
private static int[] genBigIntArray(int len) {
    int[] x = new int[len];
    Random random = new Random();
    for (int i = 0; i < len; i++) {
        x[i] = random.nextInt(len);
    }
    return x;
}

public static void main(String[] args) {
    int[] x = genBigIntArray(100000);
    int[] y = Arrays.copyOf(x, 100000);

    long begin = System.currentTimeMillis();
    sort(x);
    System.out.println("普通插入排序耗时:" + (System.currentTimeMillis() - begin) + "ms");

    begin = System.currentTimeMillis();
    optimizedSort(x);
    System.out.println("二分插入排序耗时:" + (System.currentTimeMillis() - begin) + "ms");
}

    多次运行的测试结果:

普通插入排序耗时:1100ms
二分插入排序耗时:4ms

普通插入排序耗时:1044ms
二分插入排序耗时:4ms

普通插入排序耗时:1075ms
二分插入排序耗时:4ms

普通插入排序耗时:1071ms
二分插入排序耗时:4ms

    对10万个随机整数进行排序,普通的插入排序耗时在1100ms左右,而优化后的二分插入排序稳定在4ms。

© 著作权归作者所有

上一篇: 排序--选择排序
下一篇: 排序--冒泡排序
蔡佳娃
粉丝 16
博文 54
码字总数 48865
作品 0
海淀
程序员
私信 提问
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 年迈渔夫遭黑帮袭抢

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享Elvis Presley的单曲《White Christmas》: 《White Christmas》- Elvis Presley 手机党少年们想听歌,请使劲...

小小编辑
今天
1K
20
CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
昨天
5
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
昨天
8
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
昨天
16
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部