链表定义及主函数

1、list.h文件

1、	#ifndef _LIST_H_  2、	#define _LIST_H_  3、	  4、	struct ListNode  5、	{  6、	    int val;  7、	    ListNode* next;  8、	};  9、	  10、#endif

2、main.cpp（省去链表排序代码）

1.	#include 
   
      2.	  3.	using namespace std;  4.	  5.	#include "List.h"  6.	  7.	void InsertionSortList();  8.	void SelectSortList();  9.	  10.	//构建链表头结点  11.	ListNode* head = new ListNode;  12.	  13.	int main()  14.	{  15.	    head->next = NULL;  16.	      17.	    //对链表赋值  18.	    for (int i = 0; i < 10; ++i)  19.	    {  20.	          21.	        ListNode* p = new ListNode;  22.	        cin >> p->val;  23.	        p->next = head->next;  24.	        head->next = p;  25.	          26.	    }  27.	  28.	    //这里填写链表排序函数，如下：29.	    //InsertionSortList();  30.	    SelectSortList();  31.	  32.	    ListNode* q = head->next;  33.	    while (q)  34.	    {  35.	        cout << q->val << ' ';  36.	        q = q->next;  37.	    }  38.	  39.	    return 0;  40.	}

一、交换结点

1、直接插入排序

假设排序规则为从小到大。

左边的有序区为：head - pend的区域

右边的无序区为：p – NULL的区域

每次从head->next开始，tmp = head->next; 比较tmp->val与p->val和tmp与p的关系。

pre为tmp的前缀节点。

当tmp->val < p->val时，tmp、pre一直向后移；

当tmp->val > p->val时，将tmp与p两结点交换；

当tmp == p时，说明head – p为有序区，将pend = p。

插入排序在链表应用中交换结点。

二、交换元素

1、选择排序

假设排序规则由小到大。

将待排序列分为有序序列与无序序列。

每次在无序序列中找到最小的元素，将其与有序序列的最后一个值进行交换。

选择排序在链表应用中交换元素而不交换节点。

2、快速排序

单链表的快排序和数组的快排序基本思想相同，同样是基于划分，但是又有很大的不同：单链表不支持基于下标的访问。故算法中把待排序的链表拆分为2个子链表。

为了简单起见，选择链表的第一个节点作为基准，然后进行比较，比基准小得节点放入左面的子链表，比基准大的放入右边的子链表。在对待排序链表扫描一遍之后，左边子链表的节点值都小于基准的值，右边子链表的值都大于基准的值，然后把基准插入到链表中，并作为连接两个子链表的桥梁。然后分别对左、右两个子链表进行递归快速排序，以提高性能。

但是，由于单链表不能像数组那样随机存储，和数组的快排序相比较，还是有一些需要注意的细节：

1、支点的选取，由于不能随机访问第K个元素，因此每次选择支点时可以取待排序那部分链表的头指针；

2、遍历量表方式，由于不能从单链表的末尾向前遍历，因此使用两个指针分别向前向后遍历的策略失效。

事实上，可以采用一趟遍历的方式将较小的元素放到单链表的左边。具体方法为：

1)定义两个指针pslow，pfast，其中pslow指向单链表的头结点，pfast指向单链表头结点的下一个结点;

2)使用pfast遍历单链表，每遇到一个比支点小的元素，就令pslow=pslow->next，然后和pslow进行数据交换。

3)、交换数据方式，直接交换链表数据指针指向的部分，不必交换链表节点本身。

链表快速排序描述来源：

转载地址：http://cvtai.baihongyu.com/

你可能感兴趣的文章