• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            2011排序-歸并排序(數組 & 鏈表)

            歸并排序: 平均時間復雜度與最壞時間復雜度都是O(nlogn),穩定排序

            歸并排序是把序列遞歸地分成短序列,遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列合并成一個有序的長序列,不斷合并直到原序列全部排好序。可以發現,在1個或2個元素時,1個元素不會交換,2個元素如果大小相等也沒有人故意交換,這不會破壞穩定性。那么,在短的有序序列合并的過程中,穩定是是否受到破壞?沒有,合并過程中我們可以保證如果兩個當前元素相等時,我們把處在前面的序列的元素保存在結果序列的前面,這樣就保證了穩定性。所以,歸并排序也是穩定的排序算法。


            void
            merge(
            int *array, int *aux, int begin, int mid, int end)
            {
                
            int len = end - begin + 1;
                memcpy(aux
            +begin, array+begin, sizeof(int)*len);

                
            int *first, *second, *ptr = array+begin;
                first 
            = aux+begin;
                second 
            = aux+mid+1;
                
            while(first<=aux+mid && second<=aux+end) {
                    
            if(*first <= *second)
                        
            *ptr++ = *first++;
                    
            else
                        
            *ptr++ = *second++;
                }
                
            if(first <= aux+mid)
                    
            while(first <= aux+mid)
                        
            *ptr++ = *first++;
                
            if(second <= aux+end)
                    
            while(second <= aux+end)
                        
            *ptr++ = *second++;
            }

            void
            merge_sort_dc(
            int *array, int *aux, int begin, int end)
            {
                
            if(begin >= end)
                    
            return;
                
            int mid = begin + ((end-begin)>>1);
                merge_sort_dc(array, aux, begin, mid);
                merge_sort_dc(array, aux, mid
            +1, end);
                merge(array, aux, begin, mid, end);
            }

            void 
            merge_sort(
            int *array, int len)
            {
                
            int *aux = (int *)malloc(sizeof(int* len);
                merge_sort_dc(array, aux, 
            0, len-1);
                free(aux);
            }

            struct Node {
                
            int val;
                
            struct Node *next;
            };

            struct Node *
            list_merge(
            struct Node *first, struct Node *second)
            {
                
            if(first == NULL)
                    
            return second;
                
            if(second == NULL)
                    
            return first;

                
            struct Node *node = NULL;
                
            if(first->val <= second->val) {
                    node 
            = first;
                    first 
            = first->next;
                } 
            else {
                    node 
            = second;
                    second 
            = second->next;
                }
                node
            ->next = list_merge(first, second);
                
            return node;
            }

            struct Node *
            list_merge_sort(
            struct Node *list)
            {
                
            if(list==NULL || list->next==NULL)
                    
            return list;
                
            struct Node *once = list;
                
            struct Node *twice = list;
                
            while(twice->next && twice->next->next) {
                    once 
            = once->next;
                    twice 
            = twice->next->next;
                }
                twice 
            = once->next;
                once
            ->next = NULL;
                once 
            = list;
                list_merge(list_merge_sort(once), list_merge_sort(twice));
            }

            posted on 2011-07-29 19:39 simplyzhao 閱讀(330) 評論(0)  編輯 收藏 引用 所屬分類: R_找工復習2011

            導航

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产精品久久久久久久| 久久精品国产亚洲网站| 久久精品中文字幕大胸| 精品综合久久久久久98| 欧美精品一区二区精品久久| 精品国产一区二区三区久久蜜臀| 久久久午夜精品福利内容| 久久一日本道色综合久久| 国产A级毛片久久久精品毛片| 亚洲国产婷婷香蕉久久久久久| 精品久久久久久成人AV| 合区精品久久久中文字幕一区| 国产成人久久激情91| 香蕉99久久国产综合精品宅男自| 久久99精品国产自在现线小黄鸭| 久久精品无码一区二区三区日韩| 无码伊人66久久大杳蕉网站谷歌 | 久久综合给合综合久久| 久久婷婷五月综合色奶水99啪| 久久嫩草影院免费看夜色| 精品久久久久久无码中文字幕一区 | 日本精品一区二区久久久| 精品一区二区久久| 久久人人爽爽爽人久久久| 一本色道久久综合狠狠躁篇 | 久久久无码一区二区三区| 一本久道久久综合狠狠躁AV| 久久精品?ⅴ无码中文字幕| AAA级久久久精品无码片| 日韩精品久久久久久久电影蜜臀| 亚洲狠狠久久综合一区77777| 国内精品人妻无码久久久影院导航 | 精品一二三区久久aaa片| 大香网伊人久久综合网2020| 人妻无码αv中文字幕久久琪琪布| 久久精品中文字幕第23页| 99久久国产免费福利| 四虎国产精品免费久久5151| 国产V综合V亚洲欧美久久| 久久国产成人精品麻豆| 91久久精品无码一区二区毛片|