看了一本书，《数据结构（C语言版）1000个问题与解答》，这本书第481-482页，介绍了一种快速排序方法，感觉挺有趣的（也感觉挺奇怪的，尤其是gap值的选择方法），就在VS2022中做了代码实现，和大家共同学习研究。
在VS2022中创建空项目，添加文件“main.cpp”，并输入如下代码：
#include <iostream>
int update_gap(int gap);
void combine_sort(double* pData, int nDataSize);
void show_data_value(double* pData, int nDataSize);
bool monotone_increasing(double* pData, int nDataSize);
bool bPrint = true; // 是否显示
// 更新gap值（gap值是进行比较的两个元素之间的间隔数.）
// 输入gap值，返回更新后的gap值.
// 由combine_sort函数调用.
int update_gap(int gap)
{
gap = (gap * 10) / 13;
if (gap == 9 || gap == 10)
gap = 11;
if (gap < 1)
return 1;
return gap;
}
// 对数组pData中的数值按从小到大顺序排序(组合排序).
// 组合排序的代码实现参考了文献《数据结构（C语言版）1000个问题与解答》第481-482页.
void combine_sort(double *pData, int nDataSize)
{
int gap = nDataSize;
std::cout << "gap初始值：" << gap << std::endl;
bool bSwapped = false;
do {
bSwapped = false;
gap = update_gap(gap);
std::cout << "gap值：" << gap << std::endl;
for (int i = 0; i < nDataSize - gap; i++) {
if (pData[i]>pData[i + gap]) { // 比较
if(bPrint)
std::cout << "交换pData[" << i <<"](值为"<< pData[i] << ")"
<< "和pData[" << i+gap << "](值为" << pData[i+gap]<<")的值：" << std::endl;
// 交换.(将乌龟移到顶部，帮助兔子走到底部)
double temp = pData[i]; pData[i] = pData[i + gap]; pData[i + gap] = temp;
bSwapped = true;
// 显示交换后的数据值
if (bPrint) show_data_value(pData, nDataSize);
}
}
} while (gap > 1 || bSwapped);
}
// 显示数据的值
void show_data_value(double* pData, int nDataSize)
{
for (int i = 0; i < nDataSize; i++)
std::cout << pData[i] << " ";
std::cout << std::endl;
}
// 判断数组是否是单调递增的.
bool monotone_increasing(double* pData, int nDataSize)
{
for (int i = 0; i < nDataSize - 1; i++) {
if (pData[i + 1] < pData[i]) {
std::cout << "pData[" << i + 1 << "]（值" << pData[i + 1] << ")小于pData[" << i << "](值" << pData[i] << ")" << std::endl;
return false;
}
}
return true;
}
int main()
{
// 构造数组pData，元素个数为nDataSize
int nDataSize = 13;
double* pData = new double[nDataSize];
for (int i = 0; i < nDataSize; i++)
pData[i] = nDataSize - i;
// 排序前，显示pData的初始值.
std::cout << "排序前pData的值:" << std::endl;
show_data_value(pData, nDataSize);
bool b = monotone_increasing(pData, nDataSize);
// 调用combine_sort进行排序
combine_sort(pData, nDataSize);
// 排序前，显示pData的初始值.
std::cout << "排序后pData的值:" << std::endl;
show_data_value(pData, nDataSize);
if(!monotone_increasing(pData, nDataSize))
std::cout << "出错：排序后pData的值不满足单调递增性." << std::endl;
else
std::cout << "正确：排序后pData的值满足单调递增性." << std::endl;
return 1;
}
update_gap用于更新gap的值，这个更新算法确实有些新奇，看不明白这种算法是经过严格的数学证明还是根据经验设置的；combine_sort是排序的核心算法，通过比较、交换将数组元素按照从小到大排序；show_data_value是个辅助函数，用于显示数组的内容；monotone_increasing也是个辅助函数，用于验证数组中的元素是否是单调递增的。bPrint用于控制combine_sort执行过程中是否在控制台显示数组的内容。
main函数创建数组，并对函数的正确性进行检验。
当nDataSize的值为13时，其程序执行结果如下：
当nDataSize的值为1300时，排序依然正确。
虽然不是太明白gap值更新算法，但是经过检验，这个组合排序算法确实是正确的，能正确地完成排序。