合并排序是利用了分治思想的排序方式，具有O(NlogN)的時(shí)間復(fù)雜度，與快速排序、堆排序相比，它需要N的輔助空間。它的核心部分是將兩個(gè)有序序列合并（由Merge()函數(shù)實(shí)現(xiàn)）。
合并排序的基本思想是：單個(gè)元素是有序的，兩個(gè)較小的有序序列可被合并為一個(gè)較大的有序序列。
算法描述如下：
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];
}，時(shí)間復(fù)雜度O(N^2)，基本操作是將一個(gè)元素插入到有序序列中。當(dāng)待排序元素個(gè)數(shù)為n時(shí)，因?yàn)榈谝粋€(gè)元素是有序的，因此只需經(jīng)過n - 1次插入，就能完成排序。
單次插入的過程為：
1.找到要插入元素在已排序部分中的位置j。
2.將有序序列中j后面的所有元素向后移動(dòng)一位，為待插入元素空出位置。
3.將待排序元素插入j位置，保持序列有序。
算法描述為：
void InsertSort(int *a, int n)
{//數(shù)組下標(biāo)從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--)//向后移動(dòng)元素
a[k] = a[k - 1];
a[j] = t;//插入
}
}posted on 2012-07-18 11:12
小鼠標(biāo) 閱讀(926)
評論(0) 編輯 收藏 引用 所屬分類:
排序