数据结构-排序-基数排序法

本是古典何须时尚 2023-10-04 16:27 74阅读 0赞

#### 基数排序法 ####

基数排序法和我们之前所讨论的排序法不太一样，它并不需要进行元素间的比较操作，而是属于一种分配模式排序方式

基数排序法按比较的方向可以分为最高位优先(Most Significant Digit First,MSD)和最低位优先(Least Signigicat Digit First,LSD)两种。MSD法是从最左边的位数开始比较，而LSD则是从最右边的位数开始比较。以LSD为例对三位数的整数进行排序

原始数据

1.  把每个整数按其个位数字放到列表中
    
    <table> 
     <thead> 
      <tr> 
       <th>数字</th> 
       <th>0</th> 
       <th>1</th> 
       <th>2</th> 
       <th>3</th> 
       <th>4</th> 
       <th>5</th> 
       <th>6</th> 
       <th>7</th> 
       <th>8</th> 
       <th>9</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>数据</td> 
       <td>60</td> 
       <td>171</td> 
       <td>372</td> 
       <td>133</td> 
       <td>34</td> 
       <td>95<br>45</td> 
       <td></td> 
       <td>7</td> 
       <td>168<br>88</td> 
       <td>59<br>259</td> 
      </tr> 
     </tbody> 
    </table>
    
    合并之后为
    
    <table> 
     <thead> 
      <tr> 
       <th>原始数据</th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>60</td> 
       <td>171</td> 
       <td>372</td> 
       <td>133</td> 
       <td>34</td> 
       <td>95</td> 
       <td>45</td> 
       <td>7</td> 
       <td>168</td> 
       <td>88</td> 
       <td>59</td> 
       <td>259</td> 
      </tr> 
     </tbody> 
    </table>
2.  再按十位数
    
    <table> 
     <thead> 
      <tr> 
       <th>数字</th> 
       <th>0</th> 
       <th>1</th> 
       <th>2</th> 
       <th>3</th> 
       <th>4</th> 
       <th>5</th> 
       <th>6</th> 
       <th>7</th> 
       <th>8</th> 
       <th>9</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>数据</td> 
       <td>7</td> 
       <td></td> 
       <td></td> 
       <td>133<br>34</td> 
       <td>45</td> 
       <td>59<br>259</td> 
       <td>60<br>168</td> 
       <td>171<br>372</td> 
       <td>88</td> 
       <td>95</td> 
      </tr> 
     </tbody> 
    </table>
    
    合并之后为
    
    <table> 
     <thead> 
      <tr> 
       <th>原始数据</th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>7</td> 
       <td>133</td> 
       <td>34</td> 
       <td>45</td> 
       <td>59</td> 
       <td>259</td> 
       <td>60</td> 
       <td>168</td> 
       <td>171</td> 
       <td>372</td> 
       <td>88</td> 
       <td>95</td> 
      </tr> 
     </tbody> 
    </table>
3.  再按其百位数字
    
    <table> 
     <thead> 
      <tr> 
       <th>数字</th> 
       <th>0</th> 
       <th>1</th> 
       <th>2</th> 
       <th>3</th> 
       <th>4</th> 
       <th>5</th> 
       <th>6</th> 
       <th>7</th> 
       <th>8</th> 
       <th>9</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>数据</td> 
       <td>7<br>34<br>45<br>59<br>60<br>88<br>95</td> 
       <td>133<br>168<br>171</td> 
       <td>259</td> 
       <td>372</td> 
       <td></td> 
       <td></td> 
       <td></td> 
       <td></td> 
       <td></td> 
       <td></td> 
      </tr> 
     </tbody> 
    </table>
    
    合并之后为
    
    <table> 
     <thead> 
      <tr> 
       <th>原始数据</th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
       <th></th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>7</td> 
       <td>34</td> 
       <td>45</td> 
       <td>59</td> 
       <td>60</td> 
       <td>88</td> 
       <td>95</td> 
       <td>133</td> 
       <td>168</td> 
       <td>171</td> 
       <td>259</td> 
       <td>372</td> 
      </tr> 
     </tbody> 
    </table>

**基数排序法的分析**

*  在所有情况下，时间复杂度均为O(nlogpk),K是原始数据的最大值
 *  基数排序法是稳定排序法
 *  基数排序法会使用很大的额外空间来存放列表数据，其空间复杂度为O(n\*p),n是原始数据的个数，p是数据字符数。
 *  若n很大，p固定或很小，则此排序很有效

import random
    
    
    def radix(data,size):
        n = 1   #首先从各位开始
        while n <= 100:
            tmp = [[0] * 100 for row in range(10)]  #建立一个二维数组存储数据
            #存储临时数据
            for i in range(size):   #逐个查看数据
                m = (data[i] // n) % 10  #m为n位数的值，如36取十位数（36/10）%10=3
                tmp[m][i] = data[i]
            k = 0
            #取出临时数据
            for i in range(10):
                for j in range(size):
                    if tmp[i][j] != 0:  #把不为零的数据取出来放到data中
                        data[k] = tmp[i][j]
                        k += 1
            print('经过%3d位数排序后：'%n,end='')
            showdata(data,size)
            n *= 10
    
    def showdata(data,size):
        for i in range(1,size):
            print('%5d'%data[i],end='')
        print()
    
    def inputarr(data,size):
        for i in range(size):
            data[i] = random.randint(0,999)
    
    def main():
        data = [0] * 100
        size = int(input('请输入数组大小（100以下）：'))
        print('您输入的原始数据：')
        inputarr(data,size)
        showdata(data,size)
        radix(data,size)
    
    if __name__ == '__main__':
        main()