我是初学者，正在练习 C 选择排序，但会针对不同的值获得不同的输出

Question

我有以下执行选择排序的代码：

#include<stdio.h>
    int main(){
       //selection_sort(int,int);
       int a[] = {55,932,53,98};
       int n = sizeof(a)/sizeof(a[0]);
    //    printf("%d \n",n);
       
       printf("Array before sorting: ");
       for (int i = 0; i < n; i++){
           printf("%d ", a[i]);
       }
       selection_sort(a,n);
       printf("Array after sorting: ");
       for (int k = 0; k < n; k++){
           printf("%d ", a[k]);
       }
    }
    int selection_sort(int a[], int n){
        int i,j,minidx,tmp;
        //int a[size];
        for (i = 0; i < n - 1 ; i++){
            minidx = i;
            for (j = i + 1; j < n; j++){
                if (a[minidx] > a[j]){
                        minidx = j;
                        swap_elements(&a[minidx], &a[i]);
                }
            }
        }
    }
    int swap_elements(int *a, int *b){
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }

我已经为数组尝试了不同的值，它正在随机化精度。我在做什么不该做的事？

Answer 1

在这个 if 语句中

            if (a[minidx] > a[j]){
                    minidx = j;
                    swap_elements(&a[minidx], &a[i]);
            }

调用函数swap_elements后，索引为minidx的元素不代表当前最小值。它表示存储在 a[i].

中的先前值

实际上，当您在发现小于元素 a[i] 的元素时立即进行交换时，使用您的方法，变量 minidx 只是多余的。你可以改写

            if (a[i] > a[j]){
                    swap_elements(&a[i], &a[j]);
            }

或者你可以这样写

    for (i = 0; i < n - 1 ; i++){
        minidx = i;
        for (j = i + 1; j < n; j++){
            if (a[minidx] > a[j]){
                    minidx = j;
            }
        }

        if ( i != minidx ) swap_elements( a + minidx, a + i );
    }

你的函数也有 return 类型 int 但 return 没有这两个函数应该有 return 类型 void.

并且函数 selection_sort 的第二个参数应该具有类型 size_t 而不是类型 int。相应地，变量 n 应该声明为

 size_t n = sizeof(a)/sizeof(a[0]);

并且您应该在使用它们的最小范围内声明变量。

函数可以通过以下方式声明和定义

void selection_sort( int a[], size_t n )
{
    for ( size_t i = 0; i < n  ; i++ )
    {
        size_t minidx = i;
        for ( size_t j = i + 1; j < n; j++ )
        {
            if ( a[j] < a[minidx] ) minidx = j;
        }

        if ( i != minidx ) swap_elements( a + minidx, a + i );
    }
}

注意所有被调用的函数必须在调用前声明。

Answer 2

除了调用交换元素外，您的选择排序算法是正确的。找到最小元素后应交换元素。

#include<stdio.h>
int swap_elements(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
int selection_sort(int a[], int n){
    int i, j, minidx;
    for (i = 0; i < n - 1 ; i++){
        minidx = i;
        for (j = i + 1; j < n; j++){
            if (a[minidx] > a[j]){
                minidx = j;
            }
        }
        swap_elements(&a[minidx], &a[i]);
    }
}

int main(){
   int a[] = {64, 25, 12, 22, 11};
   int n = sizeof(a) / sizeof(a[0]);
   
   printf("Array before sorting: ");
   for (int i = 0; i < n; i++){
       printf("%d ", a[i]);
   }
   selection_sort(a, n);
   printf("Array after sorting: ");
   for (int k = 0; k < n; k++){
       printf("%d ", a[k]);
   }
}

试试这个代码。

我是初学者，正在练习 C 选择排序，但会针对不同的值获得不同的输出

I'm a beginner and practising C selection sort but getting different output for different values

c

sorting

swap

selection-sort

function-definition