排序
1. 外部排序
2. 内部排序
插入排序（直接插入排序；折半插入排序；希尔排序）交换排序（冒泡排序、快速排序、双向冒泡排序）选择排序（简单选择排序、堆排序）归并排序基数排序
插入排序
直接插入排序：
#include<stdio.h>
#define N 10
void InsertSort(int r[],int n){
int i,j,temp;
for(i=1;i<n;++i){
temp=r[i];
j=i-1;
while(j>=0&&temp<r[j]){
r[j+1]=r[j];
--j;
}
r[j+1]=temp;
}
}
int main(){
int m = 0;
int b[N] = {5,6,2,4,9,3,1,0,8,44};
printf("=============================\n\n");
printf("排序前的数据是:\n");
for(int i=0;i<N;++i)
printf(" %d ", b[i]);
InsertSort(b, N);
printf("\n排序后的结果是:\n");
for(m = 0; m < N; m++)
{
printf(" %d ", b[m]);
}
printf("\n\n=============================\n\n");
return 0;
}
性能分析： 最坏的情況：整个序列逆序，基本操作次数n(n-1)/2，时间复杂度为O(n^2)。 最好的情况，整个序列已经有序，时间复杂度为n。 是稳定的排序方法
折半插入排序：
#include<stdio.h>
#define N 10
void InsertSort(int r[],int n){
int i,j,low,high,mid,temp;
for(i=1;i<n;++i){
temp=r[i];
//查找范围
low=0;high=i-1;
while(low<=high){
mid=(low+high)/2;
if(r[mid]>temp)
high=mid-1;
else
low=mid+1;
}
//此时high<low，条件用low或high+1都可以
for(j=i-1;j>=high+1;--j){
r[j+1]=r[j];
}
r[high+1]=temp;
}
}
算法分析：折半插入仅仅减少了比较次数，记录的比较次数与初始序列无关，且是一个稳定的排序算法。 时间复杂度最好的情况为O(nlog(2)n)，最差的情况为O(n^2) 。平均情况为O(n^2)。
交换排序
冒泡排序
void BubbleSort(int r[],int n)
{
int flag;
int temp;
for(int i=0; i<n-1; ++i)
{
flag=0;
for(int j=n-1; j>i; --j)
{
if(r[j-1]>r[j])
{
temp=r[j];
r[j]=r[j-1];
r[j-1]=temp;
flag=1;
}
}
if(flag==0)
return ;
}
}
算法性能分析： 最坏的情况，待排序列逆序，基本操作次数n(n-1)/2，时间复杂度为O(n^2) 。最好的情况，交换不发生，时间复杂度为O(n)（外循环为1，内循环不发生）。平均时间复杂度为O(n^2)。冒泡排序是一个稳定的排序算法。
双向冒泡
//双向冒泡算法，极大的减少了循环排序的次数
void sort(int a[],int length)
{
int j;
//必须要给st和limit赋值，否则若数组一开始就有序
int limit=length;
int st=-1;
while(st<limit)
{
st++;
limit--;
int swapped=0;
//从左往右循环将最大的值放到末尾
for (j = st; j < limit; j++)
{
if (a[j]>a[j+1])
{
int T=a[j];
a[j]=a[j+1];
a[j+1]=T;
swapped=1;
}
}
if (!swapped)
{
break;//如果没有发生交换，则该序列有序，即停止循环
}
else
{
swapped=0;
//从右往左循环将最小的值放到了开头
for (j = limit-1; j>st; --j)
{
if(a[j]<a[j-1])
{
int T=a[j];
a[j]=a[j-1];
a[j-1]=T;
swapped=1;
}
}
if (!swapped)
{
break;//如果没有发生交换，则该序列有序，即停止循环
}
}
}
}
快速排序
void QuickSort(int R[],int l,int r){
int temp;
int i=l,j=r;
if(l<r){
temp=R[l];
//下面的循环及完成一次排序
while(i!=j){
//从右边开始循环
while(i<j&&R[j]>temp)
--j;
if(i<j){
R[i]=R[j];
++i;
}
while(i<j&&R[i]<temp)
++i;
if(i<j){
R[j]=R[i];
--j;
}
}
//循环结束
R[i]=temp;
//一次遍历结束，并依次对两个子表进行递归
QuickSort(R,l,i-1);
QuickSort(R,i+1,r);
}
}
算法分析： 快速排序最好的情况下时间复杂度为O(nlog(2)n),待排序列越接近无序，本算法效率就越高。最坏的情况下的时间复杂度为O(n^2)，待排序列越接近有序，本算法效率越低。平均时间复杂度为O(nlog(2)n)。就平均时间而言，快速排序是所有排序算法中最好的。快速排序的排序趟数和初始序列有关。本算法的空间复杂度为O(log(2)n)。本算法是一个不稳定的排序方法。
选择类排序
简单选择排序
void SelectSort(int R[],int n){
int i,j,min;
int temp;
for(i=0;i<n;++i){
min=i;//假设待排序的第一个值为最小值
//循环一遍查找当前最小值的索引
for(j=i+1;j<n;++j)
if(R[min]>R[j]){
min=j;
}
//到目前位置i依然是带排序列中的第一个值的索引
temp=R[i];
R[i]=R[min];
R[min]=temp;
}
}
算法分析： 循环执行次数和初始序列没有关系，基本操作执行次数为n(n-1)/2，即时间复杂度为O(n^2)。本算法是一个不稳定的排序方法。
