首页 > 代码库 > 单链表插入排序
单链表插入排序
输入：一个无序的单链表的头结点
输出：一个有序的单链表的头结点（这里假设是升序排序）
分析：
1. 插入排序的基本思想：将一个节点插入到一个有序的序列中。对于链表而言，要依次从待排序的链表中取出一个节点插入到已经排好序的链表中，也就是说，在单链表插入排序的过程中，原链表会截断成两部分，一部分是原链表中已经排好序的节点，另一部分是原链表中未排序的节点，这样就需要在排序的过程中设置一个当前节点，指向原链表未排序部分的第一个节点。
注意单链表插入排序和数组插入排序的不同：数组插入排序是从排好序的部分的最后一个节点往前找，找到第一个比它小的数，然后插到其后面；而单链表只能从前往后遍历，找到第一个比当前节点大的值结束，因此在遍历已经排好序的链表部分的时候，需要两个指针，一个指针用于往前遍历（该指针假设为遍历指针），一个指针用于记录遍历指针指向的当前节点的前一个节点（该指针假设为遍历指针），这样当遍历指针找到第一个比待插入节点的值大的节点的时候，就可以将待插入节点插入到记录指针的后面。（之所以使用两个指针，是因为单链表不能反指）
插入排序分两种情况，一种是当前节点的值比已经排好序的尾节点的值大，则直接将当前节点挂在已排序的节点即可；一种是当前节点值比已经排好序的尾节点的值小，则需将已排好序的链表部分从头到尾遍历，找到第一个比当前节点值大的节点，插入到其前面即可。因为可能待插入的节点可能在第一个节点的前面，因此另外创建一个头结点，指向已经排好序的链表的第一个节点。这样可以每次插入新的节点的时候，将上面所提到的记录节点初始化为新创建的头结点，这样便于在第一个节点前面插入新节点。
代码如下：
1 ListNode *insertionSortList(ListNode *head) { 2 if(!head||head->next==NULL) return head; 3 ListNode *pHead=new ListNode(-10000); //为了便于在头结点的前面插入节点 4 pHead->next=head; 5 ListNode *pFirst = head; //指向前面一段链表头节点 6 ListNode *pLast=head; //指向前面一段链表尾节点 7 ListNode *pNode=head->next; //记录当前节点 8 ListNode *pTemp=NULL; //遍历指针 9 10 pLast->next=NULL;11 while(pNode!=NULL)12 {13 ListNode *pInsert=pHead; //记录指针14 ListNode *pNext=pNode->next;15 if(pNode->val < pLast->val)16 {17 pTemp=pFirst;18 while(pTemp!=NULL && pNode->val>=pTemp->val)19 {20 pInsert=pTemp;21 pTemp=pTemp->next;22 }23 pInsert->next=pNode;24 pNode->next=pTemp;25 pFirst=pHead->next;26 pNode=pNext;27 }28 else29 {30 pLast->next=pNode;31 pNode->next=NULL;32 pLast=pNode;33 pNode=pNext;34 }35 }36 delete pHead;37 return pFirst;38 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。