链表排序，反转算法

介绍、

链表排序思想和数组排序类似，区别就是数组遍历容易，数据交换也容易；链表(单项链表)只能一个方向遍历，不能逆序遍历，且不能随机访问，所以排序比较麻烦。所以下文将使用双向循环链表来进行排序。

排序思想、

链表排序和顺序表排序不相同，适用于顺序表的排序方法有些在链表上并不适用！排序方法有交换数据域的值和交换节点来进行排序。

下面是我双向循环链表的结点结构体，和链表结构体设计，为了方便链表的操作，一般都会在链表结构体中加入一个头指针。

template<class _Ty>
class node
{
public:
	node* prev;    //前驱指针域
	node* next;    //后继指针域
	_Ty data;      //数据域
};

template<class _Ty>
class list
{
public:
        using node_pointer = node<_Ty>*;
        ......
private:
        size_t sizes;         //链表结点数量

        node_pointer _head;   //头结点指针
};

下面是交换一个双向循环链表两个节点的函数

// p1，p2是任意的两个节点指针
void _swap_(node_pointer p1, node_pointer p2)
{
	// 判断交换的特殊情况，两个节点是否相等，是否是头结点。
	if (p1 == p2 || p1 == _head || p2 == _head)
	{
		return;
	}

	//临时指针，记录交换节点的一些信息
	node_pointer p1_prev = p1->prev;   //p1的前驱
	node_pointer p1_next = p1->next;   //p1的后继
	node_pointer p2_prev = p2->prev;   //p2的前驱
	node_pointer p2_next = p2->next;   //p2的后继

        //相邻的情况需要调整6次指针，不相邻需要调整8次指针
	if (p1->next == p2)                //如果两个节点相邻的情况，p1在p2前面
	{
		p1_prev->next = p2;
		p2->prev = p1_prev;
		p2->next = p1;
		p1->prev = p2;
		p1->next = p2_next;
		p2_next->prev = p1;
	}
	else if (p2->next == p1)          //如果两个节点相邻的情况，p2在p1前面
	{
		p1->prev = p2_prev;
		p2_prev->next = p1;
		p1->next = p2;
		p2->prev = p1;
		p2->next = p1_next;
		p1_next->prev = p2;
	}
	else                              //不相邻的情况
	{
		p1_prev->next = p2;       //p1的前驱的next指向p2
		p2->prev = p1_prev;       //p2的前驱指向p1的前驱
		p2->next = p1_next;       //p2的next指向p1的next
		p1_next->prev = p2;       //p1的next的prev指向p2
		p2_prev->next = p1;       //p2的prev的next指向p1
		p1->prev = p2_prev;       //p1的prev指向p2的prev
		p2_next->prev = p1;       //p2的next 的prev指向p1
		p1->next = p2_next;       //p1的next指向p2的next
	}

}

使用交换节点排序的方法有一个大坑！！！！！就是交换了两个节点后，原先指针指向的节点的节点前后信息就改变了！！！。

假设我有一个q指针指向节点p1，然后我交换节点p1和节点p3后，q->next从原先的p2变成了p4，会造成排序错误！！！！所以就需要更新q指针的值，使其指向交换的节点！！也就是q = p3。

排序方法、

（1）选择排序

//交换节点的方法
void select_sort()
{
        if (sizes < 2 )
	{
		return;
	}
	node_pointer min_node = nullptr;
	for (node_pointer p = _head->next; p != _head ->prev; p = p->next)
	{
		min_node = p;
		for (node_pointer q = p->next; q != _head; q = q->next)
		{
			if (q->data < min_node->data)
			{
				min_node = q;
			}
		}
		if (min_node != p)
		{
			_swap_(p, min_node);
			p = min_node;           //关键的一步！！！  
		}
	}
}

//交换节点值的方法
void select_sort()
{
        if (sizes < 2 )
	{
		return;
	}
	node_pointer min_pointer = nullptr;
	for (node_pointer p = _head->next; p != _head->prev; p = p->next)
	{
		min_pointer = p;
		for (node_pointer q = p->next; q != _head; q = q->next)
		{
			if (q->data < min_pointer->data)
			{
				min_pointer = q;
			}
		}
		if (min_pointer != p)
		{
			swap(min_pointer->data,p->data);
		}
	}
}

（2）插入排序

void insert_sort()
{
	if (sizes < 2 )
	{
		return;
	}

	for (node_pointer p = _head->next->next; p != _head; p = p->next)
	{
		for (node_pointer q = p; q != _head ->next; q = q->prev)
		{
			if (q->data < q->prev->data)
			{
				p = q->prev;   //关键！！！
				_swap_(q->prev, q);
				q = p;         //关键！！！
			}
			else
			{
				break;
			}
		}
	}
}

反转算法、

void reverse()
{
	node_pointer cur = _head->prev;
	node_pointer first = _head->next;
	node_pointer last = _head->prev;
	node_pointer prev = nullptr;
	node_pointer next = nullptr;
	while (cur != _head)
	{
		next = cur->next;
		prev = cur->prev;
		cur->next = prev;
		cur->prev = next;
		cur = cur->next;
	}
	_head->prev = first;
	_head->next = last;
}