归并排序，分别用汇编语言，C语言，C++,java,python编写出来

帆帆资源网

前面学的快速排序，体现了分治的思想，但是不够典型，而归并排序则是非常典型的分治策略。归并的总体思想是先将数组分割，再分割...分割到一个元素，然后再两两归并排序，做到局部有序，不断地归并，直到数组又被全部合起来。

排序步骤大致如下：

• 将长度为 n 的数组分割成为 n/2 的两个子数组。
• 子数组也不断分割成为更小的子数组，直到不能分割。
• 最小子数组之间开始两两合并，合并之后的结果再合并。合并的时候可以申请一个临时空间，利用两个索引指针比较的方式，将两个子数组的结果合并到临时数组中去。
• 循环 3 步骤，直到合并成为长度为 n 的已经排序的数组。
  

归并排序，分别用汇编语言，C语言，C++,java,python编写出来
当然！以下是归并排序算法的示例代码，分别使用汇编语言、C语言、C++、Java和Python编写：
1. 汇编语言（x86汇编）：

1. assembly
   
2. section .data
   
3.     array db 64, 25, 12, 22, 11
   
4.     length equ $ - array
   
5. section .text
   
6.     global _start
   
7. _start:
   
8.     mov ecx, length
   
9.     dec ecx
   
10.     mov esi, 0
    
11.     mov edi, ecx
    
12.     call merge_sort
    
13.     ; 输出排序后的数组
    
14.     mov ecx, length
    
15.     mov esi, 0
    
16. print_loop:
    
17.     movzx eax, byte [array + esi]
    
18.     add eax, '0'
    
19.     push eax
    
20.     push msg_digit
    
21.     call printf
    
22.     add esp, 8
    
23.     inc esi
    
24.     loop print_loop
    
25.     ; 退出程序
    
26.     mov eax, 1
    
27.     xor ebx, ebx
    
28.     int 0x80
    
29. section .data
    
30.     msg_digit db "%c ", 0
    
31. section .text
    
32.     extern printf, malloc, free
    
33. merge_sort:
    
34.     push ebp
    
35.     mov ebp, esp
    
36.     sub esp, 4
    
37.     mov eax, edi
    
38.     sub eax, esi
    
39.     cmp eax, 1
    
40.     jle end_merge_sort
    
41.     mov eax, edi
    
42.     add eax, esi
    
43.     shr eax, 1
    
44.     push eax
    
45.     mov eax, edi
    
46.     sub eax, esi
    
47.     push eax
    
48.     call merge_sort
    
49.     add esp, 8
    
50.     push eax
    
51.     mov eax, edi
    
52.     add eax, esi
    
53.     shr eax, 1
    
54.     push eax
    
55.     mov eax, edi
    
56.     sub eax, esi
    
57.     push eax
    
58.     call merge_sort
    
59.     add esp, 8
    
60.     push edi
    
61.     push esi
    
62.     push edi
    
63.     sub edi, esi
    
64.     push edi
    
65.     call merge
    
66.     add esp, 16
    
67.     pop ebp
    
68. end_merge_sort:
    
69.     ret
    
70. merge:
    
71.     push ebp
    
72.     mov ebp, esp
    
73.     sub esp, 8
    
74.     mov eax, [ebp + 8]
    
75.     mov ecx, [ebp + 12]
    
76.     mov edx, ecx
    
77.     sub edx, eax
    
78.     mov esi, eax
    
79.     mov edi, ecx
    
80.     lea edi, [edi + 1]
    
81.     shl edi, 2
    
82.     push edi
    
83.     call malloc
    
84.     add esp, 4
    
85.     mov ebx, eax
    
86.     mov edi, eax
    
87.     mov ecx, edx
    
88.     shl ecx, 2
    
89.     rep movsd
    
90.     mov eax, [ebp + 8]
    
91.     mov ecx, [ebp + 12]
    
92.     mov edx, [ebp + 16]
    
93.     lea esi, [eax * 4 + array]
    
94.     lea edi, [edx * 4 + array]
    
95.     mov ebx, eax
    
96.     mov ebp, ecx
    
97. merge_loop:
    
98.     cmp eax, ecx
    
99.     jge copy_remaining
    
100.     mov edx, [esi]
     
101.     cmp edx, [edi]
     
102.     jle copy_from_left
     
103.     mov edx, [edi]
     
104.     mov [esi], edx
     
105.     add edi, 4
     
106. copy_from_left:
     
107.     add esi, 4
     
108.     inc eax
     
109.     jmp merge_loop
     
110. copy_remaining:
     
111.    

复制代码

mov ecx, ebp
    sub ecx, ebx
    lea esi, [ebx * 4 + array]
    lea edi, [edx * 4 + array]
    shl ecx, 2
    rep movsd
    mov eax, ebx
    shl eax, 2
    add eax, array
    push eax
    call free
    add esp, 4
    pop ebp
    ret




2. C语言：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. void merge(int arr[], int left, int mid, int right) {
   
4.     int n1 = mid - left + 1;
   
5.     int n2 = right - mid;
   
6.      int *L = (int *)malloc(n1 * sizeof(int));
   
7.     int *R = (int *)malloc(n2 * sizeof(int));
   
8.      for (int i = 0; i < n1; i++) {
   
9.         L[i] = arr[left + i];
   
10.     }
    
11.     for (int j = 0; j < n2; j++) {
    
12.         R[j] = arr[mid + 1 + j];
    
13.     }
    
14.      int i = 0, j = 0, k = left;
    
15.     while (i < n1 && j < n2) {
    
16.         if (L[i] <= R[j]) {
    
17.             arr[k] = L[i];
    
18.             i++;
    
19.         } else {
    
20.             arr[k] = R[j];
    
21.             j++;
    
22.         }
    
23.         k++;
    
24.     }
    
25.      while (i < n1) {
    
26.         arr[k] = L[i];
    
27.         i++;
    
28.         k++;
    
29.     }
    
30.      while (j < n2) {
    
31.         arr[k] = R[j];
    
32.         j++;
    
33.         k++;
    
34.     }
    
35.      free(L);
    
36.     free(R);
    
37. }
    
38. void mergeSort(int arr[], int left, int right) {
    
39.     if (left < right) {
    
40.         int mid = left + (right - left) / 2;
    
41.          mergeSort(arr, left, mid);
    
42.         mergeSort(arr, mid + 1, right);
    
43.          merge(arr, left, mid, right);
    
44.     }
    
45. }
    
46. 
    

复制代码

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
     mergeSort(arr, 0, n - 1);
     printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr);
    }
    printf("\n");
     return 0;
}




3. C++：

1. #include <iostream>
   
2. using namespace std;
   
3. void merge(int arr[], int left, int mid, int right) {
   
4.     int n1 = mid - left + 1;
   
5.     int n2 = right - mid;
   
6.      int L[n1], R[n2];
   
7.      for (int i = 0; i < n1; i++) {
   
8.         L[i] = arr[left + i];
   
9.     }
   
10.     for (int j = 0; j < n2; j++) {
    
11.         R[j] = arr[mid + 1 + j];
    
12.     }
    
13.      int i = 0, j = 0, k = left;
    
14.     while (i < n1 && j < n2) {
    
15.         if (L[i] <= R[j]) {
    
16.             arr[k] = L[i];
    
17.             i++;
    
18.         } else {
    
19.             arr[k] = R[j];
    
20.             j++;
    
21.         }
    
22.         k++;
    
23.     }
    
24.      while (i < n1) {
    
25.         arr[k] = L[i];
    
26.         i++;
    
27.         k++;
    
28.     }
    
29.      while (j < n2) {
    
30.         arr[k] = R[j];
    
31.         j++;
    
32.         k++;
    
33.     }
    
34. }
    
35. void mergeSort(int arr[], int left, int right) {
    
36.     if (left < right) {
    
37.         int mid = left + (right - left) / 2;
    
38.          mergeSort(arr, left, mid);
    
39.         mergeSort(arr, mid + 1, right);
    
40.          merge(arr, left, mid, right);
    
41.     }
    
42. }
    
43. 
    

复制代码

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
     mergeSort(arr, 0, n - 1);
     cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr << " ";
    }
    cout << endl;
     return 0;
}




4. Java：

1. public class MergeSort {
   
2.     public static void merge(int[] arr, int left, int mid, int right) {
   
3.         int n1 = mid - left + 1;
   
4.         int n2 = right - mid;
   
5.          int[] L = new int[n1];
   
6.         int[] R = new int[n2];
   
7.          for (int i = 0; i < n1; i++) {
   
8.             L[i] = arr[left + i];
   
9.         }
   
10.         for (int j = 0; j < n2; j++) {
    
11.             R[j] = arr[mid + 1 + j];
    
12.         }
    
13.          int i = 0, j = 0, k = left;
    
14.         while (i < n1 && j < n2) {
    
15.             if (L[i] <= R[j]) {
    
16.                 arr[k] = L[i];
    
17.                 i++;
    
18.             } else {
    
19.                 arr[k] = R[j];
    
20.                 j++;
    
21.             }
    
22.             k++;
    
23.         }
    
24.          while (i < n1) {
    
25.             arr[k] = L[i];
    
26.             i++;
    
27.             k++;
    
28.         }
    
29.          while (j < n2) {
    
30.             arr[k] = R[j];
    
31.             j++;
    
32.             k++;
    
33.         }
    
34.     }
    
35.      public static void mergeSort(int[] arr, int left, int right) {
    
36.         if (left < right) {
    
37.             int mid = (left + right) / 2;
    
38.             mergeSort(arr, left, mid);
    
39.             mergeSort(arr, mid + 1, right);
    
40.             merge(arr, left, mid, right);
    
41.         }
    
42.     }
    
43.      
    
44. }

复制代码

public static void main(String[] args) {
        int[] arr = { 64, 25, 12, 22, 11 };
         mergeSort(arr, 0, arr.length - 1);
         System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }




5.Python代码示例：

1. def merge(arr, left, mid, right):
   
2.     n1 = mid - left + 1
   
3.     n2 = right - mid
   
4.      L = arr[left:mid+1]
   
5.     R = arr[mid+1:right+1]
   
6.      i = j = 0
   
7.     k = left
   
8.      while i < n1 and j < n2:
   
9.         if L[i] <= R[j]:
   
10.             arr[k] = L[i]
    
11.             i += 1
    
12.         else:
    
13.             arr[k] = R[j]
    
14.             j += 1
    
15.         k += 1
    
16.      while i < n1:
    
17.         arr[k] = L[i]
    
18.         i += 1
    
19.         k += 1
    
20.      while j < n2:
    
21.         arr[k] = R[j]
    
22.         j += 1
    
23.         k += 1
    
24. def mergeSort(arr, left, right):
    
25.     if left < right:
    
26.         mid = (left + right) // 2
    
27.         mergeSort(arr, left, mid)
    
28.         mergeSort(arr, mid + 1, right)
    
29.         merge(arr, left, mid, right)
    
30. 
    

复制代码

arr = [64, 25, 12, 22, 11]
mergeSort(arr, 0, len(arr) - 1)
print("Sorted array:")
print(arr)




这些代码示例演示了如何编写归并排序算法。您可以根据需要运行这些代码，并查看排序后的结果。