当前位置：首页 > news >正文

实用网站模板全网推广系统

news 2025/8/9 1:22:13

实用网站模板,全网推广系统,ps怎么做网站视频特效,美国做网站工资在我们之前的算法设计课程中，我们学习了合并排序与自底向上合并排序算法，今天我们就来分析一下这个算法合并算法无论是合并排序还是自底向上合并排序，他的实现都基于一个重要的算法：合并算法（merge算法）。…

在我们之前的算法设计课程中，我们学习了合并排序与自底向上合并排序算法，今天我们就来分析一下这个算法

合并算法

无论是合并排序还是自底向上合并排序，他的实现都基于一个重要的算法：合并算法（merge算法）。Merge算法实现的功能是将两个数组合并成为一个数组，我们可以定义一个结果数组b，再分别定义两个索引p1、p2，分别指向两个数组的头，将p1、p2指向的两个数进行比较，并将较小的那一个放入数组b

Merge算法的伪码如下：

merge(p, q, r, a[]):

s←p; t←q+1; k←p
while s≤q and t≤r
if a[s] ≤ a[t] then
b[k] ← a[s]
s ←s+1
6. else
b[k]←a[t]
t←t+1
9. end if
k←k+1
11. end while
if s=q+1 then b[k…r]←a[t…r]
else b[k…r]←a[s…q]
14. end if
a[p…r]←b[p…r]

自底向上合并排序算法

自底向上合并算法顾名思义，就是从最底部开始，将数组元素两两合并，再将合并后的数组两两合并，直到重新合并成一个完整的数组。对于数组a = {9,4,5,2,1,7,4,6}的合并过程可以用如下图来表示：

自底向上合并排序算法伪码如下：

BottomSort(a[]):

t←1
while t<n
s←t; t←2s; i←0
while i+t≤n
merge(i+1, i+s, i+t, a)
i←i+t
7. end while
if i+s<n then merge(i+1, i+s, n)
9. end while

合并排序算法

合并排序算法与自底向上合并排序十分相似（废话！），只不过与自底向上合并排序不同的是，合并排序是一个自顶向下的过程。我们可以将一整个数组拆分成两个数组，将其中的一个数组再进行拆分，直到拆分成两个单个元素，再将他们合并…重复此过程直到整个数组都重新合并完毕。

对于数组a[]={9,4,5,2,1,7,4,6}的合并排序可以用如下图示表示：

其中顶端数组表示其获得的输入，底端数组表示其合并后的输出

合并排序算法伪码如下：

mergesort(low, high, a[]):

if low<high then
mid←(low + high)/2
mergesort(low, mid, a)
mergesort(mid+1, high, a)
merge(low, mid, high, a)
6. end if

两个算法的完整代码

自底向上合并排序（java）：

 1 //自底向上合并排序
 2 public class BottomUpSort {
 3     public static void main(String args[])
 4     {
 5         int a[] = {9,4,5,2,1,7,4,6};
 6         bottomUpSort(a);
 7         for(int i=0;i<a.length;i++)
 8             System.out.print(a[i] + " ");
 9         System.out.println();
10     }
11     
12     public static void bottomUpSort(int a[])
13     {
14         int i, s, t = 1;
15         while(t < a.length-1)
16         {
17             s = t;
18             t = 2*s;
19             i = 0;
20             for(;i+t < a.length;i+=t)
21                 merge(i, i+s-1, i+t-1, a);    //自底向上进行排序
22             if(i+s-1 < a.length-1)    //判断是否有落单元素
23                 merge(i, i+s-1, a.length-1, a);
24             
25         }
26     }
27     
28     public static void merge(int low, int mid, int high, int a[])
29     {
30         int b[] = new int[a.length];    //    建立转存数组
31         int f = low, s = mid+1, p = low;
32         //f为第一个数组索引，s为第二个数组索引，p为b数组索引
33         while(f<=mid && s<=high)
34         {
35             //在两个数组元素中值小的一方放入b数组
36             if(a[f] <= a[s])
37             {
38                 b[p] = a[f];
39                 f++;
40             }
41             else
42             {
43                 b[p] = a[s];
44                 s++;
45             }
46             p++;
47         }
48         
49         if(f == mid+1)    //若第一个数组中的元素全部存储进去了，那么将第二个数组中的剩余元素全部放入b数组
50             for(;s <= high && p<=high;p++,s++)
51                 b[p] = a[s];
52         else //否则将第一个数组中的元素全部放入b数组
53             for(;f<=mid && p<=high;p++,f++)    
54                 b[p] = a[f];
55         
56         for(int i=low;i<=high;i++)
57             a[i] = b[i];
58     }
59 }

自底向上合并排序（c）：

 1 #include<stdio.h>
 2 
 3 //数组合并函数
 4 void merge(int low, int mid, int high, int a[])
 5 {
 6     int b[50];    //定义转存数组
 7     int f = low, s = mid + 1, p = low;
 8     //f表示第一个数组的索引，s表示第二个数组的索引，p表示b数组的索引
 9 
10     while (f <= mid && s <= high)
11     {
12         //将两个数组中值小的一方存入数组b
13         if (a[f] <= a[s])
14         {
15             b[p] = a[f];
16             f++;
17         }
18         else
19         {
20             b[p] = a[s];
21             s++;
22         }
23         p++;
24     }
25     if (f == mid + 1)    //若第一个数组都存进了数组b，那么将第二个数组中的剩下元素全部存入
26         for (; s <= high; p++, s++)
27             b[p] = a[s];
28     else    //否则将第一个数组中的剩下元素全部存入
29         for (; f <= mid; p++, f++)
30             b[p] = a[f];
31 
32     for (int i = low; i <= high; i++)
33         a[i] = b[i];    //将合并后的数组转存回a
34 }
35 
36 void BottomUpSort(int low, int high, int a[])
37 {
38     int t = 1, s, i;
39     int length = high + 1;
40     while (t < length-1)
41     {
42         s = t;
43         t = 2 * s;
44         i = 0;
45         for (; i + t <= length - 1; i+=t)    //自底向上进行合并
46             merge(i, i + s - 1, i + t - 1, a);
47         if (i + s-1 < length - 1)    //判断是否有落单元素
48             merge(i, i + s - 1, length - 1, a);
49     }
50 }
51 
52 int main()
53 {
54     int a[] = { 9,4,5,2,1,7,4,6 };
55     int length = sizeof(a) / sizeof(a[0]);
56     for (int i = 0; i < length; i++)
57         printf("%d ", a[i]);
58     printf("\n");
59     BottomUpSort(0, length - 1, a);
60     for (int i = 0; i < length; i++)
61         printf("%d ", a[i]);
62     printf("\n");
63     return 0;
64 }

合并排序（java）:

 1 //合并排序算法
 2 public class MergeSort {
 3     public static void main(String args[])
 4     {
 5         int a[] = {9,4,5,2,1,7,4,6};
 6         mergeSort(0, a.length-1, a);
 7         for(int i=0;i<a.length;i++)
 8             System.out.print(a[i] + " ");
 9         System.out.println();
10     }
11     
12     //合并排序
13     public static void mergeSort(int low, int high, int a[])
14     {
15         if(low < high)
16         {
17             int mid = (low + high)/2;
18             mergeSort(low, mid, a);
19             mergeSort(mid+1, high, a);
20             merge(low, mid, high, a);
21         }
22     }
23     
24     //合并两个数组
25     public static void merge(int low, int mid, int high, int a[])
26     {
27         int b[] = new int[a.length];    //    建立转存数组
28         int f = low, s = mid+1, p = low;
29         //f为第一个数组索引，s为第二个数组索引，p为b数组索引
30         while(f<=mid && s<=high)
31         {
32             //在两个数组元素中值小的一方放入b数组
33             if(a[f] <= a[s])
34             {
35                 b[p] = a[f];
36                 f++;
37             }
38             else
39             {
40                 b[p] = a[s];
41                 s++;
42             }
43             p++;
44         }
45         
46         if(f == mid+1)    //若第一个数组中的元素全部存储进去了，那么将第二个数组中的剩余元素全部放入b数组
47             for(;s <= high && p<=high;p++,s++)
48                 b[p] = a[s];
49         else //否则将第一个数组中的元素全部放入b数组
50             for(;f<=mid && p<=high;p++,f++)    
51                 b[p] = a[f];
52         
53         for(int i=low;i<=high;i++)
54             a[i] = b[i];
55     }
56 }

合并排序（c）:

 1 #include<stdio.h>
 2 
 3 //数组合并函数
 4 void merge(int low, int mid, int high, int a[])
 5 {
 6     int b[50];    //定义转存数组
 7     int f = low, s = mid + 1, p = low;
 8     //f表示第一个数组的索引，s表示第二个数组的索引，p表示b数组的索引
 9 
10     while (f <= mid && s <= high)
11     {
12         //将两个数组中值小的一方存入数组b
13         if (a[f] <= a[s])
14         {
15             b[p] = a[f];
16             f++;
17         }
18         else
19         {
20             b[p] = a[s];
21             s++;
22         }
23         p++;
24     }
25     if (f == mid+1)    //若第一个数组都存进了数组b，那么将第二个数组中的剩下元素全部存入
26         for (; s <= high; p++, s++)
27             b[p] = a[s];
28     else    //否则将第一个数组中的剩下元素全部存入
29         for (; f <= mid; p++, f++)
30             b[p] = a[f];
31 
32     for (int i = low; i <= high; i++)
33         a[i] = b[i];    //将合并后的数组转存回a
34 }
35 
36 //合并排序函数
37 void MergeSort(int low, int high, int a[])
38 {
39     if (low < high)
40     {
41         int mid = (low + high) / 2;
42         MergeSort(low, mid, a);    
43         MergeSort(mid + 1, high, a);    //从上到下合并数组
44         merge(low, mid, high, a);
45     }
46 }
47 
48 int main()
49 {
50     int a[] = { 9,4,5,2,1,7,4,6 };
51     int length = sizeof(a) / sizeof(a[0]);
52     for (int i = 0; i < length; i++)
53         printf("%d ", a[i]);
54     printf("\n");
55     MergeSort(0, length - 1, a);
56     for (int i = 0; i < length; i++)
57         printf("%d ", a[i]);
58     printf("\n");
59     return 0;
60 }