带头结点的单链表实现极快、冒泡、直接插入/选择排序

结构体

1.  
   typedef int ElemType;
2.  
   typedef struct LNode {
3.  
   ElemType data;
4.  
   struct LNode* next;//指针域
5.  
   }LNode, * LinkList;

快速排序

1.  
   LinkList Quicksort(LinkList* listHead, LinkList* listTail)
2.  
   {
3.  
   LNode* current;
4.  
   LNode* lessHead = NULL, * lessTail = NULL, * moreHead = NULL, * moreTail = NULL;
5.  
   current = (*listHead)->next;//每次取首节点为枢纽，current指向第二个节点用于遍历
6.  
   if ((*listHead)->next != NULL)//当链表节点数不为1时(说明链表未排好序)
7.  
   {
8.  
   for (current = (*listHead)->next; current; current = current->next)
9.  
   {
10.  
    if (current->data < (*listHead)->data)
11.  
    {
12.  
    if (lessHead == NULL)
13.  
    lessHead = current;
14.  
    else
15.  
    lessTail->next = current;
16.  
    lessTail = current;
17.  
    }//current结点key小于枢纽key时放入less链表
18.  
    else
19.  
    {
20.  
    if (moreHead == NULL)
21.  
    moreHead = current;
22.  
    else
23.  
    moreTail->next = current;
24.  
    moreTail = current;
25.  
    }//current结点key大于枢纽key时放入more链表
26.  
    }
27.  
    //根据枢纽结点将T链表分为less和more两个链表
28.  
    if (moreTail)
29.  
    moreTail->next = NULL;
30.  
    if (lessTail)
31.  
    lessTail->next = NULL;
32.  
    //将more链表尾结点next域置空
33.  
    if (moreHead != NULL)
34.  
    {
35.  
    moreTail->next = NULL;
36.  
    Quicksort(&moreHead, &moreTail);
37.  
    (*listHead)->next = moreHead;
38.  
    *listTail = moreTail;
39.  
    }
40.  
    //若moreHead不空，则current为more链表的尾结点，对more链表进行递归处理,将more链表接在枢纽节点后
41.  
    else
42.  
    {
43.  
    (*listHead)->next = NULL;
44.  
    *listTail = *listHead;
45.  
    }
46.  
    //若moreHead为空，则只有less链表(即结点key全小于枢纽)，将枢纽结点接在less节点后
47.  
    if (lessHead != NULL)
48.  
    {
49.  
    lessTail->next = NULL;
50.  
    Quicksort(&lessHead, &lessTail);
51.  
    lessTail->next = *listHead;
52.  
    *listHead = lessHead;
53.  
    }
54.  
    //若lesseHead不空，对less链表进行递归处理，再将枢纽节点接在less链表后
55.  
    else
56.  
    {
57.  
    lessHead = *listHead;
58.  
    }
59.  
    //若lesseHead为空，则枢纽结点作为首节点
60.  
    return lessHead;
61.  
    }
62.  
    else
63.  
    return *listHead;
64.  
    }

直接插入排序

1.  
   //直接插入排序
2.  
   void Insertsort1(LinkList& L) {
3.  
   LNode* p = L->next, * q;
4.  
   LNode* r = p->next;
5.  
   p->next = NULL;
6.  
   p = r;
7.  
   while (p!=NULL)
8.  
   {
9.  
   r = p->next;
10.  
    q = L;
11.  
    while (q->next != NULL && q->next->data < p->data)
12.  
    q = q->next;
13.  
    p->next = q->next;
14.  
    q->next = p;
15.  
    p = r;
16.  
    }
17.  
    }

冒泡排序

1.  
   void BubbleSort(LinkList &L)
2.  
   {
3.  
   LNode* r, *t, *p;
4.  
   p = NULL;
5.  
    
6.  
   while (L->next->next != p)
7.  
   {
8.  
   r = L;
9.  
   t = L->next;
10.  
     
11.  
    while (t->next != p)
12.  
    {
13.  
    if (t->data > t->next->data)
14.  
    {
15.  
    r->next = t->next;
16.  
    t->next = t->next->next;
17.  
    r->next->next = t;
18.  
    t = r->next;
19.  
    }
20.  
    r = r->next;
21.  
    t = t->next;
22.  
    }
23.  
    p = t;
24.  
    }
25.  
     
26.  
    }

直接选择

//选出最小值
LinkList MinList(LinkList &L) {
    LinkList minp = L,  p = L->next;//minp指向头结点
    while (p != NULL) {
        if ((minp->data) > (p->data)) {
            minp = p;
        }
        p = p->next;
    }
    return minp;
}
//遍历链表并调用上述算法（选出最小值）
void SortList(LinkList& L) {
    LNode* j, * r = L->next;//j指向链表中最小的结点，r指向链表的当前结点
    int temp;//用于交换位置，设数据为整数
    while (r->next != NULL) {
        j = MinList(r);
        if (j->data != r->data) {
            temp = r->data;
            r->data = j->data;
            j->data = temp;
        }
        r = r->next;//如果当前结点数据就是最小值直接后移一位
    }
}

这篇好文章是转载于：学新通技术网