梳排序算法实现

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

影响梳齿排序的因素有：

• 通过使用大于1的间隙来改进气泡排序。
• 间隙从大值开始, 然后缩小1.3倍。
• 差距缩小直到值达到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 elements
    a  =  (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 array
    for(i = 0;i < n;i++)
    {
         printf("%d", a[i]);
    }
    combsort(a, n);
    printf("Sorted list:\n"); // Display the sorted array
    for(i = 0;i < n;i++)
    {
        printf("%d ", (a[i]));
    }
    return 0;
}