Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Thuật toán radix sort

  1. #1
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Mặc định Thuật toán radix sort

    C++ Code:
    1. #include <iostream.h>
    2. #include <stdlib.h>
    3. #include <string.h>
    4.  
    5. void radix (int byte, long N, long *source, long *dest)
    6. {
    7.   long count[256];
    8.   long index[256];
    9.   memset (count, 0, sizeof (count));
    10.   for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;
    11.  
    12.   index[0]=0;
    13.   for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
    14.   for ( i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
    15. }
    16.  
    17. void radixsort (long *source, long *temp, long N)
    18. {
    19.   radix (0, N, source, temp);
    20.   radix (1, N, temp, source);
    21.   radix (2, N, source, temp);
    22.   radix (3, N, temp, source);
    23. }
    24.  
    25. void make_random (long *data, long N)
    26. {
    27.   for ( int i=0; i<N; i++ ) data[i]=rand()|(rand()<<16);
    28. }
    29.  
    30. long data[100];
    31. long temp[100];
    32.  
    33. void main (void)
    34. {
    35.  make_random(data, 100);
    36.  radixsort (data, temp, 100);
    37.  for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
    38. }
    Đâ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 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 ^_^

  2. #2
    Ngày gia nhập
    05 2009
    Bài viết
    2

    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

  3. #3
    Ngày gia nhập
    03 2008
    Bài viết
    14

    Cái này mình đang cần rất cám ơn nhiều.

  4. #4
    Ngày gia nhập
    08 2009
    Bài viết
    9

    Mặc định ý tưỡng Radix sort

    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();
    }
    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!

Các đề tài tương tự

  1. Sắp xếp mảng số nguyên (âm dương) bằng Radix Sort
    Gửi bởi gialoui trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 22-10-2013, 08:15 PM
  2. code thuật toán radix sort bằng C, kết quả không đúng. Mọi người sửa giúp với?
    Gửi bởi yeulamvietnam trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 1
    Bài viết cuối: 24-11-2011, 11:55 PM
  3. Giúp em bài toán Mô phỏng thuật toán MERGE sort va RADIX Sort bằng C
    Gửi bởi mr.fan trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 03-06-2010, 09:34 AM
  4. Sắp xếp Radix sort. Nhờ mọi người sửa giúp
    Gửi bởi alexander88 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 17-10-2009, 06:39 AM
  5. Thuật radix sort
    Gửi bởi kinhmoiban trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 11-09-2008, 10:55 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn