最爱Java

书山有路勤为径，学海无涯苦作舟

插入排序思路与泛型版本的实现

一.插入排序算法的思路
        假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或者等于它前面的位置为止。
二.插入排序算法实例
        用五个名字(Monroe,Chin,Flores,Stein和Dare)的列表的插入排序算法为例：
                                       Monroe    从Monroe开始

        处理名字Chin        Chine  Monroe    将Chin插入到位置0；Monroe移动至位置1

        处理名字Flores     Chine  Flores  Monroe    将Flores插入到位置1；Monroe移动至位置2

        处理名字Stein       Chine  Flores  Monroe  Stein    Stein位置正确 

        处理名字Dare       Chine  Dare  Flores  Monroe  Stein    将Dare插入在位置1；列表尾部向右移动 

三.插入排序算法的实现
public class InsertSort {
    //sort an array of elements using insertion sort
    public static <T extends Comparable<? super T>> void sort(T[] arr) {
        int i, j, n = arr.length;
        T target;

        /**
         * place element at index i into the sublist
         * from index 0 to i-1 where 1<= i,
         * so it is in the correct positon
         */
        for (i = 1; i < n; i++) {
            //index j scans down list from index i looking for
            //correct position to locate target; assigns it to
            //arr at index j
            j = i;
            target = arr[i];
            //locate insertion point by scanning downward as long
            //as target < arr[j] and we have not encountered the
            //beginning of the array
            while (j > 0 && target.compareTo(arr[j - 1]) < 0) {
                //shift elements up list to make room for insertion
                arr[j] = arr[j - 1];
                j--;
            }
            //the location is found;insert target
            arr[j] = target;
        }
    }
}

四.插入排序算法的效率
        假定n是数组的长度，那么插入排序需要n-1遍。对于通用的遍i来说，插入操作从arr[0]到arr[i-1]的子列表中，并且需要平均i/2次比较。比较的平均总数为：
                 T(n) = 1/2 + 2/2 + 3/2 + ...... + (n-2)/2 + (n-1)/2 = n(n-1)/4
        根据T(n)的主项，插入排序算法的平均运行时间为O(n2)。最好情况为O(n)，最坏情况为O(n2)。

posted on 2008-06-11 23:56 Brian 阅读(2688) 评论(4)  编辑  收藏 所属分类: 数据结构与算法

评论

# re: 插入排序思路与泛型版本的实现 2008-06-12 00:16 eastmountain

很好，我也在这个基于泛型的算法，但是好多类都不是很清楚。所以刚刚放弃，看见你写的大受启发。呵呵，谢谢了。  回复  更多评论   

# re: 插入排序思路与泛型版本的实现 2008-06-12 10:56 盐田酒店

http://www.hotels-shenzhen.cn/jiudian-xinwen.asp?id=135  回复  更多评论   

# re: 插入排序思路与泛型版本的实现 2008-06-13 02:02 小梅沙听涛酒店

gjhtg  回复  更多评论   

# re: 插入排序思路与泛型版本的实现 2008-06-13 12:59 ~上善若水~

传智播客 &amp; ajax全套独家发布

1.ajax 入门

2.ajax 原理

3.ajax 简单实例

4.ajax 无限级联动菜单

5.ajax 简易聊天室

6.ajax 开源框架简介

7.DWR 框架源码分析一

8.DWR 框架源码分析二

9.DWR 框架源码分析三

10.DWR 框架源码分析四

11.DWR框架源码分析五

12.SSH + DWR完成商城驱动

13. Extjs 简介

14 Extjs&nbsp; 简单实例

15.SSH + Extjs 开发系列之OA一

16. SSH + Extjs 开发系列之OA二

17. SSH + Extjs 开发系列之OA三

18. SSH + Extjs 开发系列之OA四

19 .SSH + Extjs 开发系列之OA五

20.&nbsp;SSH + Extjs 开发系列之OA六

21. SSH + Extjs 开发系列之OA七

22.&nbsp;SSH + Extjs 开发系列之OA八

23.SSH + Extjs 开发系列之OA九

24.SSH + Extjs 开发系列之OA十

25. ajax 前景之我见

下载地址:http://www.ibeifeng.com/read.php?tid=2338&u=5043  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航:
 

公告


导航

<2008年6月>
日一二三四五六
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

统计

常用链接

留言簿(4)

随笔分类

随笔档案

收藏夹

搜索

最新评论

阅读排行榜

评论排行榜