梳排序

梳排序是氣泡排序的推進形式。氣泡排序會比較所有相鄰值，而梳排序會刪除列表末尾附近的所有小值。

影響梳排序的因素有：

• 通過使用大於1的間隙來改進氣泡排序。
• 差距從大值開始，收縮至因子1.3。
• 差距縮小直到值達到1。

複雜性

演算法

第1步，開始
第2步，如果間隙值 == 1，則計算間隙值，然後轉到第5步，否則轉到第3步
第3步，疊代資料集並將每個專案與間隙專案進行比較，然後轉到第4步。
第4步，如果需要，請交換元素轉到第2步。
第5步，列印已排序的組數。
第6步，停止

使用C語言實現桶排序演算法，程式碼如下所示 -

#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;  
}