今天由我来给大家介绍一个我学习阶段想出来排序算法，该排序算法基于对数据的二进制状态下的某一位0或者1的排序，从最高位二进制开始，对子数组进行下一位二进制排序的递归快速排序

我的算法思路是这样的

1、从数组中最高二进制为1开始，一个指针从首位开始寻找最高位二进制为1的整数，另一个指针从末尾开始寻找最高二进制为0的整数，然后交换这两个数，指针依次向中间寻找一一对应的0和1，并交换，第一步完成后就得到左边全是最高位二进制为0的整数，右边全是最高位二进制为1的整数

2.依次对剩余两个子数组进行下一位二进制数的排序，0放前，1放后，利用递归重复这种操作就能将数组排序好

3.这样每个整数只需遍历最高位二进制的位数次就能结束递归操作，该排序算法的时间复杂度为最高位二进制的位数乘以数组长度，也就是O（kn），空间复杂度：只需创建一些辅助变量，不与数组长度相关，取决于最高位二进制的位数，因此我认为是O（1）

以下就是二进制快速排序相关算法代码

#include <iostream>

#include <cmath>

#include<ctime>

#include<random>

//交换两个元素的值

void swap(int* a, int* b){

  int temp = *a;

  *a = *b;

  *b = temp;

}

//打印数组函数

void printArray(int arr[], int size){

  for (int i = 0; i < size; i++）

    std::cout << arr[i] << " ";

  std::cout << std::endl;

}

// 划分函数，选择一个基准元素，将小于等于基准的元素放在左边，大于基准的元素放在右边

int partition(int arr[], int low, int high, int c) {

  int p = pow(2, c);

  while (low < high) {

    while (((arr[low] & p) == 0) && (low < high)) { low++; }

    while (((arr[high] & p) == p) && low < high) { high--; }

    swap(&arr[low], &arr[high]);

  }

//判断最后指针指向1还是0，把指针置为前面全为该二进制位数0下标

  if ((arr[low] & p) == p) {

    return low - 1;

  }

  else {

    return low;

  }

}

void quickSort(int arr[], int low, int high, int c) {

  if (low < high && c >= 0) {

    int pi = partition(arr, low, high, c);

    quickSort(arr, low, pi, c - 1);

    quickSort(arr, pi + 1, high, c - 1);

  }

}

// 测试示例

int main() {

  clock_t start, end;

  double cpu_time_used;

  start = clock();

    int arr[100000];

    std::default_random_engine gen(static_cast<unsigned int>(time(0)));

    std::uniform_int_distribution<int> dis(0, 1024);

    for (int i = 0; i < 100000; ++i) {

      arr[i] = dis(gen);

    }

  int n = sizeof(arr) / sizeof(arr[0]);

  quickSort(arr, 0, n - 1, 10);

  end = clock();

  cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

  std::cout << "代码运行时间: " << cpu_time_used << " 秒" << std::endl;

  return 0;

}

下面是我对代码的一些个人觉得还有改进的地方：1、有没有一个能够直接提取二进制某一位的0或1，然后跳单个数据的存储空间得到下一位，避免用&操作其余为0的二进制位，这样就能提高一些效率。2、遍历一遍记录整数在二进制位的每一位位数及所有在该位为1的数，这样可以跳过一些为全为0的二进制位。

看到这里的大家，谢谢大家的观看，我其实并不是一位程序员，我目前在土木工程行业从事施工员的工作，为什么学习编程，一方面是我现在工作确实不想继续干了，一方面我确实对编程有着极大的兴趣，因此发了这篇粗糙的文章，想要得到大家的认可

以上均为本人个人观点，看在我还没入行，望轻喷，标题只是吸引大家注意，不要在意；最后，希望大家指正及建议

————————————————

              版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/2401_86662195/article/details/141231626