有意思的排序算法-插入排序

标签: 排序算法 插入排序 | 发表时间:2012-04-28 21:20 | 作者:迷茫的孩子
出处:http://www.cnblogs.com/

所谓排序,无非就是把一个无序的序列排成一个有序的序列,从本文开始,将着重介绍经典的一些排序算法。

插入排序,是指将待排序列中的数,一个一个插入到适当位置的过程。说起算法的概念来,总是让人摸不着头脑,还是从生活中的例子来理解吧。相信每个人都玩过牌,我们在开始摸牌的时候,左手是空的,牌面朝下放到桌子上,接着,一次从桌子上摸起一张牌,并将它插入到左手一把牌中的正确位置上,为了找到这张牌的正确位置,要将它与手中已有的每一张牌从右到左地进行比较,无论什么时候,左手中的牌都是排好序的,而这些牌原先都是桌子上那副牌里最顶上的一些牌。

于是,根据以上的算法分析,可以写出以下的Java代码。

 1 /**
 2      * 插入排序算法
 3      * 
 4      * @param A
 5      *            int数组
 6      * @param isInc
 7      *            是否升序,true为升序,false为降序
 8      */
 9     private void InsertSort(int[] A, boolean isInc) {
10         int len = A.length;
11         int key = 0;
12         int i = 0;
13         for (int j = 1; j < len; j++) {
14             key = A[j];
15             i = j - 1;
16             while (i >= 0 && (isInc ? A[i] > key : A[i] < key)) {
17                 A[i + 1] = A[i];
18                 i = i - 1;
19             }
20             A[i + 1] = key;
21         }
22     }

从算法的机理可以看出,该算法是原地排序的,而且其算法复杂度为O(n 2)。

本文链接

相关 [排序算法 插入排序] 推荐:

有意思的排序算法-插入排序

- - 博客园_首页
所谓排序,无非就是把一个无序的序列排成一个有序的序列,从本文开始,将着重介绍经典的一些排序算法. 插入排序,是指将待排序列中的数,一个一个插入到适当位置的过程. 说起算法的概念来,总是让人摸不着头脑,还是从生活中的例子来理解吧. 相信每个人都玩过牌,我们在开始摸牌的时候,左手是空的,牌面朝下放到桌子上,接着,一次从桌子上摸起一张牌,并将它插入到左手一把牌中的正确位置上,为了找到这张牌的正确位置,要将它与手中已有的每一张牌从右到左地进行比较,无论什么时候,左手中的牌都是排好序的,而这些牌原先都是桌子上那副牌里最顶上的一些牌.

排序算法

- - 互联网 - ITeye博客
排序算法有很多,所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法,可以按照建议的顺序考虑以下标准: .     对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要.  一、冒泡(Bubble)排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

排序算法 Sleep Sort

- Jeff - 酷壳 - CoolShell.cn
排序算法好像是程序员学习编程最多的算法,也可能是算法研究者们最喜欢研究的算法了. 排序有很多很多的算法,比如,冒泡,插入,选择,堆,快速,归并等等(你可以看看本站以前的那些文章:可视化的排序,排序算法比较,显示排序过程的python)这里向大家介绍一个“巨NB”的排序算法——Sleep Sort. 闲言少说,请看下面的代码(用Shell脚本写的).

“天才”排序算法:Sleepsort

- Sirius - 黑客志
4chan上某位神人发明的天才排序算法:Sleepsort,充分发挥多核威力,评论中还有更多优化版本:. TermKit: 下一代的Mac命令行/终端程序.

SegmentFault问答排序算法

- - 标点符
SegmentFault 参考了 Stack Overflow的热门算法设置了自己的排序算法,具体排序算法如下:. 对于热门文章,使用了如下公式:. views:浏览量,对浏览量做了一次去对数处理,主要是为了防止某些浏览量较大的文章异军突起,待在榜单迟迟不动. recommendScore/collectScore:文章的推荐数和收藏数,直接加和到分子中,作为文章热门程度的考虑因素.

常用排序算法小结

- - ITeye博客
离开课堂后,排序算法写的比较少了,当有排序的要求时,一般用的比较多的是直接采用Arrays.sort以及Collections.sort结合比较器来实现. Arrays工具类包含了对各种类型数组的排序,以下是Arrays中包括的sort方法:. 以下是 Collections中的sort方法,该sort方法中结合了Arrays.sort来实现的.

Java排序算法:归并排序

- - zzm
 Java排序算法(九):归并排序. 归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的. 然后再把有序子序列合并为整体有序序列. 归 并排序是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.

面试算法之排序算法集锦

- - CSDN博客推荐文章
排序算法在面试过程中是经常会考的,这是很基础的,面试官觉得你应该很熟悉这些东西,如果你半个小时内写不出来,那基本就给跪了,因为这真的是狠基础狠基础的东西,所以我们得对一些基本的排序算法烂熟于胸,对这些排序思想,效率了如指掌,才能让面试官觉得你还行. 基本的排序算法有:直接插入排序,冒泡排序,简单选择排序,shell排序,归并排序,快速排序,堆排序.

利用归并排序算法对大文件进行排序

- - ITeye博客
归并排序算法介绍,请参照Wikipeida. 大文件分割成行数相等的两个小文件,使用递归一直分割到所有所有小文件低于限制行数. 两个排序好的小文件归并到大文件. 直到最后所有排序好的文件归并到输入的大文件并返回. 之前看了网上很多示例代码,写的很不简洁, 引入了过多的临时变量i, j, k等等, 导致程序基本没法看,.

Java程序员必知的8大排序算法

- - JavaRanger - 专注JAVA高性能程序开发、JVM、Mysql优化、算法
(1)基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排. 好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数. 如此反复循环,直到全部排好顺序. //将大于temp的值整体后移一个单位. (1)基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序.