[分享] CMake构建实战读书笔记04-CMake快速排序

DDZZ669 2024-10-7 10:40 楼主

本篇来学习CMake构建实战的第5章：CMake快速排序。

第5章只有一个使用CMake编写的快速排序的脚本，我们就来分析下这个脚本。

# 1 CMake快速排序脚本分析

## 1.1 分区算法

定义一个partition函数，参数有：

- arr：输入的数组（或称列表），作为输入参数
- pivot：主元（或称分界值），作为输入参数
- left：比主元小的数据组成的数组，作为结果输出
- right：比主元大或相等的数据组成的数组，作为结果输出

这里使用set命令中的PARENT_SCOPE来实现将内部变量传递到外层

```cmake
function(partition arr pivot left right)
    foreach(x ${arr})
        if(${x} LESS ${pivot})
            list(APPEND _left ${x})
        else()
            list(APPEND _right ${x})
        endif()
    endforeach()

set(${left} ${_left} PARENT_SCOPE)
    set(${right} ${_right} PARENT_SCOPE)
endfunction()
```

## 1.2 快速排序函数

定义一个quick_sort函数，参数有：

- input：待排序的数组（或称列表），作为输入参数
- res：排序结果数组，作为结果输出

该函数中，首先会判断待排序的数组长度是否小于等于（LESS_EQUAL）1，如果是，则不需要排序了。

然后通过list的GET方法来获取待排序数组中的第一个元素作为主元，

然后通过SUBLIST来将第一个元素去除后得到新的数组，并对该数组带哦有分区算法函数，

将得到的主元左、右的子数组，通过递归调用的方式，分别得到其排序结果，

最后将左数组的排序结果，连接主元，再连接右数组的排序结果，即可得到最终原始数组的排序结果。

```cmake
function(quick_sort input res)
    list(LENGTH input input_len)

if(${input_len} LESS_EQUAL 1)
        set(${res} "${input}" PARENT_SCOPE)
        return()
    endif()
    
    list(GET input 0 pivot)
    list(SUBLIST input 1 -1 input)

partition("${input}" ${pivot} left right)
    quick_sort("${left}" left)
    quick_sort("${right}" right)

list(APPEND _res ${left} ${pivot} ${right})
    set(${res} "${_res}" PARENT_SCOPE)
endfunction()
```

## 1.3 客户端代码

通过for循环来接收参数的方式来获取要排序的数据，这里数字4表示要忽略前面的4个参数，后面开始是要排序的数据。

然后调用quick_sort函数进行排序，并打印排序前后的结果：

```cmake
foreach(i RANGE 4 ${CMAKE_ARGC})
    list(APPEND input ${CMAKE_ARGV${i}})
endforeach()

message("排序前: ${input}")
quick_sort("${input}" res)
message("排序后: ${res}")
```

测试结果如下：

# 2 改写成C++

也可以改写成C++代码来做下对比，这里使用std::vector存储排序的数组。

## 2.1 分区算法

也是4个参数，通过for循环，来将数据根据主元（pivot）分为左右两个部分

```c++
void partition(std::vector<int> &arr, int pivot, std::vector<int> &left, std::vector<int> &right)
{
  left.clear();
  right.clear();
  
    for (int &it : arr)
    {
        (it < pivot) ? left.push_back(it) : right.push_back(it);
    }
}

```

## 2.2 快速排序

可以只有一个待排序数组作为参数，并将排序结果通过返回值返回

```c++
std::vector<int> quick_sort(std::vector<int> &input)
{
    if(input.size() <= 1)
    {
        return input;
    }
    
    int pivot = input[0];
    input.erase(input.begin());

std::vector<int> left;
  std::vector<int> right;

partition(input, pivot, left, right);
    left = quick_sort(left);
    right = quick_sort(right);
    
    left.push_back(pivot);
    left.insert(left.end(), right.begin(), right.end());
    
    return left;
}

```

## 2.3 客户端代码

通过main函数的参数接收功能来实现待排序数据的获取，并单独写一个printf_vector来实现数据的打印。

```c++
//g++ -o test01 -std=c++11 test01.cpp
#include <unistd.h>
#include <vector>
#include <string>

std::string printf_vector(std::vector<int> data)
{
  std::string res;
  for (int it : data)
  {
  res += std::to_string(it);
  }
  return res;
}

int main(int argc, char **argv)
{
  std::vector<int> input;
  
  for (int i=1; i<argc; i++)
  {
  input.push_back(std::atoi(argv<i>));
    }

printf("排序前: %s\n", printf_vector(input).c_str());
  input = quick_sort(input);
  printf("排序后: %s\n", printf_vector(input).c_str());

return 0;
}
```

测试结果如下：

# 3 总结

本篇介绍了CMake构建实战的第5章：CMake快速排序，分析了脚本的代码逻辑，并通过改写为C++语言，进行对比。