链表快速排序-白红宇

链表快速排序

阅读量：4091 次

发布时间：2019-05-25

本文共 2869 字，大约阅读时间需要 9 分钟。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;struct LinkNode{
       int val;    LinkNode *next;    LinkNode(int x): val(x)    {
           next = NULL;    }};LinkNode *partition_iter(LinkNode *head, LinkNode *tail){
       int pivot = head->val;    LinkNode *j = head;    LinkNode *i = head->next;    for (; i != tail; i = i->next)    {
           if(i->val < pivot)        {
               j = j->next;            swap(i->val, j->val);        }    }    swap(head->val, j->val);    return j;}void qSort(LinkNode *head, LinkNode *tail){
       if(head == tail)        return ;    LinkNode *pivot = partition_iter(head, tail);    //copy(v.begin(), v.end(), ostream_iterator
        
         (cout, " ")); qSort(head, pivot); qSort(pivot->next, tail);}int main(int argc, const char **argv){ LinkNode a('c'); LinkNode b('a'); LinkNode c('b'); a.next = &b; b.next = &c; qSort(&a, NULL); LinkNode *p = &a; while (p != NULL) { cout << p->val << " "; p = p->next; } return 0;}#if 0int partition(vector
         
           &v, int head, int tail){ int pivot = v.at(head); int j = head; int i = head + 1; for (; i <= tail; i++) { if(v.at(i) < pivot) { swap(v.at(i), v.at(++j)); } } swap(v.at(head), v.at(j)); return j;}void qSort(vector
          
            &v, int head, int tail){ if(head > tail) return ; int pivot = partition(v, head, tail); //copy(v.begin(), v.end(), ostream_iterator
           
            (cout, " ")); qSort(v, head, pivot - 1); qSort(v, pivot + 1, tail);}int main(int argc, const char **argv){ vector
            
              v { 4, 2, 6, 12, 10, -8, 3, 0}; qSort(v, 0, v.size() - 1); copy(v.begin(), v.end(), ostream_iterator
             
              (cout, " ")); return 0;}#endif#if 0list
              
               ::iterator partition_iter(list
               
                ::iterator head, list
                
                 ::iterator tail){ int pivot = *head; list
                 
                  ::iterator j = head; list
                  
                   ::iterator i = next(head); for (; i != tail; i++) { if(*i < pivot) { j++; swap(*i, *j); } } swap(*head, *j); return j;}void qSort(list
                   
                    ::iterator head, list
                    
                     ::iterator tail){ if(head == tail) return ; list
                     
                      ::iterator pivot = partition_iter(head, tail); //copy(v.begin(), v.end(), ostream_iterator
                      
                       (cout, " ")); qSort( head, pivot); qSort( ++pivot, tail);}int main(int argc, const char **argv){ list
                       
                         v { 4, 2, 6, 12, 10, -8, 3, 0}; qSort(v.begin(), v.end()); copy(v.begin(), v.end(), ostream_iterator
                        
                         (cout, " ")); return 0;}#endif