梳排序算法实现梳排序算法|数据结构

梳理排序是冒泡排序的高级形式。冒泡排序会比较所有相邻的值, 而梳齿排序会删除列表末尾附近的所有乌龟值或较小的值。
影响梳齿排序的因素有：

通过使用大于1的间隙来改进气泡排序。
间隙从大值开始, 然后缩小1.3倍。
差距缩小直到值达到1。

复杂

算法	复杂
最坏情况的复杂性	O(n2)
最佳案例复杂度	θ（n log n）
平均案件复杂度	Ω（n2 / 2p）, 其中p是增量数。
最坏情况下的空间复杂性	O(1)

算法

步骤1开始
步骤2如果间隙值== 1, 则计算间隙值转到步骤5, 否则转到步骤3
步骤3遍历数据集并将每个项目与缺口项目进行比较, 然后转到步骤4。
步骤4如果需要则交换元素转到步骤2
步骤5打印排序后的数组。
步骤6停止

【梳排序算法实现】程序

#include < stdio.h> #include < stdlib.h> int newgap(int gap){gap = (gap * 10) / 13; if (gap == 9 || gap == 10)gap = 11; if (gap < 1)gap = 1; return gap; } void combsort(int a[], int aSize){int gap = aSize; int temp, i; for (; ; ){gap = newgap(gap); int swapped = 0; for (i = 0; i < aSize - gap; i++) {int j = i + gap; if (a[i] > a[j]){temp = a[i]; a[i] = a[j]; a[j] = temp; swapped=1; }}if (gap==1 & & !swapped)break; }}int main (){int n, i; int *a; printf("Please insert the number of elements to be sorted: "); scanf("%d", & n); // The total number of elementsa=(int *)calloc(n, sizeof(int)); for (i = 0; i< n; i++){printf("Input element %d :", i); scanf("%d", & a[i]); // Adding the elements to the array}printf("unsorted list"); // Displaying the unsorted arrayfor(i = 0; i < n; i++){printf("%d", a[i]); }combsort(a, n); printf("Sorted list:\n"); // Display the sorted arrayfor(i = 0; i < n; i++){printf("%d ", (a[i])); }return 0; }