中文在线观看免费,黄色小视频在线免费观看,日本一区二区三区播放

插入排序思路與泛型版本的實現

一.插入排序算法的思路
        假定這個數組的序是排好的，然后從頭往后，如果有數比當前外層元素的值大，則將這個數的位置往后挪，直到當前外層元素的值大于或者等于它前面的位置為止。
二.插入排序算法實例
        用五個名字(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(n²)。最好情況為O(n)，最壞情況為O(n²)。

posted on 2008-06-11 23:56 Brian 閱讀(2699) 評論(4) 編輯收藏所屬分類: 數據結構與算法

傳智播客 & 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  簡單實例

15.SSH + Extjs 開發系列之OA一

16. SSH + Extjs 開發系列之OA二

17. SSH + Extjs 開發系列之OA三

18. SSH + Extjs 開發系列之OA四

19 .SSH + Extjs 開發系列之OA五

20. SSH + Extjs 開發系列之OA六

21. SSH + Extjs 開發系列之OA七

22. SSH + Extjs 開發系列之OA八

23.SSH + Extjs 開發系列之OA九

24.SSH + Extjs 開發系列之OA十

25. ajax 前景之我見

下載地址:http://www.ibeifeng.com/read.php?tid=2338&u=5043 回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 歸并排序思路與泛型版本的實現插入排序思路與泛型版本的實現

# re: 插入排序思路與泛型版本的實現 2008-06-12 00:16 eastmountain

# re: 插入排序思路與泛型版本的實現 2008-06-12 10:56 鹽田酒店

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

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

最愛Java

插入排序思路與泛型版本的實現

評論

公告

導航

統計

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

收藏夾

搜索

最新評論

閱讀排行榜

評論排行榜