亚洲午夜在线视频,日韩精品一区二区三区外面,蜜乳av另类精品一区二区

插入排序思路與泛型版本的實(shí)現(xiàn)

一.插入排序算法的思路
        假定這個(gè)數(shù)組的序是排好的，然后從頭往后，如果有數(shù)比當(dāng)前外層元素的值大，則將這個(gè)數(shù)的位置往后挪，直到當(dāng)前外層元素的值大于或者等于它前面的位置為止。
二.插入排序算法實(shí)例
        用五個(gè)名字(Monroe,Chin,Flores,Stein和Dare)的列表的插入排序算法為例：
                                       Monroe    從Monroe開始

        處理名字Chin        Chine Monroe    將Chin插入到位置0；Monroe移動(dòng)至位置1

        處理名字Flores     Chine Flores Monroe    將Flores插入到位置1；Monroe移動(dòng)至位置2

        處理名字Stein       Chine Flores Monroe Stein    Stein位置正確

        處理名字Dare       Chine Dare Flores Monroe Stein    將Dare插入在位置1；列表尾部向右移動(dòng)

三.插入排序算法的實(shí)現(xiàn)

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是數(shù)組的長(zhǎng)度，那么插入排序需要n-1遍。對(duì)于通用的遍i來(lái)說(shuō)，插入操作從arr[0]到arr[i-1]的子列表中，并且需要平均i/2次比較。比較的平均總數(shù)為：
                 T(n) = 1/2 + 2/2 + 3/2 + ...... + (n-2)/2 + (n-1)/2 = n(n-1)/4
        根據(jù)T(n)的主項(xiàng)，插入排序算法的平均運(yùn)行時(shí)間為O(n²)。最好情況為O(n)，最壞情況為O(n²)。

posted on 2008-06-11 23:56 Brian 閱讀(2709) 評(píng)論(4) 編輯收藏所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法

評(píng)論

# re: 插入排序思路與泛型版本的實(shí)現(xiàn) 2008-06-12 00:16 eastmountain

很好，我也在這個(gè)基于泛型的算法，但是好多類都不是很清楚。所以剛剛放棄，看見你寫的大受啟發(fā)。呵呵，謝謝了。回復(fù) 更多評(píng)論

# re: 插入排序思路與泛型版本的實(shí)現(xiàn) 2008-06-12 10:56 鹽田酒店

http://www.hotels-shenzhen.cn/jiudian-xinwen.asp?id=135 回復(fù) 更多評(píng)論

# re: 插入排序思路與泛型版本的實(shí)現(xiàn) 2008-06-13 02:02 小梅沙聽濤酒店

gjhtg 回復(fù) 更多評(píng)論

# re: 插入排序思路與泛型版本的實(shí)現(xiàn) 2008-06-13 12:59 ~上善若水~

傳智播客 & ajax全套獨(dú)家發(fā)布

1.ajax 入門

2.ajax 原理

3.ajax 簡(jiǎn)單實(shí)例

4.ajax 無(wú)限級(jí)聯(lián)動(dòng)菜單

5.ajax 簡(jiǎn)易聊天室

6.ajax 開源框架簡(jiǎn)介

7.DWR 框架源碼分析一

8.DWR 框架源碼分析二

9.DWR 框架源碼分析三

10.DWR 框架源碼分析四

11.DWR框架源碼分析五

12.SSH + DWR完成商城驅(qū)動(dòng)

13. Extjs 簡(jiǎn)介

14 Extjs  簡(jiǎn)單實(shí)例

15.SSH + Extjs 開發(fā)系列之OA一

16. SSH + Extjs 開發(fā)系列之OA二

17. SSH + Extjs 開發(fā)系列之OA三

18. SSH + Extjs 開發(fā)系列之OA四

19 .SSH + Extjs 開發(fā)系列之OA五

20. SSH + Extjs 開發(fā)系列之OA六

21. SSH + Extjs 開發(fā)系列之OA七

22. SSH + Extjs 開發(fā)系列之OA八

23.SSH + Extjs 開發(fā)系列之OA九

24.SSH + Extjs 開發(fā)系列之OA十

25. ajax 前景之我見

下載地址:http://www.ibeifeng.com/read.php?tid=2338&u=5043 回復(fù) 更多評(píng)論

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問(wèn) 管理
相關(guān)文章: 歸并排序思路與泛型版本的實(shí)現(xiàn) 插入排序思路與泛型版本的實(shí)現(xiàn)

# re: 插入排序思路與泛型版本的實(shí)現(xiàn) 2008-06-12 00:16 eastmountain

# re: 插入排序思路與泛型版本的實(shí)現(xiàn) 2008-06-12 10:56 鹽田酒店

# re: 插入排序思路與泛型版本的實(shí)現(xiàn) 2008-06-13 02:02 小梅沙聽濤酒店

# re: 插入排序思路與泛型版本的實(shí)現(xiàn) 2008-06-13 12:59 ~上善若水~

最愛Java

插入排序思路與泛型版本的實(shí)現(xiàn)

評(píng)論

公告

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

收藏夾

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜