Radix sort based on counting sort:O(n) time complexity and O(log(n)) space complexity


  • 0
    L

    const int RADIX = 16;

    void baseSort(int *data, int lenth, int radix)
    {

    int count[RADIX] = { 0 }, offset[RADIX] = { 0 };
    
    for (int i = 0; i < lenth; i++){
    	count[(data[i] / radix) % RADIX]++;
    }
    for (int i = 1; i < RADIX; i++){
    	count[i] += count[i - 1];
    	offset[i] = count[i - 1];
    }
    for (int times = 0; times < RADIX; times++){
    	int *keyOffset = &offset[times];
    	while (offset[times] < count[times]){
    		int nextKey = (data[*keyOffset] / radix) % RADIX;
    		int *nextkeyOffset = &offset[nextKey];
    		if (nextKey == times){
    			(*keyOffset)++;
    		}
    		else{
    			while (nextKey == (data[*nextkeyOffset] / radix) % RADIX){
    				(*nextkeyOffset)++;
    			}
    			swap(data[*keyOffset], data[*nextkeyOffset]);
    			(*nextkeyOffset)++;;
    			/*
    			for (int i = 0; i < lenth; i++)
    			cout << data[i] << "->";
    			cout << endl;//*/
    		}
    	}
    	if (times == 0 && count[0]>1 && radix >= RADIX)
    		baseSort(data, count[0], radix / RADIX);
    	else if (times != 0 && count[times] - count[times - 1]>1 && radix >= RADIX)
    		baseSort(&data[count[times - 1]], count[times] - count[times - 1], radix / RADIX);
    }
    

    }
    void myRadixSort(int *data, int lenth)
    {

    long long maxRadix = RADIX;
    for (int i = 0; i < lenth; i++)
    {
    	while (INT_MAX >= maxRadix)
    		maxRadix *= RADIX;
    }
    maxRadix /= RADIX;
    baseSort(data, lenth, maxRadix);
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.