找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 1586|回复: 0
打印 上一主题 下一主题
收起左侧

C语言分治排序算法

[复制链接]
跳转到指定楼层
楼主
ID:280163 发表于 2018-1-27 11:58 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
分治排序算法
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<math.h>

  4. /*将A数组中p到r元素进行分治排序*/
  5. MERGE(int *A, int p, int q, int r)
  6. {
  7.         int n1 = q - p + 1;//数组L中元素个数
  8.         int n2 = r - q;//数组R中元素个数
  9.         int *L, *R;
  10.         int i;
  11.         int j;
  12.         int k;
  13.         L = malloc( ( n1 + 1 ) * sizeof( int ) );
  14.         R = malloc( ( n2 + 1 ) * sizeof( int ) );

  15.         for( i = 0; i < n1; i++ )
  16.         {
  17.                 *( L + i ) = *( A + p + i );//A[p]到A[q]
  18.         }

  19.         for( i = 0; i < n2; i++ )
  20.         {
  21.                 *( R + i ) = *( A + q + i + 1 );//A[q+1]到A[r]
  22.         }

  23.         L[n1] = 2147483647;//2^31-1
  24.         R[n2] = 2147483647;//2^31-1

  25.         i=0;
  26.         j=0;

  27.         for( k = p; k <= r; k++ )
  28.         {
  29.                 if( L[i] <= R[j] )
  30.                 {
  31.                         A[k] = L[i];
  32.                         i = i + 1;
  33.                 }
  34.                 else
  35.                 {
  36.                         A[k] = R[j];
  37.                         j = j + 1;
  38.                 }
  39.         }

  40.         free( L );
  41.         free( R );
  42. }

  43. MERGE_SORT( int *A, int p, int r )
  44. {
  45.         int q;
  46.         if( p < r )
  47.         {
  48.                 q = ( int )floor( ( p + r ) / 2 );
  49.                 MERGE_SORT( A , p , q );
  50.                 MERGE_SORT( A , q+1 , r );
  51.                 MERGE( A , p , q , r );
  52.         }
  53. }

  54. main()
  55. {
  56.         int i;
  57.         int x[100];

  58.         for( i = 0; i < 10; i++ )
  59.         {
  60.                 x[i] = rand() % 100;
  61.                 printf("x[%d] = %d\n", i, x[i] );
  62.         }

  63.         MERGE_SORT( x , 0 , 9 );

  64.         for( i = 0; i < 10; i++ )
  65.         {
  66.                 printf("x[%d] = %d\n", i, x[i] );
  67.         }

  68.     getch();
  69. }
复制代码


分治排序.rar

656 Bytes, 下载次数: 4, 下载积分: 黑币 -5

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏1 分享淘帖 顶 踩
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表