识别这种形式的排序算法并计算其时间复杂度

Question

在尝试排序时，我想到了一种类似于某种插入排序的排序方式。

不同之处在于，在交换时，我不必比较从元素索引到索引 0 的元素（最坏情况）。

它也类似于分而治之的排序算法，因为它在同一数组中模拟已排序的扇区和未排序的扇区。

我的看法是，最初我会将当前元素指定为第一个元素。然后我会将当前元素与下一个元素进行比较。如果电流更大，我交换元素。然后我递减以保持当前索引相同。

否则，我递增以推进当前索引。

这意味着我的电流永远是最新的参考值。比较的其他值总是较小且排序。

请参考代码：

#include<stdio.h>

void printArray(int *a, int l)
{
    int i = 1;
    printf("[%d", a[0]);
    while(i < l)
    {
        printf(", %d", a[i]);
        ++i;
    }
    printf("]\n");
}

void whatSort(int *a, int l)
{
    int i = 0;
    int temp;

    while(i < (l - 1))
    {
        if(*(a + i) > *(a + i + 1))
        {
            temp = *(a + i);
            *(a + i) = *(a + i + 1);
            *(a + i + 1) = temp;
            --i;
        }
        else
        {
            ++i;
        }
    }
}

int main(void)
{
    //int array[] = {42, 18, 74, 2, 35, 92, 37, 25};
    int array[] = {6, 5, 3, 1, 8, 7, 2, 4};
    printArray(array, 8);
    whatSort(array, 8);
    printArray(array, 8);
    return 0;
}

我很确定这种类型（双关语）已经存在，但我找不到名字。很高兴知道它叫什么。尽管如此，我只希望在计算此类代码的运行时复杂性方面得到帮助。这就是我想出的。任何帮助将不胜感激。

对于这种特殊情况，假设每个操作需要 1 个时间单位。

Declaration
Assignment
Declaration

Loop condition will run l - 1 times:
    Comparison
    Subtraction

Loop inside code will run l - 2 times:
    IF statement:
        Dereference
            Addition
        Comparison
        Dereference
            Addition
            Addition
    Assignment
    Dereference
        Addition
    Dereference
        Addition
    Assignment
    Dereference
        Addition
        Addition
    Dereference
        Addition
        Addition
    Assignment
    Decrement

    OR

    ELSE statement:
        Increment

最终，我想出了 O(n) 其中：

Worst case = 3 + [2 * (l - 1)] + [6 * (l - 2)] + [14 * (l - 2)]
    O(22n - 39)
    O(n)
Best case = 3 + [2 * (l - 1)] + [6 * (l - 2)] + (l - 2)
    O(9n - 13)
    O(n)

Answer 1

抱歉，没有比 O(n log n) 更好的排序算法，除非您对输入设置一些限制。

目前此代码无效。

例如，如果第一个元素大于第二个元素（在您的示例中就是这种情况），则 i 递减。最初 i=0，所以现在 i=-1。循环重新开始，您尝试访问 a[-1]，并且发生分段错误。错误是

Then I decrement so as to keep current index same.

事实并非如此，正如您所说，索引会递减，因此不会保留该值。

This is the ouput

编辑：

即使纠正了这种情况，以下也不正确

Loop inside code will run l - 2 times:

该算法总是试图将第 (i+1) 个元素放到正确的位置，最坏的情况下将它带到第一个位置。

当index == 0时，您最多交换一次。当 index == 1 时，您最多进行两次交换。当index == 2时，你最多交换3次。

这种情况会发生，直到您到达数组的末尾。所以，1x2x3x...x(n-1)，即 O(n²)

识别这种形式的排序算法并计算其时间复杂度

Identifying this form of sorting algorithm and calculating its time complexity

c

algorithm

sorting

time-complexity

big-o