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. {
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. }
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. }