文档章节

插入排序 Insertion sort

fokYaland
 fokYaland
发布于 2015/06/04 17:27
字数 259
阅读 2
收藏 0
是一种简单的排序方法。时间复杂度为   O(n^2),即N的平方。在数据量较小的情况下,是比较有效的排序方式。

输入:N个数 < a1,a2,a3.....an >
输出:输入序列的一个排序 <a'1,a'2,a'3.....a'n> 要求 a'1<=a'2<=.....a'n

思想:把序列分为2部分:已排序,未排序。 每次从未排序中取一个数,与已排序中的值比较,插入到合适的位置。

public   class   InsertSort {
       public   static   void   main(String[] args) {
               //   TODO   Auto-generated method stub
               int [] a;
            a =   new   int [30];
            Random rand =   new   Random();
               for (   int   i=0;i<a.   length ;i++){
                  a[i] = rand.nextInt(100);
            }
             println(a);
               long   s = System. nanoTime();
               int [] b= sort(a);
               long   dur = System. nanoTime() - s;         
             println(b);
            System.   out .println(dur);            
      }
      
       public   static   int [] sort( int [] a){
               for (   int   i=1;i<a.   length ;i++){
                     int   key = a[i];
                     int   j=i-1;
                     while   (j>=0 && a[j]>key){
                        a[j+1] = a[j];
                        j=j-1;
                  }
                  a[j+1] = key;
            }
               return   a;         
      }

       public   static   void   println( int [] a){
            System.   out .print(   "[" );
               for   (   int   i = 0; i < a.   length ; i++) {
                  System.   out .print(a[i]);
                     if (i != a.   length -1)
                        System.   out .print(   "," );
            }
            System.   out .println(   "]" );
      }
}


本文转载自:http://blog.csdn.net/yanliang1/article/details/17127417

fokYaland
粉丝 4
博文 68
码字总数 3062
作品 0
东城
私信 提问
PAT_A1098#Insertion or Heap Sort

Source: PAT_A1098 Insertion or Heap Sort (25 分) Description: According to Wikipedia: Insertion sort iterates, consuming one input element each repetition, and growing a sorted......

林東雨
05/09
0
0
MIT Introduction to Algorithms 学习笔记(四)

lecture 3 Insertion Sort, Merge Sort 1.(插入排序)Insertion sort def InsertSort(L): if(len(L) == 0 or len(L) == 1): return L tmp = 0 for i in range(1,len(L)): for j in range(i,0,......

hyaicc
2015/12/21
31
0
PAT A1089. Insert or Merge (25)

https://www.patest.cn/contests/pat-a-practise/1089 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue According to Wikipedia: Insertion sort......

阿豪boy
2017/03/01
0
0
stl-stable_sort源码学习笔记

前几天,一个新同事前来询问算法stl-stablesort的情况。由于离上次研读stl源码时间久已(两三年前的事儿了),有些细节笔记模糊了。所以就找了sgi-stl和ms-stl俩版本,重新复习一遍其中的stl...

huangjunkun
2011/11/07
0
0
hackerrank: Insertion Sort Advanced Analysis

Insertion Sort Advanced Analysis Insertion Sort is a simple sorting technique which was covered in previous challenges. Sometimes, arrays may be too large for us to wait around ......

Alexander_zhou
2014/02/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

10分钟详解Spring全家桶7大知识点

点关注,不迷路;持续更新Java架构相关技术及资讯热文!!! Spring框架自诞生以来一直备受开发者青睐,有人亲切的称之为:Spring 全家桶。它包括SpringMVC、SpringBoot、Spring Cloud、Spr...

我最喜欢三大框架
26分钟前
5
0
注册服务&开机自启动

列出所有服务[root@localhost ~]# systemctl list-unit-files[root@localhost ~]# systemctl status mysqld[root@localhost ~]# systemctl stop mysqld[root@localhost ~]# ......

jxlgzwh
30分钟前
1
0
解决jdk8 stream tomap方法报错:java.lang.IllegalStateException: Duplicate key异常解决(key重复)

List<User> userList = User.ME.loadList(users); if (CollectionUtils.isNotEmpty(userList)) { Map<Long, User> userMap = userList.stream().filter(Objects::nonN......

冰峰雪座
39分钟前
1
0
jdk中的一些命令

jdk中的一些命令 jps jstack jmap jstat jhat jinfo javap http://www.importnew.com/18398.html

晨猫
39分钟前
1
0
Bystack的高TPS共识算法

共识算法是分布式系统保证节点数据状态一致性的方法,在区块链的共识算法分POW(工作量证明)和POS(权益证明)两大类。第一类POW模式是在公链项目中运用的最广泛应用的共识算法,比特币长达10年...

比原链Bytom
40分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部