数据结构与算法面试：基于比较的排序算法时间复杂度最坏情况下是 O(nlogn)，请问有没有更快的算法？（提示：计数排序、基数排序）

ゝ一世哀愁。 2024-03-16 17:05 8阅读 0赞

## 数据结构与算法面试：基于比较的排序算法时间复杂度最坏情况下是 O(nlogn)，请问有没有更快的算法？（提示：计数排序、基数排序） ##

简介：基于比较的排序算法时间复杂度最坏情况下是 O(nlogn)，请问有没有更快的算法？（提示：计数排序、基数排序）

基数排序是一种时间复杂度O(nlogn)的排序算法，其中d是数组a中最大数字的位数。如果数字长度d较小，那么基数排序要比比较排序更快。

基数排序的实现思路如下：

1.  用一个桶数组来记录每个可能的数字出现的次数（这里假设数值范围在0~9之间）。
2.  将原始数组a依次按照个位、十位、百位、千位…进行排序。对于某个"当前位数"可以采用计数排序或者桶排序的方式，在该轮排序后，原始数组a已经被排好序了。

下面是使用C++实现基数排序的代码，并附带详细注释：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    void radix_sort(vector<int>& a) {
        int n = a.size();
        if (n <= 1) return;
    
        // 获取数组中的最大值
        int max_val = a[0];
        for (int i = 1; i < n; ++i) {
            max_val = max(max_val, a[i]);
        }
    
        // 计算出最大值的长度
        int k = 0;
        while (max_val > 0) {
            max_val /= 10;
            ++k;
        }
    
        // 建立桶数组并进行基数排序
        vector<int> bucket(a.size());
        vector<int> count(10);
    
        // 每一轮循环按照不同的位数进行排序
        for (int i = 0, r = 1; i < k; ++i, r *= 10) {
            // 将桶清零
            fill(count.begin(), count.end(), 0);
    
            // 统计出现次数
            for (int j = 0; j < n; ++j) {
                int c = (a[j] / r) % 10;
                ++count[c];
            }
    
            // 计算前缀和
            for (int j = 1; j <= 9; ++j) {
                count[j] += count[j - 1];
            }
    
            // 按顺序将数放到桶中
            for (int j = n - 1; j >= 0; --j) {
                int c = (a[j] / r) % 10;
                bucket[--count[c]] = a[j];
            }
    
            // 从桶中取回数据
            for (int j = 0; j < n; ++j) {
                a[j] = bucket[j];
            }
        }
    }
    
    int main() {
        vector<int> a = {7, 6, 5, 4, 3, 2, 1, 0};
        radix_sort(a);
        for (int i = 0; i < a.size(); ++i) {
            cout << a[i] << " ";
        }
        cout << endl;
        return 0;
    }

该算法借助"桶"和"计数"两种数据结构，实现了时间复杂度O(dn)的基数排序算法。为了方便地处理数组中的数字，我们可以将其转换为字符串然后进行操作。

*  java

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    class Main {
        
        public static void radixSort(int[] a) {
        
            int n = a.length;
            if (n <= 1) return;
    
            // 获取数组中的最大值
            int max_val = a[0];
            for (int i = 1; i < n; ++i) {
        
                max_val = Math.max(max_val, a[i]);
            }
    
            // 计算出最大值的位数
            int k = 0;
            while (max_val > 0) {
        
                max_val /= 10;
                ++k;
            }
    
            // 建立桶数组并进行基数排序
            int[] bucket = new int[a.length];
            int[] count = new int[10];
    
            // 每一轮循环按照不同的位数进行排序
            for (int i = 0, r = 1; i < k; ++i, r *= 10) {
        
                // 将桶清零
                Arrays.fill(count, 0);
    
                // 统计出现次数
                for (int j = 0; j < n; ++j) {
        
                    int c = (a[j] / r) % 10;
                    ++count[c];
                }
    
                // 计算前缀和
                for (int j = 1; j < 10; ++j) {
        
                    count[j] += count[j - 1];
                }
    
                // 按顺序将数放到桶中
                for (int j = n - 1; j >= 0; --j) {
        
                    int c = (a[j] / r) % 10;
                    bucket[--count[c]] = a[j];
                }
    
                // 从桶中取回数据
                for (int j = 0; j < n; ++j) {
        
                    a[j] = bucket[j];
                }
            }
        }
    
        public static void main(String[] args) {
        
            int[] a = {
        7, 6, 5, 4, 3, 2, 1, 0};
            radixSort(a);
            for (int i = 0; i < a.length; ++i) {
        
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
    }