文档章节

插入排序

datacube
 datacube
发布于 2016/08/09 11:43
字数 517
阅读 3
收藏 0

将arr[i]复制为一个名为target的临时元素。 向下扫描列表,比较这个目标值target与arr[i-1]、arr[i-2]的大小,依次类推。 这个比较过程在小于或等于目标值的第一个元素(arr[j])处停止,或者在列表开始处停止(j=0)。 在arr[i]小于前面任何已排序元素时,后一个条件(j=0)为真, 因此,这个元素会占用新排序子列表的第一个位置。 在扫描期间,大于目标值target的每个元素都会向右滑动一个位置(arr[j]=arr[j-1])。 一旦确定了正确位置j,目标值target(即原始的arr[i])就会被复制到这个位置。 与选择排序不同的是,插入排序将数据向右滑动,并且不会执行交换。
通常,插入排序呈现出二次排序算法中的最佳性能。对于具有较少元素(如n<=15)的列表来说,二次算法十分有效。

package com.lifeibigdata.fight;

/**
 * Created by lifei on 16/10/24.
 */
public class InsertSort {

    static int[] insertSort(int[] a){
        int j;
        for (int i = 1; i < a.length; i++) {
            int target = a[i];
            j = i;
            while (j > 0 && target < a[j - 1]){
                a[j] = a[j - 1];
                j--;
            }
            a[j] = target;
            for (int x:a) {
                System.out.printf(x +" ");
            }
            System.out.println();
        }
        return a;
    }

    
    public static void main(String[] args) {//TODO 插入排序,只能在大于前一个值并且小于后一个值的地方交换,只大或者只小不能解决问题
        int[] a = new int[]{2,3,5,1,4};
        int[] r = insertSort(a);
        for (int x:r) {
            System.out.println(x);
        }
    }
}

//=======================================================

/** * 
 *特点是简单,不需要额外的存储空间,在元素少的时候工作得好
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = { 3, -1, 0, -8, 2, 1 };
        printArray(array);
        insertSort(array);
        printArray(array);
    }
    public static void insertSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }

        for (int i = 1; i < array.length; i++) {
            int currentValue = array[i];
            int position = i;
            for (int j = i - 1; j >= 0; j--) {  //j表示已经插入元素的索引值
                if (array[j] > currentValue) {
                    array[j + 1] = array[j];
                    position -= 1;
                } else {
                    break;
                }
            }
            array[position] = currentValue;
        }
    }
    public static void printArray(int[] array) {
        System.out.print("{");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("}");
    }

}

本文转载自:http://blog.csdn.net/kimylrong/article/details/17121519

datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问

暂无文章

golang-字符串-地址分析

demo package mainimport "fmt"func main() {str := "map.baidu.com"fmt.Println(&str, str)str = str[0:5]fmt.Println(&str, str)str = "abc"fmt.Println(&s......

李琼涛
今天
4
0
Spring Boot WebFlux 增删改查完整实战 demo

03:WebFlux Web CRUD 实践 前言 上一篇基于功能性端点去创建一个简单服务,实现了 Hello 。这一篇用 Spring Boot WebFlux 的注解控制层技术创建一个 CRUD WebFlux 应用,让开发更方便。这里...

泥瓦匠BYSocket
今天
6
0
从0开始学FreeRTOS-(列表与列表项)-3

FreeRTOS列表&列表项的源码解读 第一次看列表与列表项的时候,感觉很像是链表,虽然我自己的链表也不太会,但是就是感觉很像。 在FreeRTOS中,列表与列表项使用得非常多,是FreeRTOS的一个数...

杰杰1号
今天
8
0
Java反射

Java 反射 反射是框架设计的灵魂(使用的前提条件:必须先得到代表的字节码的 Class,Class 类 用于表示.class 文件(字节码)) 一、反射的概述 定义:JAVA 反射机制是在运行状态中,对于任...

zzz1122334
今天
5
0
聊聊nacos的LocalConfigInfoProcessor

序 本文主要研究一下nacos的LocalConfigInfoProcessor LocalConfigInfoProcessor nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/impl/LocalConfigInfoProcessor.java p......

go4it
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部