合并排序是利用了分治思想的排序方式,具有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
小鼠标 阅读(901)
评论(0) 编辑 收藏 引用 所属分类:
排序