c - 选择排序和在 C 中使用 findMin 方法的问题

Question

所以我对用 C 语言编写的选择排序有疑问。当在一个函数中实现时，我可以让选择排序发挥作用。但是，当我执行作业要求的操作并使用返回数组的最小索引的 findMin 函数时，它不会完全对其进行排序。我尝试使用打印语句对其进行调试，但我似乎无法弄清楚出了什么问题。

这是我与 findMin 方法一起使用的排序方法:

void sortMin2(int A[]) {
    int outer;
    int minIndex;
    for(outer = 0; outer < 5; outer++) {
        minIndex = findMin(A, outer, 5);
        if(minIndex != outer) {
                swap(&A[minIndex], &A[outer]);
        }//end if
    } // end for
}

int findMin(int A[], int i, int j) {
    int k; // for loop
    int index = 0;
    for(k = (i + 1); k < (j+1); k++) {
        if(A[k] < A[index]) {
            index = k;
        } // end if
    } // end for
    return index;
} // end findMin

void swap(int *i, int *j) {
    int temp = *i;
    *i = *j;
    *j = temp;
} // end swap

这是我在五个值的数组上运行它时的输出:

Array Before: 4, 10, 9, 1, 3, 
4, 10, 9, 1, 3, 
1, 10, 9, 4, 3, 
10, 1, 9, 4, 3, 
10, 1, 3, 4, 9, 
10, 1, 3, 9, 4, 
Array after: 4, 1, 3, 9, 10, 

现在，这是我的选择排序方法，它确实可以查找(即正确排序)。

void selectionSort2(int A[]) {
    int outer; // for loops
    int inner;
    int minimum = 0;
    //int minIndex = 0;
    for(outer = 0; outer < 5; outer++) {
        //minIndex = findMin(A, 0, 19);
        minimum = outer;
        for(inner = outer + 1; inner < 5; inner++) {
            if(A[minimum] > A[inner]) {
                minimum = inner;
            } // end if
        } // end inner for

        if(minimum != outer) {
            swap(&A[minimum], &A[outer]);
        } // end if
    } // end outer for
}

有人明白为什么我的 sortMin2 函数实际上没有对它进行排序吗？

Answer 1

代码中的某些内容并不正确。

为什么在 findMin(...)方法，for循环有k < (j+1)作为终止条件。你不觉得，应该是k < j ？自 j + 1将导致6 ，因此循环将持续到 j = 5 ，这将导致未定义的行为(因为它超出了数组 A 的边界)。数组索引从 0 开始。由于大小是 5 ，因此索引的范围为 0 - 4 .

此外，index的值永远不会改变。它总是从 0 开始在每次迭代中。相反，它应该是 int index = i ，在 findMin(...) 内函数，如Selection Sort我们找到最小的元素，并将其放在左侧，正确的位置，因此下一次，我们从一个位置开始，比这个位置早一个。

在 sortMin2(...) 里面函数，您未能调用 swap(...) ，以防您有新的索引来交换值。

这是代码片段的修改版本:

int findMin(int A[], int i, int j) {
    int k; // for loop
    int index = i;
    for(k = (i + 1); k < (j); k++) {
        if(A[k] < A[index]) {
            index = k;
        } // end if
    } // end for
    return index;
} // end findMin

void swap(int *i, int *j) {
    int temp = *i;
    *i = *j;
    *j = temp;
} // e

void display(int A[])
{
    int i = 0;
    for (i = 0; i < 5; ++i)
        printf("%d\t", A[i]);
    printf("\n");
}

void sortMin2(int A[]) {
    int outer = 0;
    int minIndex = -1;
    for(outer = 0; outer < 5; outer++) {
        minIndex = findMin(A, outer, 5);
        if(minIndex != outer) {
            swap(&A[minIndex], &A[outer]);
            display(A);
        }//end if
    } // end for
}