本文内容来自《Algorithms in C》一书。
一.选择排序（Selection Sort）
1.工作过程：首先，选出数组中最小的元素，将它与数组中第一个元素交换。然后，再选出余下数组元素最小的，将它与数组中第二个元素交换，以此类推，直到最后 数组中剩余最后一个未排序的元素，即完成。如图1所示：
图1.选择排序
2.CODE:
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 typedef int Item; 5 #define key(A) (A) 6 #define less(A,B) (key(A)<key(B)) 7 #define exch(A,B) {Item t=A;A=B;B=t;} 8 #define compexch(A,B) if(less(B,A)) exch(A,B) 9 void selection(char s[],int l,int r)//l为数组第一个元素，r为数组最后一个元素 10 { 11 int i,j; 12 for(i=l;i<r;i++) 13 { 14 int min=i;//min保存最小的数组元素下标 15 for(j=i;j<=r;j++) 16 if(less(s[j],s[min]))min=j; 17 exch(s[i],s[min]);//将最小元素交换到最终位置上 18 } 19 } 20 int main(void) 21 { 22 char s[]="asortingexample"; 23 printf("%s\n",s); 24 selection(s,0,strlen(s)-1); 25 printf("%s\n",s); 26 return 0; 27 }
3.缺点：对有序的文件和无序的文件排序时间基本相同。
二.插入排序（Insertion Sort）
1.工作过程：在排序过程中当前索引左边的元素都是排好序的，不过它们不是处于最终的位置上，因为之后他们还需要向右移动来为更小的元素腾出空间。当索引移动到最右边时，即完成排序。如图2所示：
图2.插入排序
2.CODE：
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 typedef int Item; 5 #define key(A) (A) 6 #define less(A,B) (key(A)<key(B)) 7 #define exch(A,B) {Item t=A;A=B;B=t;} 8 #define compexch(A,B) if(less(B,A)) exch(A,B) 9 void insertion(char s[],int l,int r) 10 { 11 int i,j; 12 for(i=r;i>l;i--)//首先遍历一遍数组，找出最小元素，交换到第一位当作观察哨。 13 compexch(s[i-1],s[i]); 14 for(i=l+2;i<=r;i++)//然后从第三个元素开始插入排序（前两个元素已经有序）。 15 { 16 char v; 17 j=i; 18 v=s[i]; 19 while(less(v,s[j-1]))//为待插入的元素找到合适的插入点，索引左边的有序元素依次右移。 20 { 21 s[j]=s[j-1]; 22 j--; 23 } 24 s[j]=v; 25 } 26 27 } 28 int main(void) 29 { 30 char s[]="asortingexample"; 31 printf("%s\n",s); 32 insertion(s,0,strlen(s)-1); 33 printf("%s\n",s); 34 return 0; 35 }
3.特点：插入排序的运行时间和带排序的文件数据的原始排列顺序密切相关，在已经排好序的文件数据中排序，插入比选择快。
原文：http://www.cnblogs.com/jhooon/p/3565652.html