看了一本书，《数据结构（C语言版）1000个问题与解答》，这本书第481-482页，介绍了一种快速排序方法，感觉挺有趣的（也感觉挺奇怪的，尤其是gap值的选择方法），就在VS2022中做了代码实现，和大家共同学习研究。
在VS2022中创建空项目，添加文件“main.cpp”，并输入如下代码：
#include 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，元素个数为nDataSizeint 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;elsestd::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值的更新算法，但是经过检验，这个组合排序算法确实是正确的，能正确地完成排序。