设为首页收藏本站
天气与日历 切换到窄版

 找回密码
 立即注册

QQ登录

只需一步，快速开始

此广告位出租
帆帆资源网»首页 › 编程教程 › 编程教程 › 归并排序，分别用汇编语言，C语言，C++,java,python编写 ...
返回列表 发新帖
查看: 572|回复: 0

[其它教程] 归并排序，分别用汇编语言，C语言，C++,java,python编写出来

[复制链接]
帆帆资源网

3188

主题

4

回帖

3290

积分

管理员

积分
3290
发表于 2024-2-27 12:48:16 | 显示全部楼层 |阅读模式
前面学的快速排序，体现了分治的思想，但是不够典型，而归并排序则是非常典型的分治策略。归并的总体思想是先将数组分割，再分割...分割到一个元素，然后再两两归并排序，做到局部有序，不断地归并，直到数组又被全部合起来。
排序步骤大致如下：
  • 将长度为 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. }

复制代码
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. }

复制代码
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)

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




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

数组, 排序, 归并, 分割, 合并

相关帖子

扫码关注微信公众号，及时获取最新资源信息！【下载附件优惠：VIP会员5折；永久VIP免费】
回复

举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

免责声明：
1、本站提供的所有资源仅供参考学习使用，版权归原著所有，禁止下载本站资源参与商业和非法行为，请在24小时之内自行删除！
2、本站所有内容均由互联网收集整理、网友上传，并且以计算机技术研究交流为目的，仅供大家参考、学习，请勿任何商业目的与商业用途。
3、若您需要商业运营或用于其他商业活动，请您购买正版授权并合法使用。
4、论坛的所有内容都不保证其准确性，完整性，有效性，由于源码具有复制性，一经售出，概不退换。阅读本站内容因误导等因素而造成的损失本站不承担连带责任。
5、用户使用本网站必须遵守适用的法律法规,对于用户违法使用本站非法运营而引起的一切责任，由用户自行承担
6、本站所有资源来自互联网转载，版权归原著所有，用户访问和使用本站的条件是必须接受本站“免责声明”，如果不遵守，请勿访问或使用本网站
7、本站使用者因为违反本声明的规定而触犯中华人民共和国法律的，一切后果自己负责，本站不承担任何责任。
8、凡以任何方式登陆本网站或直接、间接使用本网站资料者，视为自愿接受本网站声明的约束。
9、本站以《2013 中华人民共和国计算机软件保护条例》第二章 “软件著作权” 第十七条为原则：为了学习和研究软件内含的设计思想和原理，通过安装、显示、传输或者存储软件等方式使用软件的，可以不经软件著作权人许可，不向其支付报酬。若有学员需要商用本站资源，请务必联系版权方购买正版授权！
10、本网站如无意中侵犯了某个企业或个人的知识产权，请来信【站长信箱312337667@qq.com】告之，本站将立即删除。
郑重声明：
本站所有资源仅供用户本地电脑学习源代码的内含设计思想和原理，禁止任何其他用途！
本站所有资源、教程来自互联网转载，仅供学习交流，不得商业运营资源，不确保资源完整性，图片和资源仅供参考，不提供任何技术服务。
本站资源仅供本地编辑研究学习参考，禁止未经资源商正版授权参与任何商业行为，违法行为！如需商业请购买各资源商正版授权
本站仅收集资源，提供用户自学研究使用，本站不存在私自接受协助用户架设游戏或资源，非法运营资源行为。
快速回复 返回顶部 返回列表