• <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 閱讀(2892) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            色综合色天天久久婷婷基地| 色偷偷91久久综合噜噜噜噜| 久久久噜噜噜久久中文字幕色伊伊 | 久久国产免费直播| 精品熟女少妇aⅴ免费久久| 手机看片久久高清国产日韩 | 国内精品伊人久久久久影院对白 | 97精品国产97久久久久久免费| 国产 亚洲 欧美 另类 久久| 久久亚洲国产成人影院| 丰满少妇人妻久久久久久| 久久精品中文字幕有码| 伊人久久精品无码av一区| 一本久久久久久久| 日韩久久久久久中文人妻 | 亚洲一区二区三区日本久久九| 伊人久久国产免费观看视频| 精品国产VA久久久久久久冰 | 久久国语露脸国产精品电影| 久久伊人精品青青草原高清| 久久天天躁狠狠躁夜夜躁2014| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 99久久久精品免费观看国产| 久久福利资源国产精品999| 丁香五月综合久久激情| 大伊人青草狠狠久久| 无码精品久久久久久人妻中字| 久久最新免费视频| 欧美一区二区精品久久| 久久香蕉超碰97国产精品| 久久亚洲AV无码精品色午夜麻豆| 婷婷综合久久狠狠色99h| 97超级碰碰碰久久久久| 人妻精品久久久久中文字幕69| 热99RE久久精品这里都是精品免费 | 久久精品亚洲欧美日韩久久| 国产成人精品久久一区二区三区| 久久精品国产久精国产一老狼| 久久天天躁夜夜躁狠狠躁2022| 人妻无码精品久久亚瑟影视| 日韩十八禁一区二区久久|