bác cho em hỏi
for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++
dể làm gì đó.chương trình này em không hiểu lắm
Đây là code của radix sort, ý tưởng của giải thuật này là sắp xếp trên từng byte. Ý tưởng của bạn về giải thuật này là gì?C++ Code:
#include <iostream.h> #include <stdlib.h> #include <string.h> void radix (int byte, long N, long *source, long *dest) { long count[256]; long index[256]; memset (count, 0, sizeof (count)); for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++; index[0]=0; for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1]; for ( i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i]; } void radixsort (long *source, long *temp, long N) { radix (0, N, source, temp); radix (1, N, temp, source); radix (2, N, source, temp); radix (3, N, temp, source); } void make_random (long *data, long N) { for ( int i=0; i<N; i++ ) data[i]=rand()|(rand()<<16); } long data[100]; long temp[100]; void main (void) { make_random(data, 100); radixsort (data, temp, 100); }
Đã được chỉnh sửa lần cuối bởi rox_rook : 29-05-2009 lúc 02:30 PM. Lý do: Dùng tag code cho đẹp ^_^
bác cho em hỏi
for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++
dể làm gì đó.chương trình này em không hiểu lắm
Cái này mình đang cần rất cám ơn nhiều.
cái này mình làm nhưng còn một số lỗi! mong các pác giúp nghen!Code:#include<conio.h> #include<stdio.h> #include<stdlib.h> #include<math.h> #define MAX 100 #define MAXDIGIT 3 void Nhapmang(int a[], int & n) { do{ n=random(100); }while(n<10); for(int i=0; i<n; i++) a[i]=random(100); } //--------------------------------------------- void Xuatmang(int a[], int n) { for(int i=0; i<n; i++) printf("%3d",a[i]); } //----------------------------------- void Swap(int &a, int &b) { int tmp; tmp=a; a=b; b=tmp; } //--------------------------------------- void radixsort(long a[], int n) { int i,j,d,num,digit; int len[10]; int h=10; long B[10][MAX]; for( d=0; d<MAXDIGIT; d++) { for(i=0; i<10; i++) len[i]=0; for(i=0; i<n; i++) { digit=(a[i]%h)/(h/10); B[digit][len[digit]++]=a[i]; num=0; for(i=0; i<10; i++) for(i=0;i<len[i]; i++) a[num++]=B[i][j]; h*=10; } } } void main() { clrscr(); int a[MAX],n; Nhapmang(a,n); printf("\nMang truoc khi sap xep:\n"); Xuatmang(a,n); radixsort(a,n); printf("\nMang sau khi sap xep:\n"); Xuatmang(a,n); getch(); }