C語言算法--插入排序

C語言算法--插入排序

1. /*----------------------------- 
2. * 
3. * For    排序算法學習 
4. * IDE    DEV-CPP4.9.2 
5. * Auhtor  Czp 
6. * Date   2012/10/17 
7. *------------------------------ 
8. */ 
9. #include <stdlib.h>  
10. #include <stdio.h>  
11. //插入排序  
12. void insertSort(int* arr,size_t n)       
13. { 
14.        
15.       int i,j,key; 
16.       for(i=1;i<n;i++)                      //初始:ar={169,45,2,489,469,4,-778,156}  
17.       {                                     
18.           key = arr[i];                   
19.           j=i-1; 
20.           while(j>=0&&arr[j]>key)          //把key與前面的arr[0~j]進行比較   
21.                   arr[j+1] = arr[j--];     //找到一個比key大的數就把它後移   
22.           arr[j+1]=key;                    //上面的循環終止，則j+1就key的位置   
23.       }   
24.       /* 
25.       *Loop0:169,45,2,489,469,4,-778,156  數組原型  取key=arr[2]=2  
26.       *Loop1:2,169,45,489,469,4,-778,156  key=2比arr[1] arr[0]小，找到arr[2]的位置arr[0]-> 
27.       *Lopp3:2,169,45,469,489,4,-778,156  進行插入和ArrayList的insert(value,index)一樣  
28.       *Loop4:2,169,45,469,489,4,-778,156  ....... 
29.       *Loop5:2,4,169,45,469,489,-778,156  ... 
30.       *Loop6:-778,2,4,169,45,469,489,156  ... 
31.       *Loop7:-778,2,4,156,169,45,469,489  ... 
32.       */ 
33. }   
34.  
35.  int main(int argc, char *argv[]) 
36.  { 
37.      int arr[] = {169,45,2,489,469,4,-778,156}; 
38.      size_t len = (sizeof arr/sizeof arr[0]); 
39.      insertSort(arr,len); 
40.      int i; 
41.      for(i=0;i<len;i++) 
42.      { 
43.          printf("%d ,",arr[i]);                 
44.      } 
45.      //====>-778,2,4,156,169,45,469,489  
46.      getchar(); 
47.      return 0; 
48.  }