0

为什么与冒泡排序和插入排序相比，shell 排序的时间复杂度更低？我们如何计算时间复杂度，我的意思是我们认为我们的代码是高时间复杂度还是低时间复杂度？

#include <stdio.h>
void shellsort(int arr[], int num)
{
    int i, j, k, tmp;
    for (i = num / 2; i > 0; i = i / 2)
    {
        for (j = i; j < num; j++)
        {
            for (k = j - i; k >= 0; k = k - i)
            {
                if (arr[k + i] >= arr[k])
                    break;
                else
                {
                    tmp = arr[k];
                    arr[k] = arr[k + i];
                    arr[k + i] = tmp;
                }
            }
        }
    }
}
int main()
{
    int arr[30];
    int k, num;
    printf("Enter total no. of elements : ");
    scanf("%d", &num);
    printf("\nEnter %d numbers: ", num);
    for (k = 0; k < num; k++)
    {
        scanf("%d", &arr[k]);
    }
    shellsort(arr, num);
    printf("\n Sorted array is: ");
    for (k = 0; k < num; k++)
        printf("%d ", arr[k]);
    return 0;
}
4

1 回答 1

0

关于您的问题，我们认为我们的代码是高时间复杂度还是低时间复杂度，对于具有 N 个元素的排序算法，一个简单的考虑是进行多少次比较以使元素数组排序。比较进一步导致交换元素，这转化为系统（CPU）上使用的更多资源。

冒泡/插入排序可以以 n^2 比较结束（如果没有进行交换，则可以优化，然后不再扫描已排序的数组）。Shell 排序经过改进，在某些情况下比 n^2 做得更好。维基百科指针是一个很好的参考，但建议阅读一本关于算法的书，专门处理排序以获得更清晰的信息（数据结构和算法分析 - Mark Allen Weiss 或其他一些人）

于 2017-02-16T23:05:29.740 回答