合并排序是利用了分治思想的排序方式，具有O(NlogN)的时间复杂度，与快速排序、堆排序相比，它需要N的辅助空间。它的核心部分是将两个有序序列合并（由Merge()函数实现）。
合并排序的基本思想是：单个元素是有序的，两个较小的有序序列可被合并为一个较大的有序序列。
算法描述如下：
void MergeSort(int *a, int f, int r)
{
if(f < r)
{
int i = (r + f) / 2;
MergeSort(a, f, i);//排序左半部分
MergeSort(a, i + 1, r);//排序右半部分
Merge(a, f, i, r);//合并
}
}
void Merge(int *a, int f, int m, int r)
{
int *b = (int *)malloc(sizeof(int) * ( r - f + 1));
int i = f;
int j = m + 1;
int k = 0;
while(i <= m && j <= r)
{
if(a[i] > a[j])
b[k++] = a[j++];
else
b[k++] = a[i++];
}
while(i <= m)
b[k++] = a[i++];
while(j <= r)
b[k++] = a[j++];
Copy(a, b, f, r);
free(b);
}
void Copy(int *a, int *b, int f, int r)
{
for(int i = 0; i <= r - f; i++)
a[i + f] = b[i];
}，时间复杂度O(N^2)，基本操作是将一个元素插入到有序序列中。当待排序元素个数为n时，因为第一个元素是有序的，因此只需经过n - 1次插入，就能完成排序。
单次插入的过程为：
1.找到要插入元素在已排序部分中的位置j。
2.将有序序列中j后面的所有元素向后移动一位，为待插入元素空出位置。
3.将待排序元素插入j位置，保持序列有序。
算法描述为：
void InsertSort(int *a, int n)
{//数组下标从0开始，0号元素是有序的
int i, j, k;
for(i = 1; i < n; i++)
{
j = -1;
int t = a[i];
while(a[++j] < t);//找到要插入的位置
for(k = i; k > j; k--)//向后移动元素
a[k] = a[k - 1];
a[j] = t;//插入
}
}posted on 2012-07-18 11:12
小鼠标 阅读(895)
评论(0) 编辑 收藏 引用 所属分类:
排序