• <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
            久久伊人五月天论坛| 中文字幕久久欲求不满| 中文成人久久久久影院免费观看| 久久国产高清一区二区三区| 一本综合久久国产二区| 久久精品中文騷妇女内射| 亚洲国产精久久久久久久| 亚洲国产成人精品91久久久| 18岁日韩内射颜射午夜久久成人 | 伊人久久综合热线大杳蕉下载| 国产精品成人99久久久久91gav | 狠狠色婷婷综合天天久久丁香 | 久久久久99精品成人片| 日韩人妻无码精品久久免费一| 久久er国产精品免费观看8| 77777亚洲午夜久久多人| 久久久黄片| 伊人久久综合热线大杳蕉下载| 亚洲精品无码久久一线| 久久久久亚洲精品天堂久久久久久 | 伊人久久大香线蕉精品不卡| 久久久久久免费一区二区三区| 一极黄色视频久久网站| 久久高清一级毛片| 99久久婷婷国产一区二区| 国产精品一区二区久久| 国内精品九九久久久精品| 97精品依人久久久大香线蕉97| 久久99热这里只频精品6| 久久久久这里只有精品| 婷婷综合久久狠狠色99h| 69久久精品无码一区二区| 浪潮AV色综合久久天堂| 亚洲中文久久精品无码ww16| 久久婷婷国产剧情内射白浆| 亚洲欧洲精品成人久久奇米网| 很黄很污的网站久久mimi色| 国内精品久久久久久麻豆| 久久精品99无色码中文字幕| 久久久久久久久久免免费精品| 日韩美女18网站久久精品|