我的“插入排序”正确吗？

Question

我正在用C编写一个插入排序代码，这段代码非常有效。但我有点困惑，我的实现是否正确的插入排序。

//insertion sort algorithm
#include <stdio.h>
#include <stdlib.h>

void insertion_sort(int size, int *arr);

int main(void)
{
    int *array;
    int size;

    printf("enter the amount of data: ");
    scanf("%d", &size);

    array = (int*)malloc(sizeof(int) * size);

    for(int i = 0; i < size; ++i)
    {
        scanf("%d", &array[i]);
    }

    insertion_sort(size, array);

    for(int i = 0; i < size; ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

void insertion_sort(int size, int *arr)
{
    for(int i = 0; i < size; ++i)
    {
        if(i == 0)
        {
            continue;
        }
        else if(arr[i] < arr[i - 1])
        {
            int temp;
            temp = arr[i];
            arr[i] = arr[i - 1];
            arr[i - 1] = temp;

            i -= 2;

            //with this testing, you can see the number while the data still sorted
            /* for(int j = 0; j < size; ++j) */
            /* { */
            /*  printf("%d ", arr[j]); */
            /* } */
            /* printf("\n"); */
        }
        else
        {
            //do nothing
        }
    }
}

Answer 1

看看维基百科。它展示了插入排序的两个实现：

1. 交换插入排序，
2. 更快的插入排序。

在C中，(1)似乎是：

static void swap(int* arr, size_t higher_index) {
    int tmp = arr[higher_index];
    arr[higher_index] = arr[higher_index - 1];
    arr[higher_index - 1] = tmp;
}

void insertion_sort_v2(int* arr, size_t size) {
    for (size_t i = 1; i < size; ++i) {
        size_t j = i;

        while (j > 0 && arr[j - 1] > arr[j]) {
            swap(arr, j);
            --j;
        }
    }
}

(2)似乎：

void insertion_sort_v3(int* arr, size_t size) {
    for (size_t i = 1; i < size; ++i) {
        int x = arr[i];
        size_t j = i - 1;

        while (j >= 0 && arr[j] > x) {
            arr[j + 1] = arr[j];
            --j;
        }

        arr[j + 1] = x;
    }
}

(2)比(1)更有效，因为它使每个元素移动一次赋值。((1)进行由3项转让组成的交换。)

通知1

我相信更习惯的论点列表可能是insertion_sort(int* array, size_t size)。

建议2

现在，回到你的代码。

if(i == 0)
{
    continue;
}

您可以从循环索引i = 1开始省略上述内容。顺便说一下，循环索引i的类型应该是size_t，而不是int。

建议3

if(arr[i] < arr[i - 1])

所以，arr[i]在右边，arr[i - 1]在数组的左边。为什么不换个顺序让它更易读呢？另外，在if和条件打开(之间应该有一个单独的空间：

if (arr[i - 1] > arr[i])

建议4

else
{
    //do nothing
}

这完全没必要。把它处理掉。

苏木兰(

Summa summarum

)

#define _CRT_SECURE_NO_WARNINGS /* Visual Studio 2022 specific */
#define N 50000
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void insertion_sort(int size, int* arr);
void insertion_sort_v2(int* arr, size_t length);
void insertion_sort_v3(int* arr, size_t length);

static size_t millis() {
    return clock() / (CLOCKS_PER_SEC / 1000);
}

static int arrays_equal(int* array1, int* array2, size_t length) {
    for (size_t i = 0; i < length; ++i) {
        if (array1[i] != array2[i]) {
            return 0;
        }
    }

    return 1;
}

static int array_is_sorted(int* array, size_t length) {
    for (size_t i = 0; i < length - 1; ++i) {
        if (array[i] > array[i + 1]) {
            return 0;
        }
    }

    return 1;
}

static void benchmark() {
    int* array1 = malloc(sizeof(int) * N);
    int* array2 = malloc(sizeof(int) * N);
    int* array3 = malloc(sizeof(int) * N);

    srand(4);

    for (size_t i = 0; i < N; ++i) {
        array1[i] = array2[i] = array3[i] = rand();
    }

    size_t start_time = millis();
    insertion_sort(N, array1);
    size_t end_time = millis();
    printf("OP insertion sort in %d milliseconds.\n", end_time - start_time);

    start_time = millis();
    insertion_sort_v2(array2, N);
    end_time = millis();
    printf("insertion sort v2 in %d milliseconds.\n", end_time - start_time);

    start_time = millis();
    insertion_sort_v3(array3, N);
    end_time = millis();
    printf("insertion sort v3 in %d milliseconds.\n", end_time - start_time);

    int equal = arrays_equal(array1, array2, N) &&
                arrays_equal(array2, array3, N);

    printf("Arrays are equal: %d\n", equal);

    if (equal) {
        printf("Arrays are sorted: %d\n", array_is_sorted(array1, N));
    }
}

int main(void)
{
    int* array;
    int size;

    printf("enter the amount of data: ");
    scanf("%d", &size);

    array = (int*)malloc(sizeof(int) * size);

    for (int i = 0; i < size; ++i)
    {
        scanf("%d", &array[i]);
    }

    insertion_sort_v3(array, size);

    for (int i = 0; i < size; ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    benchmark();

    return 0;
}

void insertion_sort(int size, int* arr)
{
    for (int i = 0; i < size; ++i)
    {
        if (i == 0)
        {
            continue;
        }
        else if (arr[i] < arr[i - 1])
        {
            int temp;
            temp = arr[i];
            arr[i] = arr[i - 1];
            arr[i - 1] = temp;

            i -= 2;

            //with this testing, you can see the number while the data still sorted
            /* for(int j = 0; j < size; ++j) */
            /* { */
            /*  printf("%d ", arr[j]); */
            /* } */
            /* printf("\n"); */
        }
        else
        {
            //do nothing
        }
    }
}

static void swap(int* arr, size_t higher_index) {
    int tmp = arr[higher_index];
    arr[higher_index] = arr[higher_index - 1];
    arr[higher_index - 1] = tmp;
}

void insertion_sort_v2(int* arr, size_t length) {
    for (size_t i = 1; i < length; ++i) {
        size_t j = i;

        while (j > 0 && arr[j - 1] > arr[j]) {
            swap(arr, j);
            --j;
        }
    }
}

void insertion_sort_v3(int* arr, size_t length) {
    for (size_t i = 1; i < length; ++i) {
        int x = arr[i];
        size_t j = i - 1;

        while (j >= 0 && arr[j] > x) {
            arr[j + 1] = arr[j];
            --j;
        }

        arr[j + 1] = x;
    }
}

上述程序输出：

enter the amount of data: 0

OP insertion sort in 1555 milliseconds.
insertion sort v2 in 699 milliseconds.
insertion sort v3 in 338 milliseconds.
Arrays are equal: 0

上面，您可以看到您的实现是不正确的和缓慢的。

希望这能帮上忙。

Answer 2

不要编写，永远不要发布/提交无文档的代码。

我认为您的insertion_sort()没有真实地实现插入排序：

虽然它终止了对第一个非较大值的“插入点”的搜索，

它重新比较了所有的值“刚刚上升”和已知的排序。

有两个循环副本来打印数组中的所有值。

(如果一个被“注释掉”)：

让在一个以上的地方做同样的程序，作为奖励，你可以给它一个名字。

我不喜欢else后面的if (condition) continue; (或break或return)。

在循环中对循环控制变量的操作是意外的，而且很难跟踪--尤其是对于("C系列“) for-loop，只有突破循环才能避免第三个表达式的副作用。