Java基础算法--排序

一、插入排序

　　数组：　　

 1 void insertionSort(int[] a){
 2     int j;
 3     for(int p = 1;p<a.length;p++){
 4         int tmp = a[p];
 5         for(j=p;j>0;j--){
 6             if(tmp<a[j-1]){
 7                 a[j] = a[j-1];
 8             }else{
 9                 a[i] = tmp;
10             }
11         }    
12     }
13 }

　　若是Java泛型掌握的好，可以这样书写

1 void insertionSort(AnyType[] a){
2     int j;
3     for(int p = 1;p < a.length;p++){
4         AnyType tmp = a[p];
5         for(j=p;j>0&&tmp.compareTo(a[j-1])<0;j--)            
6             a[j] = a[j-1];    
7         a[i] = tmp;    
8     }    
9 }

　　链表：

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         ListNode dummy = new ListNode(-1);
 4         dummy.next = head;
 5         head = dummy;
 6         ListNode p = dummy.next;
 7         ListNode s;
 8         
 9         while(p!=null){
10             if(p.next==null)  break;
11             while(head!=p&&p.next.val>head.next.val){
12                 head=head.next;
13             }
14             if(head==p)
15                 p=p.next;
16             else{
17                 s = p.next;
18                 p.next = p.next.next;
19                 s.next = null;
20                 
21                 ListNode tmp = head.next;
22                 head.next = s;
23                 s.next = tmp;
24             }
25             head=dummy;
26         }
27         return dummy.next;
28     }
29 }

另一种于九章算法上的做法：

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         ListNode dummy = new ListNode(0);
 4 
 5         while (head != null) {
 6             ListNode node = dummy;
 7             while (node.next != null && node.next.val < head.val) {
 8                 node = node.next;
 9             }
10             ListNode temp = head.next;
11             head.next = node.next;
12             node.next = head;
13             head = temp;
14         }
15 
16         return dummy.next;
17     }
18 }