C++使用移位操作对数字进行排序

Question

我想问一下如何使用移位操作按大小对整数位进行排序。这是一个例子:

Input : 12823745
Output : 87543221

基本上是把数字从高位到小位排序我听说可以不使用 Bubblesort/Quicksort 算法，而是使用一些移位操作。

有人知道如何实现吗？

Answer 1

快速排序和冒泡排序是通用算法。因此，不要对要排序的数据做出任何假设。然而，只要我们有关于数据的额外信息，我们就可以使用它来获得不同的东西(我不会说更好/更快或类似的东西，因为它真的很难比像快速/冒泡排序这样简单而强大的东西更好，这实际上取决于您需要什么的具体情况。

如果要排序的元素数量有限(只有 10 个不同的数字)，可以使用这样的方法:

#include <iostream>
#include <vector>
using namespace std;
typedef std::vector<int> ivec; 

void sort(std::vector<int>& vec){
    ivec count(10,0);
    for (int i=0;i<vec.size();++i){count[vec[i]]++;}
    ivec out;
    for (int i=9;i>-1;--i){
        for (int j=0;j<count[i];j++){
            out.push_back(i);
        }
    }
    vec = out;
}
void print(const ivec& vec){
    for (int i=0;i<vec.size();++i){std::cout << vec[i];}
    std::cout << std::endl;
}
int main() {
    ivec vec {1,2,8,2,3,7,4,5};
    sort1(vec);
    print(vec);
    return 0;
}

请注意，这具有 O(N) 的复杂度。此外，当一组可能的元素具有有限大小时(不仅对于数字而且对于 float )，这总是有效的。不幸的是，它仅适用于非常小的尺寸。

有时仅仅计算元素是不够的。除了必须排序的值之外，它们可能还有一些身份。然而，上面的代码可以很容易地修改以在这种情况下也能工作(需要相当多的拷贝，但仍然是 O(n))。

其实我不知道你的问题是如何通过位移运算来解决的。但是，我只是想指出，当您的数据具有良好的属性(有时它甚至可以更有效)时，总有一种方法可以不使用通用算法。