说明
之前所介绍的排序法都是在同一个阵列中的排序,考虑今日有两笔或两笔以上的资料,
它可能是不同阵列中的资料,或是不同档案中的资料,如何为它们进行排序?
解法
可以使用合并排序法,合并排序法基本是将两笔已排序的资料合并并进行排序,如果所读入的资料
尚未排序,可以先利用其它的排序方式来处理这两笔资料,然后再将排序好的这两笔资料合并。
如果两笔资料本身就无排序顺序,何不将所有的资料读入,再一次进行排序?排序的精神是尽量利用资
料已排序的部份,来加快排序的效率,小笔资料的排序较为快速,如果小笔资料排序完成之后,再合并
处理时,因为两笔资料都有排序了,所有在合并排序时会比单纯读入所有的资料再一次排序来的有效率。
那么可不可以直接使用合并排序法本身来处理整个排序的动作?而不动用到其它的排序方式?
答案是肯定的,只要将所有的数字不断的分为两个等分,直到最后剩一个数字为止,然后再反
过来不断的合并,就如下图所示:
73 2 86 22 17 75 7 48
[2,73] [22,86] [17,75] [7,48]
22,2,73,86 7,17,48,75
2,7,17,22,48,73,75,86
当然对一个阵列可以可以采用其它较更有效的排序方式,然后再对排好序的多阵列合并排序
#include <stdio.h>
#include <stdlib.h>
#define MAX1 10
#define MAX2 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
int partition(int[], int, int);
void quicksort(int[], int, int);
void mergesort(int[], int, int[], int, int[]);
int main(void)
{
int number1[MAX1] = {73,52,86,22,47,75,7,48,87,60};
int number2[MAX1] = {40,7,36,35,13,39,16,48,79,15};
int number3[MAX1+MAX2] = {0};
int i, num;
srand(time(NULL));
printf("排序前:");
printf("\nnumber1[]:");
for(i = 0; i < MAX1; i++)
{
printf("%d ", number1[i]);
}
printf("\nnumber2[]:");
for(i = 0; i < MAX2; i++)
{
printf("%d ", number2[i]);
}
// 先排序两笔资料
quicksort(number1, 0, MAX1-1);
quicksort(number2, 0, MAX2-1);
printf("\n排序后:");
printf("\nnumber1[]:");
for(i = 0; i < MAX1; i++)
printf("%d ", number1[i]);
printf("\nnumber2[]:");
for(i = 0; i < MAX2; i++)
printf("%d ", number2[i]);
// 合并排序
mergesort(number1, MAX1, number2, MAX2, number3);
printf("\n合并后:");
for(i = 0; i < MAX1+MAX2; i++)
printf("%d ", number3[i]);
printf("\n");
return 0;
}
int partition(int number[], int left, int right)
{
int i, j, s;
s = number[right];
i = left - 1;
for(j = left; j < right; j++)
{
if(number[j] <= s)
{
i++;
SWAP(number[i], number[j]);
}
}
SWAP(number[i+1], number[right]);
return i+1;
}
void quicksort(int number[], int left, int right)
{
int q;
if(left < right)
{
q = partition(number, left, right);
quicksort(number, left, q-1);
quicksort(number, q+1, right);
}
}
void mergesort(int number1[], int M, int number2[], int N, int number3[])
{
int i = 0, j = 0, k = 0;
while(i < M && j < N)
{
if(number1[i] <= number2[j])
number3[k++] = number1[i++];
else
number3[k++] = number2[j++];
}
while(i < M)
number3[k++] = number1[i++];
while(j < N)
number3[k++] = number2[j++];
}
//测试结果
分享到:
相关推荐
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
自然合并排序是对合并排序的非递归形式的一种改进,很好很有用
/************合并排序算法的实现******************/ int main() { int p,q,r; printf("合并排序算法的实现:\n"); printf("请输入p、q、r的值(输入格式1,12,13):"); scanf("%d,%d,%d",&p,&q,&r); printf("p=%...
c++实现的合并排序算法 用递归和非递归两种方式实现的
这是用c++编写的一个合并排序的程序……
这些代码是对算法导论上对排序部分的总结,实现了以下排序方法:插入排序,合并排序,堆排序,快速排序,计数排序,每种实现都有详细的注释和相应的测试程序,可查找http://blog.csdn.net/china8848<br>中对相关问题...
针对200000长度的数组,采用插入排序和合并排序,对比两种算法的时间复杂度
这是我写的一个合并排序 用c语言实现 的,
C语言实现的排序算法,包括快排和合并排序,测试通过
经典排序算法的合并排序算法的C语言实现,适合初学者
c++ 分治法合并排序 merge sort c语言 分治法合并排序 merge sort(将cout修改printf 加头文件include "stdio.h")
通过动态规划来实现快速排序和合并排序!使我们更能很好的应用于实际中!!
实现并验证合并排序算法; 实现并验证快速排序算法(参考习题5.2第7a题,P140); 用递归与分治的方法设计并实现寻找第k小元素算法
分治策略 合并排序 快速排序 代码 C语言 是自己写的程序,还请各位指教
C#写的合并排序
利用分治法的合并排序实现数组的排序,根据算法导论第二章编写
java语言实现合并排序
合并排序的递归调用和合并排序的非递归调用的对比,可以让人感受到选择递归调用可以提高工作作业效率,只要得到递归公式和递归出口就可以了,问题解决起来会很省力
自底向上合并排序算法 ,望对大家有帮助,谢谢!