排序之基数排序

爱被打了一巴掌 2022-05-15 14:41 204阅读 0赞

# 基数排序: #

基数排序(radix Sort)是桶排序的扩展，它的基本思想是: 对长度为n的序列进行排序，序列中最大数是k位，我们将从个位开始进行分割 合并，重复此操作直到第k位结束。

### 第一个栗子: ###

基数排序对序列\{123，234，564，765，876，324，651，874，432\}

![/images/20220503/d804e5c326d04cea93502c5b267fc21d.png][https_img-blog.csdn.net_20170517212304744_watermark_2_text_aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG91YmxlX2hhcHBpbmVzcw_font_5a6L5L2T_fontsize_400_fill_I0JBQkFCMA_dissolve_70_gravity_Center]

### 第二个栗子: ###

用基数排序对序列\{53，3，542，748，14，214，154，63，616\}，示意图如下:

![/images/20220503/ce499be938a1470bad2b3ea20d5a13a0.png][https_images0.cnblogs.com_i_497634_201403_161837176365265.jpg]

此例子中，最大数是748.

所以将会对序列分割成三位: 个位 十位 百位

经过三次排序后，便生成了有序序列。

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    #include <vector>
    using namespace std;
    
    void countArray(int num[],int n,int exp)
    {
    	vector<int> vec[10];
    	for(int i = 0; i < n; i++)
    	{
    		vec[num[i] / exp % 10].push_back(num[i]);  //将该位的数塞入桶中 
    	}
    	int a=0;
    	for(int i = 0;i < 10; i++)
    	{
    		for(int j = 0;j < vec[i].size(); j++)
    		{
    			num[a] = vec[i][j];         //对原数组进行重新排列 
    			a++;
    		}
    	}
    }
    
    void radixSort(int num[],int max,int n)   //根据max的值进行从小到大排序 
    {
    	int exp;
    	for(exp = 1 ; max/exp > 0; exp *= 10)
    	{
    		countArray(num , n, exp);
    	}
    }
    
    int main()
    {
    	int n;
    	while( cin >> n )  //产生n个随机数进行排序 
    	{
    		srand(time(0));
    		int num[n];
    		int max = -99999;       
    		for(int i = 0; i < n; i++)
    		{
    			num[i] = rand() % 65536;
    			max = max > num[i] ? max : num[i];
    		}
    		radixSort(num , max, n);
    		for(int i = 0; i < n; i++)
    		{
    			cout << num[i] << ends;
    		}
    		cout << endl;
    	}
    	
    	return 0;	
    }

运行结果:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3huaF81NjUxNzU5NDQ_size_16_color_FFFFFF_t_70][]

[https_img-blog.csdn.net_20170517212304744_watermark_2_text_aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG91YmxlX2hhcHBpbmVzcw_font_5a6L5L2T_fontsize_400_fill_I0JBQkFCMA_dissolve_70_gravity_Center]: /images/20220503/d804e5c326d04cea93502c5b267fc21d.png
[https_images0.cnblogs.com_i_497634_201403_161837176365265.jpg]: /images/20220503/ce499be938a1470bad2b3ea20d5a13a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3huaF81NjUxNzU5NDQ_size_16_color_FFFFFF_t_70]: /images/20220503/91b143666383423fb8d602db2d845fae.png