标题: C语言分治排序算法 [打印本页]
作者: rocfly    时间: 2018-1-27 11:58
标题: C语言分治排序算法
分治排序算法
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<math.h>

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

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

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

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

  30.         i=0;
  31.         j=0;

  33.         for( k = p; k <= r; k++ )
  34.         {
  35.                 if( L[i] <= R[j] )
  36.                 {
  37.                         A[k] = L[i];
  38.                         i = i + 1;
  39.                 }
  40.                 else
  41.                 {
  42.                         A[k] = R[j];
  43.                         j = j + 1;
  44.                 }
  45.         }

  47.         free( L );
  48.         free( R );
  49. }

  51. MERGE_SORT( int *A, int p, int r )
  52. {
  53.         int q;
  54.         if( p < r )
  55.         {
  56.                 q = ( int )floor( ( p + r ) / 2 );
  57.                 MERGE_SORT( A , p , q );
  58.                 MERGE_SORT( A , q+1 , r );
  59.                 MERGE( A , p , q , r );
  60.         }
  61. }

  63. main()
  64. {
  65.         int i;
  66.         int x[100];

  68.         for( i = 0; i < 10; i++ )
  69.         {
  70.                 x[i] = rand() % 100;
  71.                 printf("x[%d] = %d\n", i, x[i] );
  72.         }

  74.         MERGE_SORT( x , 0 , 9 );

  76.         for( i = 0; i < 10; i++ )
  77.         {
  78.                 printf("x[%d] = %d\n", i, x[i] );
  79.         }

  81.     getch();
  82. }
复制代码


分治排序.rar

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





欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1