首页 > 代码库 > Insertion Sort List (8)
Insertion Sort List (8)
Sort a linked list using insertion sort.
首先总结一下插入排序和冒泡排序吧！
插入排序：
1 void inssort(int a[],int n){2 int i,j;3 for(i=1;i<n;i++){4 for(j=i;j>0&&(a[j]<a[j-1]);j--)//后面的比前面小，交换5 //这里还有j>0很容易出错，如果j=0的话，a[-1]没有意义6 swap(a[j],a[j-1]);7 }8 }
冒泡排序:
void bubsort(int a[],int n){ int i,j; for(i=0;i<n-1;i++){ for(j=n-1;j>i;j--)//从后往前，直至j=i if(a[j]<a[j-1]) swap(a[j],a[j-1]); }}
对于链表来说，怎么利用插入排序的思路来完成这个链表的排序呢？
我们可以重新建立一个链表来存放重新排序后的链表，这样就只需从前往后依次遍历链表中的每个元素，然后将其插入到新链表中的正确位置就行了。
下面贴出代码，仍然有一些问题需要注意，详情请看注释。
class Solution {public://十分巧妙的代码 ListNode *insertionSortList(ListNode *head) {//利用了插入排序的巧妙方法！只要采取重新建立链表，把数插入正确的位置的策略，这样就简单多了，实现起来很容易！ if(!head||!head->next) return head; ListNode *temp=new ListNode (-9999); ListNode *ptr; ptr=head; ListNode * pre; while(ptr){ ListNode *next=ptr->next; pre=temp; while(pre->next&&pre->next->val<ptr->val) pre=pre->next; ptr->next=pre->next;pre->next=ptr;/*这两句不能内嵌入循环，因为刚开始的时候要将链表汇总的第一项加入temp的后面，如果嵌入循环的话就会超时!*/ ptr=next; } head=temp->next; delete temp; return head; }};
Insertion Sort List (8)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。