排序应用于链表

前面两篇主要扯了些排序的算法，这些算法写的过程中都是应用于数组实现的，那么如何应用于链表实现这些排序算法呢？

先给出我对链表的结构体的定义以方便阅读算法代码：

typedef struct node {
	struct node *next;
	int data;
}CNode, *Linklist;

①冒泡排序

void bubblesort(Linklist head){
    Linklist p1;
    Linklist temp;
    int count = 0;
    for(temp = head; temp != NULL; temp = temp -> next)
        count ++;                                                      //这里是通过循环算出链表的长度。
    for(int i =0; i < count - 1; count --){                              
        for(p1 = head; p1 -> next != NULL; p1 = p1 -> next){           //依次比较尚未冒出的前count个元素
            if(p1 -> data > p1 -> next -> data){                       //通过依次比较选出最大的值放在最后
                int t = p1 -> data;         
                p1 -> data = p1 -> next -> data;
                p1 -> next -> data = t;
            }
        }
    }
}

这里对于冒泡排序，针对单链表访问上一个结点的苦难，所以我选择先冒出大的数值，然后依次往前排序。这样可以避免里层循环在遍历的时候不方便比较与外层指针的位置关系的问题。

②选择排序

选择排序针对于链是和对于数组是非常相似的，我们仍需要从头到尾进行与后面元素中的小于这个数本身的最小值与这个值交换的方法。

Linklist getmin(Linklist p, int value){                                //得到最小的值的指针 
    Linklist temp;
    Linklist q = NULL;
    for(temp = p; temp != NULL; temp = temp -> next){
        if(temp -> data < value){
            q = temp;
            value = q -> data;
        }
    }
    return q;
}

void selectsort(Linklist head){
	Linklist temp;
	Linklist p;
	int  t;
	for(temp = head; temp -> next != NULL; temp = temp -> next){   //temp代表的是左面依次移动的那个元素
 		p = getmin(temp, temp -> data);                        
		if(p == NULL)                                          //如果返回的还是函数中定义的NULL的p的话，说明之后没有比此元素更小的元素，继续循环
			continue;
		t = p -> data;                                         //交换
		p -> data = temp -> data;
		temp -> data = t;
	}
}

③插入排序

插入排序因为涉及到要插入的原因，所以需要较多指针来卡出插入的位置，但是还是很类似于

Linklist Insert_Sort(Linklist head)
{
	CNode *p1, *p2, *first, *temp;
	first = head -> next;                                                       //first在这里的作用是指向插排中未排序的第一个元素     
	head -> next = NULL;                                                        //用head拿出已经排好序的序列
	while(first != NULL){
		for(p1 = head, temp = first;  p1 != NULL && p1 -> data < temp -> data; p2 = p1, p1 = p1 -> next);
                                             //p1和p2这两个元素分别指向查找并卡住插入的位置，为了防止改变first的值，用temp来遍历查找
                first = first -> next;       //first指向下一个元素，即原指的元素会插入排好序的序列并组成新的有序序列
		if(p1 == head){
			temp -> next = head;                                       //如果p1的值一直未变，说明这个元素要插在第一位
			head = temp;
		}
		else {
			p2 -> next = temp;                                         //插入在p1和p2之间
                        temp -> next = p1;
		}
	}
	return head;
}

④归并排序

涉及到归并排序对链表进行排序比较麻烦，因为我们需要找到一个序列的中间。我们可以设计一个快的指针一个慢的指针来实现，也就是，当快的指针走两步的时候，慢的指针只指向下一步，这样在快指针到达NULL的时候，慢指针正好到达中间。当然我们需要改变指针的地址，所以我选择使用二级指针。

下面是分割函数：

void Split(Linklist source, Linklist *front, Linklist *rear){  //参量是头结点和要分割的两个头，即头和尾，因为要改变指针的地址并传回原函数，用二级指针
	Linklist fast;                                         //快指针
	Linklist slow;                                         //慢指针
	if(source == NULL || source -> next == NULL){          //如果这是个空表或是表中只有一个元素，那么不需要分割
		*front = source;                               //针对上面的情况是让头等于头，尾指向空
		*rear = NULL;
	}
	else {                                                
		slow = source;                                 //开始分割，让慢指针指向头结点，快指针指向头结点的下一个位置
		fast = source -> next;
	}
	while(fast != NULL){
		fast = fast -> next;
		if(fast != NULL){
			fast = fast -> next;
			slow = slow -> next;                   //慢指针每指向下一个位置，快指针指向下两个位置。
		}
	}

	*front = source;                                       //分割完成后让头指向头结点
	*rear = slow -> next;                                  //令尾指向慢指针的下一个位置，类似归并排序中的middle + 1，相当于分好的一段的尾位置
	slow -> next = NULL;                                   //截断尾位置之后的链表
}

除了分割，我们仍需要对排序好了的序列们进行合并。那么下面的函数就是实现这个功能：

Linklist SortedMerge(Linklist a, Linklist b){
	Linklist result = NULL;                       //类似于之前归并排序创建的一个temp数组，用来存储排好序的序列
	if(a == NULL)                                 //如果a已经到头，直接接上b
		return b;
	else if(b == NULL)                            //若果b已经到头，直接接上a
		return a;
	if(a -> data <= b -> data){                   //比较，如果a小的话，先将a的那个结点接上，然后递归进行比较
		result = a;
		result -> next = SortedMerge(a -> next, b);
	}
	else {
		result = b;
		result -> next = SortedMerge(a, b -> next);            //与if类似
	}
	return result;                                //返回合成后排好序的链表
}

最后我们需要一个函数来改变头结点。

void MergeSort(Linklist *head){
	Linklist new_head = *head;
	Linklist a;
	Linklist b;
	if(new_head == NULL || new_head -> next == NULL) //如果原链表中没有元素或者只有一个元素，视为已经排好序
		return ;
	Split(&a, &b);                                   //分割a和b
	MergeSort(&a);                                   //递归分割a部分
	MergeSort(&b);                                   //递归分割b部分
	*head = SortedMerge(a, b);                       //改变head的值
}

归并排序对于链表的实现大概就是这样。这一篇我们主要研究了冒泡选择插入和归并排序对于单链表的实现。下篇将带来对于单链表的快速排序的讨论。