本文介绍几种常用的排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序。
冒泡排序
冒泡排序（Bubble Sort）：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
实例：
#include <stdio.h>
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;j<len-1-i;j++)
if(arr[j]>arr[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 <stdio.h>
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 <stdio.h>
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;i<len;i++)
{
temp=arr[i];
for(j=i;j>0&&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 <stdio.h>
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<len;i++)
printf("%d ",arr[i]);
return 0;
}
void shell_sort(int arr[],int len)
{
int gap,i,j;
int temp;
for(gap=len>>1;gap>0;gap=gap>>1)
for(i=gap;i<len;i++)
{
temp=arr[i];
for(j=i-gap;j>=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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
#define N 14
void 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<len;i++)
printf("%d ",arr[i]);
return 0;
}
void merge_sort_recursive(int arr[],int reg[],int start,int end)
{
int k,len,mid,start1,start2,end1,end2;
if(start>=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
备注：常用排序算法的时间复杂度和空间复杂度
