• <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 閱讀(2891) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            狠狠色伊人久久精品综合网| 少妇精品久久久一区二区三区| 久久青青国产| 久久久高清免费视频| 久久激情五月丁香伊人| 国产亚洲成人久久| 亚洲AV乱码久久精品蜜桃| 久久久久亚洲av无码专区喷水 | 久久人做人爽一区二区三区| 久久精品国内一区二区三区| 亚洲精品国产字幕久久不卡| 亚洲国产精品无码久久久久久曰| 日批日出水久久亚洲精品tv| 久久精品中文字幕第23页| 色播久久人人爽人人爽人人片aV| 国产精品久久久香蕉| 久久精品国产亚洲av麻豆小说| 久久99精品综合国产首页| 国内精品久久久久久久久电影网| 亚洲第一永久AV网站久久精品男人的天堂AV| 精品一二三区久久aaa片| 99久久精品国产免看国产一区| 国产AV影片久久久久久| 久久亚洲国产成人影院网站| 日本久久中文字幕| 久久国产精品二国产精品| 99久久99久久精品国产片果冻 | 亚洲国产精品高清久久久| 91精品国产高清久久久久久国产嫩草 | 性做久久久久久久久浪潮| 久久婷婷五月综合国产尤物app| 伊人色综合久久| 青青青青久久精品国产| 一本久久a久久精品vr综合| 国产精品亚洲美女久久久| 色婷婷久久综合中文久久蜜桃av| 久久精品成人| 亚洲国产日韩欧美久久| 国产精品成人久久久久久久 | 国产午夜精品理论片久久影视 | 四虎国产精品成人免费久久|