radixsort.txt

radix排序法

//**************************************
//     
// Name: Radix Sort
// Description:This is a radix sort, an 
//     extermly fast sort for integer data type
//     s: char, int, and long.
The sample program using the radix sort sorts an array of 80,000 random integers, and writes the sorted numbers to a text file.
// By: Wesley Hopper
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void main()


    {
    	srand(time(NULL));
    	const int numdata=80000; //How many numbers to sort
    	int data[numdata]; //The random number array
    	
    	//make random numbers for the number array
    	for(int a=0; a<numdata; a++)
    		data[a]=rand();
    			
    	//Data for the radix sort	
    	int array1[numdata], array0[numdata];	
    	int num1, num0, mask=1;
    /**********************************************************************/
    	/**********************************
    				Radix Sort
    	The count<NUM must be the number of 
    	bits of the data type to be sorted
    	char=8,int=16,long=32
    	**********************************/
    	for(int bit=0; bit<16; bit++) //for each bit of the data type


        	{
        		num1=num0=0; //set num of 0's & 1's back to 0
        		//for each number in the number array
        		for(int index=0; index<numdata; index++)


            		{
            			//if the value of this bit is 1,
            			//copy the number to the 1's array
            			//and increase the 1's counter
            	if(data[index] & mask)


                			{
                				array1[num1]=data[index];
                				num1++;	
                			}
                				
                			//if the value of this bit is 0, 
                			//copy the number to the 0's array
                			//and increase the 0's counter
                			else


                    			{
                    				array0[num0]=data[index];
                    				num0++;
                    			}
                    		}
                    		/*************************************
                    			Copy the numbers into the number 
                    		array from the 1's and 0's arrays, 1's 
                    		first sorting them from greatest to 
                    		least. Copy the 0's array first to sort
                    		from least to greatest.
                    			the num*<<2 is the number of 1's
                    		or 0's bit shifted to the left 2.
                    		this is an optimized multiplication 
                    		by 4 (2^2), which is the size of a 
                    		32-bit variable.
                    		*************************************/
                    		memcpy(data, array1, num1<<2); 
                    memcpy(data+num1, array0, num0<<2); 
                    		//bitshift mask left for next bit
                    		mask<<=1; 
                    	}
                    	
                    /*************************************************************/
                    	
                    	//write sorted numbers to a text file
                    	FILE *file=fopen("C:\\numbers.txt", "w");
                    	for(int x=0; x<numdata; x++)
                    		fprintf(file, "%i\n", data[x]);
                }