c++实现单链表的简单排序【冒泡排序，选择排序，插入排序】

结构体：

typedef struct Node {
	int data;
	Node* next;
	Node(int x) :data(x), next(NULL) {};
}*BiNode;

创建链表

void create_link(BiNode &head, int x) {
	Node* p = new Node(x);
	if (head == NULL)
		head = p;
	else {
		Node* cur = head;
		while (cur->next) {
			cur = cur->next;
		}
		cur->next = p;
	}
}

冒泡排序

void msort(BiNode &head) {
	if (head == NULL || head->next==NULL)
		return;
	Node* newhead = head;
	Node* cur = head;
	Node* tail = NULL;
	for (newhead;newhead->next != NULL;newhead = newhead->next) {//单链表冒泡排序的外层循环仅仅其循环计数作用,而数组的外层循环也可以代表要确定位置的元素。
		for (cur = head;cur->next != tail;cur = cur->next) {//内层循环永远从头开始遍历到上次的尾部
			int t = 0;
			if (cur->data > cur->next->data) {
				t = cur->data;
				cur->data = cur->next->data;
				cur->next->data = t;
			}
		}
		tail = cur;
	}
}

选择排序

void xsort(BiNode &head) {
	if (head == NULL || head->next == NULL) 
		return;
	Node* cur;
	Node* tem;
	for (cur=head;cur->next != NULL;cur = cur->next) {
		Node* min = cur;
		for (tem = cur;tem != NULL;tem = tem->next) {
			if (tem->data < min->data) {
				int t = min->data;
				min->data = tem->data;
				tem->data = t;
			}
		}
		cur->data = min->data;
	}
}

插入排序：

Node*  csort(BiNode head) {
	if (head == NULL || head->next == NULL)
		return head;
	Node* dummyhead = new Node(0);//伪指针
	dummyhead->next = head;
	Node* last = head;//已排序部分的最后一个结点
	Node* cur = head->next;
	while (cur) {
		if (last->data <= cur->data) {
			last = last->next;
		}
		else {
			Node* pre = dummyhead;
			while (pre->next->data <= cur->data)
				pre = pre->next;
			last->next = cur->next;
			cur->next = pre->next;
			pre->next = cur;
		}
		cur = last->next;
	}
	return dummyhead->next;
}