链表快速排序

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
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<int>(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 0
int partition(vector<int> &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<int> &v, int head, int tail)
{
    if(head > tail)
        return ;

    int pivot = partition(v, head, tail);
    //copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    qSort(v, head, pivot - 1);
    qSort(v, pivot + 1, tail);
}

int main(int argc, const char **argv)
{
    vector<int> v {4, 2, 6, 12, 10, -8, 3, 0};
    qSort(v, 0, v.size() - 1);

    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    return 0;
}
#endif

#if 0
list<int>::iterator partition_iter(list<int>::iterator head, list<int>::iterator tail)
{
    int pivot = *head;
    list<int>::iterator j = head;
    list<int>::iterator i = next(head);

    for (; i != tail; i++)
    {
        if(*i < pivot)
        {
            j++;
            swap(*i, *j);
        }
    }
    swap(*head, *j);
    return j;
}

void qSort(list<int>::iterator head, list<int>::iterator tail)
{
    if(head == tail)
        return ;

    list<int>::iterator pivot = partition_iter(head, tail);
    //copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    qSort( head, pivot);
    qSort( ++pivot, tail);
}

int main(int argc, const char **argv)
{
    list<int> v {4, 2, 6, 12, 10, -8, 3, 0};
    qSort(v.begin(), v.end());

    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    return 0;
}

#endif

备份地址: 【链表快速排序】