本文介绍几种常用的排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序。
冒泡排序
冒泡排序（Bubble Sort）：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
实例：
#include void bubble_sort(int [],int);int main(){int i;int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70}; int len=(int)sizeof(arr)/sizeof(*arr); bubble_sort(arr,len); for(i=0;i<len;i++) printf("%d ",arr[i]); return 0;}void bubble_sort(int arr[],int len){ int i,j,temp; for(i=0;i<len-1;i++) for(j=0;jarr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; }}运行结果：
3 5 9 22 32 34 35 37 50 55 64 70 82 89选择排序
选择排序（Selection Sort）：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
实例：
#include void selection_sort(int [],int);int main(){int i;int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70}; int len=(int)sizeof(arr)/sizeof(*arr); selection_sort(arr,len); for(i=0;i<len;i++) printf("%d ",arr[i]); return 0;}void selection_sort(int a[],int len) { int i,j,temp; for(i=0;i<len-1;i++) { int min=i; // 记录最小值，第一个元素默认最小 for(j=i+1;j<len;j++)// 访问未排序的元素 { if(a[j]<a[min])// 找到目前最小值 min=j;// 记录最小值 } if(min!=i) { temp=a[min];// 交换两个变量 a[min]=a[i]; a[i]=temp; } }}运行结果：
3 5 9 22 32 34 35 37 50 55 64 70 82 89插入排序
插入排序（英语：Insertion Sort）：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
实例：
#include void insertion_sort(int [],int);int main(){int i;int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70}; int len=(int)sizeof(arr)/sizeof(*arr); insertion_sort(arr,len); for(i=0;i<len;i++) printf("%d ",arr[i]); return 0;}void insertion_sort(int arr[],int len){ int i,j,temp; for(i=1;i0&&arr[j-1]>temp;j--) arr[j]=arr[j-1]; arr[j]=temp; }}运行结果：
3 5 9 22 32 34 35 37 50 55 64 70 82 89希尔排序
希尔排序（Shell Sort）：也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
实例
#include void shell_sort(int [],int);int main(){int i;int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70}; int len=(int)sizeof(arr)/sizeof(*arr); shell_sort(arr,len); for(i=0;i>1;gap>0;gap=gap>>1) for(i=gap;i=0&&arr[j]>temp;j-=gap) arr[j+gap]=arr[j]; arr[j+gap]=temp; }}运行结果：
3 5 9 22 32 34 35 37 50 55 64 70 82 89归并排序
归并排序（Merge Sort）：把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。
可从上到下或从下到上进行。
实例迭代法
#include #include int mini(int,int);void merge_sort(int [],int);int main(){int i;int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70}; int len=(int)sizeof(arr)/sizeof(*arr); merge_sort(arr,len); for(i=0;i<len;i++) printf("%d ",arr[i]); return 0;}int mini(int x,int y) { return x<y?x:y;}void merge_sort(int arr[],int len){ int *a=arr; int *b=(int*)malloc(len*sizeof(int));int *temp,seg,start; for(seg=1;seg<len;seg+=seg){ for(start=0;start<len;start+=seg+seg){ int low=start;int mid=mini(start+seg,len);int high=mini(start+seg+seg,len); int k=low; int start1=low;int end1=mid; int start2=mid;int end2=high; while(start1<end1&&start2<end2) b[k++]=a[start1]<a[start2]?a[start1++]:a[start2++]; while(start1<end1) b[k++]=a[start1++]; while(start2<end2) b[k++]=a[start2++]; } temp=a; a=b; b=temp; } if(a!=arr){ int i; for(i=0;i<len;i++) b[i]=a[i]; b=a; } free(b);}递归法
#include #include #define N 14void merge_sort_recursive(int [],int [],int,int);void merge_sort(int [],const int);int main(){int i;int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70}; int len=(int)sizeof(arr)/sizeof(*arr); merge_sort(arr,len); for(i=0;i=end) return; len=end-start;mid=(len>>1)+start; start1=start;end1=mid; start2=mid+1;end2=end; merge_sort_recursive(arr,reg,start1,end1); merge_sort_recursive(arr,reg,start2,end2); k=start; while(start1<=end1&&start2<=end2) reg[k++]=arr[start1]<arr[start2]?arr[start1++]:arr[start2++]; while(start1<=end1) reg[k++]=arr[start1++]; while(start2<=end2) reg[k++]=arr[start2++]; for(k=start;k<=end;k++) arr[k]=reg[k];}void merge_sort(int arr[], const int len){ int reg[N]; merge_sort_recursive(arr,reg,0,len-1);}运行结果：
3 5 9 22 32 34 35 37 50 55 64 70 82 89备注：常用排序算法的时间复杂度和空间复杂度
