c - 如何实现以下算法以在 c 中对动态数组进行排序？

Question

我试图编写一个简单的排序函数来对 int 数组进行排序，并且研究了一些简单的算法，例如冒泡排序。我编写了以下代码，它可以很好地按升序对 int 数组进行排序:

void bubble_sort(float *scores, int size) {
    int i = 0,j = 0;
    float container = 0;
    for(i = 0; i < size - 1; i++) {
        for(j = 0; j < size - i - 1; j++) {
            if(scores[j] > scores[j + 1]) {
                container = scores[j];
                scores[j] = scores[j + 1];
                scores[j + 1] = container;
            }
        }
    }
}

然后我想到我通常如何对一张纸上的一组整数进行排序，我想为什么不编写一个代码来做同样的事情。但事实证明它并不像我第一眼想的那么简单。 我注意到我通常使用一个简单的算法来按升序对一组整数进行排序，使用以下方法:

假设集合 {4, 8, 1, 9, 0}

• 首先我创建了一个空集，其中有五个空位。 { , , , }
• 我寻找集合中的最小值，在本例中为 0。
• 然后我将它添加到新集合中的第一个空白处: {0, , , , }
• 最后我从原始集合中删除了我使用的元素: {4, 8, 1, 9}
• 我重复上述过程，直到我的原始集合中没有更多元素为止。
• 现在我有一个有序的集合。

所以我继续写了一个可以找到数组中最小值的小函数:

int minimum(int *array, int size) {
    int i, min = array[0];
    for(i = 1; i < size; i++) {
        if(array[i] < min) {
            min = array[i];
        }
    }
    return min;
}

我打算编写一个函数来获取一个数组并对它进行排序，直到我意识到我无法从数组中删除项目。我在这里不知所措，接下来我该怎么办？

Answer 1

您所描述的是一种称为选择排序的排序算法。重复选择最小元素并产生它。您不必执行删除，只需维护一个索引 NEXT，它告诉您应该将数字写入的下一个位置(初始设置为 0)。

所以本质上，您通过将位置 POS 的项目与位置 NEXT 的数字交换来模拟删除该项目。

朴素的实现需要 O(n*n) 时间，因为您遍历列表以找到最小值。更快的选择算法将使用堆结构在 O(lg n) 时间内获得最小值。