梳排序
入门理解"间隔缩小"如何将冒泡排序从 O(n²) 优化到接近 O(n log n)。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void combSort(int arr[], int n) {
2 int gap = n;
3 bool swapped = true;
4 while (gap > 1 || swapped) {
5 gap = max(1, (int)(gap / 1.3));
6 swapped = false;
7 for (int i = 0; i + gap < n; i++)
8 if (arr[i] > arr[i+gap]) { swap(arr[i], arr[i+gap]); swapped = true; }
9 }
10}
复杂度分析
时间 O(n²/2^p)
空间 O(1)
最优 O(n log n)
最坏 O(n²)
算法讲解
梳排序是冒泡排序的改进，初始间隔为数组长度，每轮缩小为原来的 1/1.3。
当间隔为 1 时，它就变成了冒泡排序。
使用缩减因子 1.3 可以在平均情况下达到 O(n²/2^p) 的性能。
它是理解"间隔排序"思想的好入口。