CMake构建实战读书笔记04-CMake快速排序
本篇来学习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;
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));
}
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++语言，进行对比。
<p>CMake编写这些经典程序会比较方便吗？ </p>
秦天qintian0303 发表于 2024-10-7 11:32
CMake编写这些经典程序会比较方便吗？
<p>可以用来学习CMake语法</p>
页:
[1]