• <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)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品麻豆日日躁夜夜躁| 久久国产精品国产自线拍免费 | 久久91精品国产91久| 久久亚洲国产成人精品无码区| 久久精品二区| 无码伊人66久久大杳蕉网站谷歌 | 久久久精品国产亚洲成人满18免费网站| 亚洲欧美精品伊人久久| 亚洲国产成人久久一区久久| 久久亚洲精品中文字幕| 久久久久国色AV免费看图片| 久久精品黄AA片一区二区三区| 日韩十八禁一区二区久久| 国产成人久久精品激情| 精品久久久一二三区| 国产成人无码精品久久久久免费| 亚洲AV无码久久精品色欲| 午夜精品久久久久久影视riav| 蜜桃麻豆www久久| 久久久久亚洲Av无码专| 久久夜色精品国产亚洲| 韩国三级中文字幕hd久久精品| 国产成人无码久久久精品一| 一本色道久久88—综合亚洲精品| 久久久久国产成人精品亚洲午夜| 精品久久久久久久无码| 日韩精品久久久肉伦网站| 久久精品国产乱子伦| 伊人久久国产免费观看视频| 久久久久无码专区亚洲av| 国产精品久久久天天影视香蕉 | 亚洲欧美成人综合久久久| 国产一区二区久久久| 一级A毛片免费观看久久精品| 精品久久久久中文字幕一区| 成人国内精品久久久久影院VR| www性久久久com| 夜夜亚洲天天久久| 久久激情亚洲精品无码?V| 久久久中文字幕日本| 亚洲人AV永久一区二区三区久久|