|
|
分治排序算法
- #include<stdio.h>
- #include<stdlib.h>
- #include<math.h>
- /*將A數組中p到r元素進行分治排序*/
- MERGE(int *A, int p, int q, int r)
- {
- int n1 = q - p + 1;//數組L中元素個數
- int n2 = r - q;//數組R中元素個數
- int *L, *R;
- int i;
- int j;
- int k;
- L = malloc( ( n1 + 1 ) * sizeof( int ) );
- R = malloc( ( n2 + 1 ) * sizeof( int ) );
- for( i = 0; i < n1; i++ )
- {
- *( L + i ) = *( A + p + i );//A[p]到A[q]
- }
- for( i = 0; i < n2; i++ )
- {
- *( R + i ) = *( A + q + i + 1 );//A[q+1]到A[r]
- }
- L[n1] = 2147483647;//2^31-1
- R[n2] = 2147483647;//2^31-1
- i=0;
- j=0;
- for( k = p; k <= r; k++ )
- {
- if( L[i] <= R[j] )
- {
- A[k] = L[i];
- i = i + 1;
- }
- else
- {
- A[k] = R[j];
- j = j + 1;
- }
- }
- free( L );
- free( R );
- }
- MERGE_SORT( int *A, int p, int r )
- {
- int q;
- if( p < r )
- {
- q = ( int )floor( ( p + r ) / 2 );
- MERGE_SORT( A , p , q );
- MERGE_SORT( A , q+1 , r );
- MERGE( A , p , q , r );
- }
- }
- main()
- {
- int i;
- int x[100];
- for( i = 0; i < 10; i++ )
- {
- x[i] = rand() % 100;
- printf("x[%d] = %d\n", i, x[i] );
- }
- MERGE_SORT( x , 0 , 9 );
- for( i = 0; i < 10; i++ )
- {
- printf("x[%d] = %d\n", i, x[i] );
- }
- getch();
- }
|
-
-
分治排序.rar
2018-1-27 11:58 上傳
點擊文件名下載附件
下載積分: 黑幣 -5
656 Bytes, 下載次數: 4, 下載積分: 黑幣 -5
|
