如何在C中创建一个可以接受任何类型数组的冒泡排序？

yqyhoc1h  于 2023-10-16  发布在  其他
关注(0)|答案(3)|浏览(101)

我们正在尝试创建一个冒泡排序，可以接受int，float或c-string数组。我们已经编写了允许我们这样做的交换函数，但是现在我们不知道如何让它与冒泡排序一起工作。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>

void swapG(void* a, void* b, int elemSize)
{
    void* temp = (char*)malloc(sizeof(char) * elemSize);
    assert(temp != NULL);
    memcpy(temp, a, elemSize);
    memcpy(a, b, elemSize);
    memcpy(b, temp, elemSize);

    free(temp);
}

void bubbleSort(void* arr[], int n, int elemSize)
{
    int i, j;
    bool swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = false;
        for (j = 0; j < n - i - 1; j++) {
            if (&arr[j] > &arr[j + 1]) {
                swapG(&arr[j], &arr[j + 1], elemSize);
                swapped = true;
            }
        }
        if (swapped == false)
            break;
    }

    for (int i = 0; i < n; i++)
        printf(&arr[i]);
}

int main()
{
    int* arr[] = { 0,1,4,6,9,10,13,7 };
    bubbleSort(arr, 8, sizeof(int));
    return 0;
}
c

3条答案

按热度按时间
vc9ivgsu

vc9ivgsu1#

为排序函数定义一个函数指针参数，如下所示：

int (*comparison_function)(void *, void *)

这是一个比较数组中两个元素的函数。你可以这样称呼它：

(*comparison_function)(argument_1, argument_2);

现在你只需要为每种类型定义不同的函数，当你调用你的排序函数时，像这样传递比较函数名：

((*)(void *, void *)) comparrison_function
赞(0）分享  回复(0）举报  2023-10-16
avwztpqn

avwztpqn2#

这种方法的问题是基础类型没有被抽象。这不仅仅是添加elemSize的问题。题外话：camelCase是如此如此的java ;）为什么不只是size和size_t？

void bubbleSort(int* arr[], size_t size)

数据可以是Array，封装大小和任何有用的元数据，如

typedef struct
{
    size_t size;
    int*   arr;
}  Array;

无论如何，我认为这个问题是一个有趣的问题，我将在下面留下一种方法来做到这一点，因为它是非常常见的需要排序或只是处理数组的不同的东西。
我会写我的代码，所以这将是一个很长的职位，结束了一个完整的程序，排序的3种类型，并显示如何封装行为在C使排序的数组排序排序的 * 对象 *。

首先，我们需要bubble_sort

首先需要的是一个有效的冒泡排序实现。让我们试试这个常见的：

int bubble_sort(int vector[], int N)
{
    int step = 0;
    int el   = 0;
    int temp = 0;

    for (step = 0; step < N - 1; step = step + 1)
    {
        int changed = 0;  // no change
        for (el = 0; el < (N - 1 - step); el = el + 1)
        {
            if (vector[el] > vector[el + 1])
            {
                temp          = vector[el];
                vector[el]     = vector[el + 1];
                vector[el + 1] = temp;
                changed    = 1;
            }  // if
        }      // for
        if (changed == 0)
            return step + 1;  
    }                         
    return step + 1; // number of swaps
};

这个函数返回为对数组排序而进行的交换次数。这不重要
我们需要测试一下。是否可以不打印数组之前和之后？不。我们希望：数组被排序。

int show_int(int arr[], int N, const char* msg)
{
    if (msg != NULL) printf("%s", msg);
    printf("%d elements\n", N);
    for (size_t i = 0; i < N; i += 1) printf("%d ", arr[i]);
    printf("\n\n");
    return 0;
};

所以上面的8行可以帮助：它显示了数组，并允许一个可选的方便消息，因此在测试过程中不需要对printf编写几十个调用。

第一个测试，使用int

int main(void)
{
    int arr[] = {2, 4, 6, 8, 1, 3, 5, 7};
    show_int(arr, 8, "before sort: ");
    bubble_sort(arr, 8);
    show_int(arr, 8, "after sort: ");
    return 0;
}

和输出

before sort: 8 elements
2 4 6 8 1 3 5 7

after sort: 8 elements
1 2 3 4 5 6 7 8

这是伟大的，因为我们几乎没有做什么，有一个功能和测试。

返回bubble_sort

如果我们想对int，float或char*进行排序，则使用相同的算法。看看代码，我们需要知道

  • 如何交换2个itens：
temp          = vector[el];
            vector[el]     = vector[el + 1];
            vector[el + 1] = temp;
            changed    = 1;
  • 如何比较2个项目：
if (vector[el] > vector[el + 1])

这就是我们所需要的

提取操作

把这些从bubble_sort()中弄出来会很难吗？
考虑：

int cmp_int(int a, int b)
{
    return a > b;
};

void swap_int(int* a, int* b)
{
    int temp = *a;
    *a       = *b;
    *b       = temp;
    return;
};

好吧，别太用力。返回bubble_sort：

int bubble_sort(int vector[], int N)
{
    int step = 0;
    int el   = 0;
    int temp = 0;

    for (step = 0; step < N - 1; step = step + 1)
    {
        int changed = 0;  // no change
        for (el = 0; el < (N - 1 - step); el = el + 1)
            if (cmp_int(vector[el],vector[el + 1]))
            {
                swap_int(vector+el,vector+el+1);
                changed = 1;
        }
        if (changed == 0) return step + 1;
    }
    return step + 1;  // number of swaps
}

它像以前一样工作。好

使swap和compare通用

因为我们想要对不同的东西进行排序，比如病历、图书馆里的书、票、int、字符串，所有常见的学生的东西，让我们将cmp_int和swap改为只使用void*，没有类型。

cmp_int

如果我们有两个void*指向原来的int s...

int cmp_int(void* one, void* other)
{
    int a = *(int*)one;
    int b = *(int*)other;
    return a > b;
};

swap_int

如果swap_int参数也是void*，我们可以使用

void swap_int(void* one, void* other)
{
    int* a    = one;
    int* b    = other;
    int  temp = *a;
    *a        = *b;
    *b        = temp;
    return;
};

当然，不需要这么多行和变量，但无论如何有6行。

bubble_sort使用新的swap和compare

int bubble_sort(int vector[], int N)
{
    int step = 0;
    int el   = 0;
    for (step = 0; step < N - 1; step = step + 1)
    {
        int changed = 0;  // no change
        for (el = 0; el < (N - 1 - step); el = el + 1)
            if (cmp_int(
                    (void*)(vector + el),
                    (void*)(vector + el + 1)))
            {
                swap_int((void*)(vector + el),(void*)(vector + el + 1));
                changed = 1;
            }
        if (changed == 0) return step + 1;
    }
    return step + 1;  // number of swaps
}

它像以前一样工作。还是很好
但是现在bubble_sort不知道它正在排序的数组中的东西的类型。只有swap_int和cmp_int是重要的。让我们换个名字：

int bubble_sort(int vector[], int N)
{
    int step = 0;
    int el   = 0;
    for (step = 0; step < N - 1; step = step + 1)
    {
        int changed = 0;  // no change
        for (el = 0; el < (N - 1 - step); el = el + 1)
            if (cmp(
                    (void*)(vector + el),
                    (void*)(vector + el + 1)))
            {
                swap((void*)(vector + el),(void*)(vector + el + 1));
                changed = 1;
            }
        if (changed == 0) return step + 1;
    }
    return step + 1;  // number of swaps
}

但是向量仍然被声明为int[]，这不是泛型。我们开始改变这一切.
我们只有swap和cmp。有两个具有类似签名的函数：

int  cmp(void*, void*);
    void swap(void*, void*);

那么，如果我们将这两个函数作为参数传递给bubble_sort呢？
C就是为这类事情而设计的。
让我们看看：

bubble_sort()获取2个新参数

int  bubble_sort(int[], int N,
     int (*)(void*, void*),
    void (*)(void*, void*)
    );

现在我们可以将自定义的cmp和swap传递给bubble_sort，以我们的方式进行排序。

更改main以提供新参数

这只是提供要使用的函数的问题：

int main(void)
{
    int arr[] = {2, 4, 6, 8, 1, 3, 5, 7};
    show_int(arr, 8, "before sort: ");
    bubble_sort(arr, 8, cmp_int, swap_int);
    show_int(arr, 8, "after sort: ");
    return 0;
}

输出

before sort: 8 elements
2 4 6 8 1 3 5 7

after sort: 8 elements
1 2 3 4 5 6 7 8

是一样的，肯定的。还是很好

我们是否已经对double数组进行了排序？

当然，这是一回事。但是我们仍然有bubble_sort的第一个参数作为int[]。不好
我们还没到那一步。让我们将bubble_sort()更改为

int bubble_sort(
    char* array, size_t el_size, size_t N, int (*cmp)(void*, void*),
    void (*swap)(void*, void*));

所以我们可以把数组作为地址和偏移量来操作，毕竟所有的数组都是这样。
C就是为了处理这种东西而设计的：系统缓冲器、进程间消息、消息队列等。
array是基地址，el_size用于在array内存块上进行寻址。剩下的就是我们所拥有的：bubble sort（冒泡排序）

bubble_sort()通用，共20行

此版本不知道数组中有什么：

int bubble_sort(
    char* arr, size_t el_size, size_t N,
    int (*cmp)(void*, void*), void (*swap)(void*, void*))
{
    int    step = 0;
    size_t el   = 0;
    for (step = 0; step < N - 1; step += 1)
    {
        char* offset  = arr;
        int   changed = 0;  // no change
        for (el = 0; el < (N - 1 - step);
             el += 1, offset += el_size)
            if (cmp(offset, offset + el_size))
            {
                swap(offset, offset + el_size);
                changed = 1;
            }
        if (changed == 0) return step + 1;
    }
    return step + 1;  // number of swaps
}

它与前面的代码相同，但swap和cmp是参数，arr是数组，el_size是每个元素的大小。
在某种意义上，它是一个“对象”：用户需要传递数据和对数据进行操作的方法。
实际上，这只是一个从一种类型复制和粘贴到另一种类型的问题。

实现双精度和字符串的swap和compare

int   cmp_int(void*, void*);
void  swap_int(void*, void*);

int   cmp_double(void*, void*);
void  swap_double(void*, void*);

int   cmp_string(void*, void*);
void  swap_string(void*, void*);

就像这样当然，对于Tickets，Patient，无论我们需要操作什么数据，都是一样的。这是OOP，一如既往。

这些函数的实现

int cmp_int(void* one, void* other)
{
    int a = *(int*)one;
    int b = *(int*)other;
    return a > b;
};

void swap_int(void* one, void* other)
{
    int* a    = one;
    int* b    = other;
    int  temp = *a;
    *a        = *b;
    *b        = temp;
    return;
}

// functions for double

int cmp_double(void* one, void* other)
{
    double a = *(double*)one;
    double b = *(double*)other;
    return a > b;
}

void swap_double(void* one, void* other)
{
    double* a    = one;
    double* b    = other;
    double  temp = *a;
    *a           = *b;
    *b           = temp;
    return;
}

// functions for strings

int cmp_string(void* one, void* other)
{
    char** a   = one;
    char** b   = other;
    int   res = strcmp(*a, *b);
    return res > 0;
}

void swap_string(void* one, void* other)
{
    if (one == NULL) return;
    if (other == NULL) return;
    char** a = one;
    char** b = other;
    char* temp = *a;  // save now
    *a         = *b;
    *b         = temp;
    return;
};

这就是我们所需要的需要排序新类型？只写swap和compare。

抽象show方法：打印任何类型

这是 javatoString，C++<< override方法.
在这个例子中，

int show(int arr[], int N, const char* msg)
{
    if (msg != NULL) printf("%s", msg);
    printf("%d elements\n", N);
    for (size_t i = 0; i < N; i += 1) printf("%d ", arr[i]);
    printf("\n\n");
    return 0;
};

而且很有效。但是使用%d打印元素，并迭代int[]数组。不好
如果用户可以告诉我们如何显示一个元素，那么我们就可以在show()中使用它。* 物体的力量 *

show一个int：7条线路

考虑一个函数，如

char* show_int(void* p)
{
    char* str = malloc(30);
    if (str == NULL) return NULL;
    int res = snprintf(str, 30, "%d", *(int*)p);
    return str;
}

适用于int：只是返回一个表示其值的字符串。但我们可以将其更改为使用double：

复制并粘贴到show一个双精度：7条线路

char* show_double(void* p)
{
    char* str = malloc(50);
    if (str == NULL) return NULL;
    int res = snprintf(str, 30, "%f", *((double*)p));
    return str;
}

复制并粘贴到show一个字符串：10行

char* show_string(void* p)
{
    char** a = p;
    if (p == NULL) return NULL;
    size_t len = 1 + strlen((char*)*a);
    char*  str = malloc(len);
    if (str == NULL) return NULL;
    strcpy(str, (char*)*a);  // copy to output
    return str;
}

将show更改为适用于任何类型：19条线路

int show(
    char* arr, size_t elem_size, size_t N,
    char* (*show_one)(void*), const char* msg)
{
    if (msg != NULL) printf("%s", msg);
    printf("%llu elements\n", N);
    char* pStr   = NULL;
    char* offset = arr;
    for (size_t i = 0; i < N; i += 1)
    {
        pStr = show_one(offset);
        printf("%s ", pStr);
        free(pStr);
        offset += elem_size;
    }
    printf("\n\n");
    return 0;
};

**这与bubble_sort中使用的方法相同：把数据看作一个对象，用户只需要为3个函数提供代码，我们就可以对任何东西进行排序。我们还可以在屏幕上显示任何数据，因为show获得了一个用户提供的 virtual 函数来显示元素。

一个完整的例子：main.c

int main(void)
{
    // int
    int arr[] = {2, 4, 6, 8, 1, 3, 5, 7};
    show(
        (char*)arr, sizeof(int), 8, show_int,
        "before sort: ");
    bubble_sort(
        (char*)arr, sizeof(int), 8, cmp_int, swap_int);
    show(
        (char*)arr, sizeof(int), 8, show_int,
        "after sort: ");

    // double
    double f_arr[] = {1.2, 1.4, 1.6, 1.8,
                      1.1, 1.3, 1.5, 1.7};
    show(
        (char*)f_arr, sizeof(double), 8, show_double,
        "before sort: ");
    bubble_sort(
        (char*)f_arr, sizeof(double), 8, cmp_double,
        swap_double);
    show(
        (char*)f_arr, sizeof(double), 8, show_double,
        "after sort: ");

    // string
    char* str_arr[] = {"Bravo", "Delta", "Fox", "Hotel",
                       "Alpha", "Charlie", "Eco", "Golf"};
    show(
        (char*)str_arr, sizeof(char*), 8, show_string,
        "before sort: ");
    bubble_sort(
        (char*)str_arr, sizeof(double), 8, cmp_string,
        swap_string);
    show(
        (char*)str_arr, sizeof(double), 8, show_string,
        "after sort: ");
    return 0;
}

这段代码，使用复制和粘贴，声明了一个排序3个数组int，double和char*。几乎和我们说的一样。

此程序的输出：分类所有3种类型

和printing功能相同

before sort: 8 elements
2 4 6 8 1 3 5 7

after sort: 8 elements
1 2 3 4 5 6 7 8

before sort: 8 elements
1.200000 1.400000 1.600000 1.800000 1.100000 1.300000 1.500000 1.700000

after sort: 8 elements
1.100000 1.200000 1.300000 1.400000 1.500000 1.600000 1.700000 1.800000

before sort: 8 elements
Bravo Delta Fox Hotel Alpha Charlie Eco Golf

after sort: 8 elements
Alpha Bravo Charlie Delta Eco Fox Golf Hotel

C完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int bubble_sort(
    char*, size_t el_size, size_t N, int (*)(void*, void*),
    void (*)(void*, void*));

int   cmp_int(void*, void*);
void  swap_int(void*, void*);

int   cmp_double(void*, void*);
void  swap_double(void*, void*);

int   cmp_string(void*, void*);
void  swap_string(void*, void*);

char* show_int(void*);
char* show_double(void*);
char* show_string(void*);

int show(
    char*, size_t, size_t, char* (*)(void*), const char*);

int main(void)
{
    // int
    int arr[] = {2, 4, 6, 8, 1, 3, 5, 7};
    show(
        (char*)arr, sizeof(int), 8, show_int,
        "before sort: ");
    bubble_sort(
        (char*)arr, sizeof(int), 8, cmp_int, swap_int);
    show(
        (char*)arr, sizeof(int), 8, show_int,
        "after sort: ");

    // double
    double f_arr[] = {1.2, 1.4, 1.6, 1.8,
                      1.1, 1.3, 1.5, 1.7};
    show(
        (char*)f_arr, sizeof(double), 8, show_double,
        "before sort: ");
    bubble_sort(
        (char*)f_arr, sizeof(double), 8, cmp_double,
        swap_double);
    show(
        (char*)f_arr, sizeof(double), 8, show_double,
        "after sort: ");

    // string
    char* str_arr[] = {"Bravo", "Delta", "Fox", "Hotel",
                       "Alpha", "Charlie", "Eco", "Golf"};
    show(
        (char*)str_arr, sizeof(char*), 8, show_string,
        "before sort: ");
    bubble_sort(
        (char*)str_arr, sizeof(double), 8, cmp_string,
        swap_string);
    show(
        (char*)str_arr, sizeof(double), 8, show_string,
        "after sort: ");
    return 0;
}

int bubble_sort(
    char* arr, size_t el_size, size_t N,
    int (*cmp)(void*, void*), void (*swap)(void*, void*))
{
    int    step = 0;
    size_t el   = 0;
    for (step = 0; step < N - 1; step += 1)
    {
        char* offset  = arr;
        int   changed = 0;  // no change
        for (el = 0; el < (N - 1 - step);
             el += 1, offset += el_size)
            if (cmp(offset, offset + el_size))
            {
                swap(offset, offset + el_size);
                changed = 1;
            }
        if (changed == 0) return step + 1;
    }
    return step + 1;  // number of swaps
}

// functions for int

int cmp_int(void* one, void* other)
{
    int a = *(int*)one;
    int b = *(int*)other;
    return a > b;
};

void swap_int(void* one, void* other)
{
    int* a    = one;
    int* b    = other;
    int  temp = *a;
    *a        = *b;
    *b        = temp;
    return;
}

// functions for double

int cmp_double(void* one, void* other)
{
    double a = *(double*)one;
    double b = *(double*)other;
    return a > b;
}

void swap_double(void* one, void* other)
{
    double* a    = one;
    double* b    = other;
    double  temp = *a;
    *a           = *b;
    *b           = temp;
    return;
}

// functions for strings

int cmp_string(void* one, void* other)
{
    char** a   = one;
    char** b   = other;
    int   res = strcmp(*a, *b);
    return res > 0;
}

void swap_string(void* one, void* other)
{
    if (one == NULL) return;
    if (other == NULL) return;
    char** a = one;
    char** b = other;
    char* temp = *a;  // save now
    *a         = *b;
    *b         = temp;
    return;
};

char* show_int(void* p)
{
    char* str = malloc(30);
    if (str == NULL) return NULL;
    int res = snprintf(str, 30, "%d", *(int*)p);
    return str;
}

char* show_double(void* p)
{
    char* str = malloc(50);
    if (str == NULL) return NULL;
    int res = snprintf(str, 30, "%f", *((double*)p));
    return str;
}

char* show_string(void* p)
{
    char** a = p;
    if (p == NULL) return NULL;
    size_t len = 1 + strlen((char*)*a);
    char*  str = malloc(len);
    if (str == NULL) return NULL;
    strcpy(str, (char*)*a);  // copy to output
    return str;
}

// show anything
int show(
    char* arr, size_t elem_size, size_t N,
    char* (*show_one)(void*), const char* msg)
{
    if (msg != NULL) printf("%s", msg);
    printf("%llu elements\n", N);
    char* pStr   = NULL;
    char* offset = arr;
    for (size_t i = 0; i < N; i += 1)
    {
        pStr = show_one(offset);
        printf("%s ", pStr);
        free(pStr);
        offset += elem_size;
    }
    printf("\n\n");
    return 0;
};
赞(0）分享  回复(0）举报  2023-10-16
hsgswve4

hsgswve43#

不要忽略编译器警告

您似乎忽略了来自编译器的警告。
首先，print语句

printf(&arr[i]);

无效，因为第一个参数不是格式字符串。
第二，初始化声明：

int* arr[] = { 0,1,4,6,9,10,13,7 };

无效，因为初始化器列表包含int，但您正在尝试初始化int*数组。

您的函数只接受void*数组

在你的问题中，你问：
我们正在尝试创建一个可以接受int，float或c字符串数组的冒泡排序。
你的冒泡排序函数有以下原型：
void bubbleSort(void* arr[], int n, int elemSize);
即使你的意图是传递一个指针数组，你的函数也无法完成你想要的任务。虽然指向某种类型T的指针可以转换为void *，反之亦然，但在T*数组到void*数组之间没有这种有效的转换。类型不兼容。
它的本质是void*（和char*）允许比T*宽。

利用现有解决方案作为模板进行跟踪

有一个原型，你可以模仿做你想做的事情。这就是标准的C函数qsort

void qsort(void *base, size_t nmemb, size_t size,
           int (*compare)(const void *, const void *));

我们注意到这个原型和为冒泡排序生成的原型之间有两个不同之处。首先，数组指针被表示为单个void*，而不是数组。其次，要使用的比较函数作为另一个参数传入。
第一个区别是允许函数接受任何类型的数组。在C中，表达式中使用的T类型数组的对象（除了少数例外）将衰减为具有指向T的类型指针，其第一个数组成员的地址值。然后，这个指针值自然地转换为标准C所允许的void*。
第二个区别允许你传入不同的比较函数来适应不同类型的数组。因此，float数组需要使用与C字符串数组不同的比较函数。
因此，您的冒泡排序函数可能更像qsort

void bubbleSort(void *arr, int n, int elemSize,
                int (*Compare)(const void *, const void *))

如何使用比较功能

有很多关于如何正确使用qsort的资源。但是，简而言之，最棘手的部分是理解如何编写正确的比较函数。不过，唯一的技巧是比较函数的参数是传递给qsort的数组元素的指针。如果第一个参数小于第二个参数，则比较函数返回负值，如果它们相等，则返回0，否则返回正值。
因此，如果sort函数传递了一个int s的数组：

int arr[] = { 1, 2, 3 };
    qsort(arr, 3, sizeof(int), cmp_int);

然后，比较函数可能看起来像这样：

int cmp_int (const void *a, const void *b) {
    const int *aa = a;
    const int *bb = b;
    return (*aa < *bb) ? -1 : (*aa > *bb);
}

如果sort函数被传递了一个指针数组，那么你需要记住比较函数的每个参数都是指向一个指针的指针。这就是C字符串排序的情况。

const char *arr[] = { "world", "hello", "this" };
    qsort(arr, 3, sizeof(const char *), cmp_string);

所以比较函数的实现可能看起来像这样：

int cmp_string (const void *a, const void *b) {
    const char * const *aa = a;
    const char * const *bb = b;
    return strcmp(*aa, *bb);
}

将void*视为元素数组

要将arr参数视为数组，可以使用char*指针指向第 i_个元素的位置，并进行偏移量计算。

char * const arr2 = arr;
    ...
    void *p = &arr2[i * elemSize];

如果你的编译器支持VLA扩展，你可以使用它来使索引更自然一些。

char (* const arr2)[elemSize] = arr;
    ...
    void *p = &arr2[i];

改进泛型交换

您实现了一个通用交换，但它有点昂贵。在任何排序算法中，交换操作都应该尽可能高效。但是，您已经将调用malloc和free的开销添加到每个交换中。
处理这个问题的一种方法是在排序开始时只为swap临时分配一个空间，并在排序完成时释放它。

void bubbleSort(void *arr, int n, int elemSize,
                int (*Compare)(const void *, const void *)) {

    void *temp = malloc(elemSize);
    assert(temp != NULL);

    //...

    free(temp);
}

现在，您可以修改swap函数以接受临时变量，而不是为自己分配一个临时变量。

static inline void swapG(void* a, void* b, int elemSize, void *temp) {
    memcpy(temp, a, elemSize);
    memcpy(a, b, elemSize);
    memcpy(b, temp, elemSize);
}

为了进一步优化分配，您可以创建一个固定大小的缓冲区用于交换，并且仅在元素大小太大而无法容纳时进行分配。

void bubbleSort(void *arr, int n, int elemSize,
                int (*Compare)(const void *, const void *)) {

    char tempbuf[256];
    void *temp = tempbuf;

    if (elemSize > sizeof(tempbuf)) {
        temp = malloc(elemSize);
        assert(temp != NULL);
    }

    //...

    if (temp != tempbuf)
        free(temp);
}

我们不讨论冒泡排序

冒泡排序算法本身并不是你应该花很多时间学习的东西，所以我不会在这个答案中讨论它的实现细节。

selection sort 怎么样？

一个更有效的排序算法是 * 选择排序 *，它像冒泡排序一样将最大的元素放在最后。选择排序的工作原理是识别感兴趣的子数组中最大的元素，并将其放置到数组的最后一个位置。归纳步骤是将数组大小减少1，停止条件是当数组剩余的元素少于2个时。
N元数组的算法

  • 设E = N
  • 当E > 1时
  • 找到I使得Array[I] >= Array[x] for all x in [0..E）
  • 交换数组[I]和数组[E-1]
  • 设E = E - 1

使用此算法，您仍然可以保持不变，即在收缩数组时对数组的最后一部分进行排序。虽然函数现在命名错误，但算法本身并不那么愚蠢。

void selectionSort(void *arr, int n, int elemSize,
                   int (*Compare)(const void *, const void *)) {

    char tempbuf[256];
    void *temp = tempbuf;

    if (elemSize > sizeof(tempbuf)) {
        temp = malloc(elemSize);
        assert(temp != NULL);
    }

    char (* const Array)[elemSize] = arr;

    int E = n;
    while (E > 1) {
        int I = 0;
        for (int i = 1; i < E; ++i) {
            if (Compare(&Array[i], &Array[I]) > 0) I = i;
        }
        swapG(&Array[I], &Array[E-1], elemSize, temp);
        --E;
    }

    if (temp != tempbuf)
        free(temp);
}

// Not really the bubble sort
void bubbleSort(void *arr, int n, int elemSize,
                int (*Compare)(const void *, const void *)) {
    selectionSort(arr, n, elemSize, Compare);
}

* 插入排序 * 怎么样？

  • 插入排序 * 通常被认为是对未知大小的小数组最有效的排序。它的工作原理是将下一个未排序的元素插入到已经排序的子数组的正确相对位置。

该算法的结果是临时不用于交换，而是在定位到感兴趣的元素的正确位置时保持其值。一旦定位，元素将向上移动，为感兴趣的值腾出空间。小数组的数组元素移动被认为是高效的，因为它可以完全在缓存中完成，并且机器通常硬编码优化函数来执行该操作。
N元数组的算法

  • 设S = 1
  • 当S < N
  • String [S]：String [S]
  • alias Array[-1] = temp
  • 在[-1，S]中找到最大的I，使得Array[S] >= Array[x] for x in [-1，I]
  • move Array[I+1.. S-1]到Array[I+2.. S]
  • let Array[I+1]
  • 设S = S + 1

还有其他方法来描述算法，但上面的代码相当简单：

void insertionSort(void *arr, int n, int elemSize,
                   int (*Compare)(const void *, const void *)) {

    char tempbuf[256];
    void *temp = tempbuf;

    if (elemSize > sizeof(tempbuf)) {
        temp = malloc(elemSize);
        assert(temp != NULL);
    }

    char (* const Array)[elemSize] = arr;

    for (int S = 1; S < n; ++S) {
        memcpy(temp, &Array[S], elemSize);
        int I = -1;
        if (Compare(temp, &Array[0]) >= 0) {
            I = S-1;
            while (Compare(temp, &Array[I]) < 0) --I;
        }
        memmove(&Array[I+2], &Array[I+1], (S-I-1)*elemSize);
        memcpy(&Array[I+1], temp, elemSize);
    }

    if (temp != tempbuf)
        free(temp);
}

// Not really the bubble sort
void bubbleSort(void *arr, int n, int elemSize,
                int (*Compare)(const void *, const void *)) {
    insertionSort(arr, n, elemSize, Compare);
}

排序了吗？

在编写排序例程之后，可以使用验证器函数验证它是否已排序。这样的函数只会扫描数组元素，并确保连续的元素彼此小于或等于。

void verifySort(void *arr, int n, int elemSize,
                int (*Compare)(const void *, const void *)) {

    char (* const Array)[elemSize] = arr;

    for (int i = 1; i < n; ++i) {
        assert(Compare(&Array[i-1], &Array[i]) <= 0);
    }
}
赞(0）分享  回复(0）举报  2023-10-16
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com