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

            coding everyday

            編程面試題 https://interview.codeplex.com

            C++博客 首頁 新隨筆 聯系 聚合 管理
              12 Posts :: 2 Stories :: 7 Comments :: 0 Trackbacks
            單鏈表的快速排序
            單鏈表的快速排序跟數組的排序原理上一致,有一個分區(區分)的函數在一個區間中針對某個標桿值進行區分,比它大的放它后面,比它小的放它前面,并返回它的地址,好對它前面的以及它后面的遞歸。

            單鏈表的快速排序跟數組有個明顯的區別,就是指示起始和終止的元素,在一輪之后它們在鏈表中的位子會發生改變,所以需要返回一個新的起始的位置(終止的位置)
            我的算法中總是拿后一個的節點作為終止位置,所以它在鏈表中的位子其實是不改變的,所以我只修改了起始位置指向新的起始位置即可。

            我的算法是,用2個鏈表,一個放比它大的一個放比它小的,最后接起來,它的位置就是mid,而其實位置就是當初起始的前一個節點在新鏈表中的next。有點拗口,就是說a->start->...->nullptr,這一輪傳進來的是start,那么經過這輪的分區之后,start的位置肯定改變了,對吧?但是a->next的地址沒有改變,即&(a->next),因為start之前的都會原封不動的放在那里。我覺得用指針的地址來處理是這里的關鍵之處吧。


            這是一輪partition之前和之后的圖示,之后就對于(begin, mid)和(mid->next, end)進行快速排序即可。

             1 // Problem: sort a singly link list by Quick Sort
             2 node *partition(list &l, node *&begin, node *end = nullptr) {
             3     // if end is the next node, that means it's only one node to sort
             4     if (begin == nullptr || end == begin->next) {
             5         return nullptr;
             6     }
             7 
             8     list small_list, big_list;
             9     node *current = l.root;
            10     node *pivot = begin;
            11     node **pbegin;          // points to the address of begin
            12     node **s_current = &small_list.root, **b_current = &big_list.root;
            13 
            14     // move previous nodes before 'begin' to small list
            15     while (current != begin) {
            16         *s_current = current;
            17         s_current = &(*s_current)->next;
            18         current = current->next;
            19     }
            20 
            21     // pbegin presents the location(address) of begin item, e.g. if (a->next == begin) then pbegin = &a->next;
            22     pbegin = s_current;
            23 
            24     while (begin != end) {
            25         if (begin->data < pivot->data) {
            26             *s_current = begin;
            27             s_current = &(*s_current)->next;
            28         }
            29         else {
            30             *b_current = begin;
            31             b_current = &(*b_current)->next;
            32         }
            33 
            34         begin = begin->next;
            35     }
            36 
            37     // pass begin back to quick_sort for next sort action
            38     begin = *pbegin;
            39 
            40     *b_current= end;
            41     *s_current = big_list.root;
            42     l = small_list;
            43     l.print();
            44 
            45     // current pivot would be the end node for smaller set sorting
            46     return big_list.root;
            47 }
            48 
            49 void quick_sort(list &l, node *begin, node *end = nullptr) {
            50     if (begin == end) {
            51         return;
            52     }
            53     // mid represents the pivot node which is the next node of the end of the small list
            54     node *mid = partition(l, begin, end);
            55 
            56     if (mid != nullptr){
            57         quick_sort(l, begin, mid);
            58     }
            59 
            60     if (mid != nullptr &&
            61         mid->next != nullptr) {        
            62         quick_sort(l, mid->next, end);
            63     }
            64 }

            代碼
            posted on 2013-07-12 13:41 everyday 閱讀(2893) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            久久被窝电影亚洲爽爽爽| 精品国产VA久久久久久久冰| 99久久婷婷国产一区二区| 国产精品亚洲综合专区片高清久久久| 亚洲国产精品人久久| 久久久综合香蕉尹人综合网| 免费无码国产欧美久久18| 国产精品99久久精品| 青春久久| 国产一区二区三区久久| 亚洲国产成人乱码精品女人久久久不卡| 日韩美女18网站久久精品| 国产麻豆精品久久一二三| 国产亚洲色婷婷久久99精品91| 国产色综合久久无码有码| 国产精品美女久久久免费 | 91精品无码久久久久久五月天 | 久久不见久久见免费视频7| 一本久久久久久久| 久久人人爽人人爽人人AV东京热 | 久久精品aⅴ无码中文字字幕不卡| 色综合久久久久| 99久久99久久精品免费看蜜桃| 亚洲欧洲久久久精品| 岛国搬运www久久| 精品少妇人妻av无码久久| 99久久做夜夜爱天天做精品| 久久精品成人免费观看97| 97精品伊人久久大香线蕉app| 久久国产色av免费看| 久久久久久国产精品美女| 久久丝袜精品中文字幕| 久久综合色之久久综合| 久久99精品免费一区二区| 狠狠色伊人久久精品综合网| 精品久久久久久无码人妻热 | 91精品国产色综合久久| 久久久久人妻一区精品色| 久久久久亚洲AV无码永不| 婷婷伊人久久大香线蕉AV| 久久99国产精品尤物|