当前位置:   article > 正文

算法实验室-15-插入排序_实验十五 插入排序与选择排序

实验十五 插入排序与选择排序

理解插入排序

什么是插入排序?这个问题得问链表,链表本身是拥有一个方法,叫insert(ListNode node)的函数

实现这个函数其实还是很简单的

  1. //插入函数
  2. public void insert(ListNode parent,ListNode value){
  3. ListNode temp = parent.next;
  4. parent.next = value;
  5. value.next = temp;
  6. }

那么,拥有这个插入函树了我是不是就能做一些事情,比如一个一个的插?或者有条件的插?

比如,我希望插入的这个节点一定是这个链表的最小值?

  1. //插入函数
  2. public void insertToMinPos(ListNode head,ListNode value){
  3. ListNode cur = head;
  4. while (cur.next!= null&&cur.val<value.val){
  5. cur = cur.next;
  6. }
  7. insert(cur,value);
  8. }

那么插入排序就变得非常简单了,就相当于从一个链表往一个新链表里面疯狂的插入最小值

当然,还是有一些地方需要去注意的:

代码: 

  1. public class InsertRank {
  2. public ListNode insertRank(ListNode node){
  3. ListNode cur = node;
  4. ListNode newList = new ListNode();
  5. while (cur!= null){
  6. ListNode cache = cur.next;
  7. //向新链表的最小一位插
  8. insertToMinPos(newList,cur);
  9. cur = cache;
  10. }
  11. return newList.next;
  12. }
  13. //插入函数
  14. public void insert(ListNode parent,ListNode value){
  15. ListNode temp = parent.next;
  16. parent.next = value;
  17. value.next = temp;
  18. }
  19. //插入函数
  20. public void insertToMinPos(ListNode head,ListNode value){
  21. ListNode cur = head;
  22. while (cur.next!= null&&cur.next.val<value.val){
  23. cur = cur.next;
  24. }
  25. insert(cur,value);
  26. }
  27. }

本题链接:

 

 

 

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号