选择排序排序不正确

Question

我的选择排序算法工作不正常。我已经坚持了很长时间。我已经使用指针解决了它，但由于某种原因它排序不正确。

void sortArray(int arr[], size_t n)  
{  
    int i;  
    int j;
    int min_idx;  
    int min;  

    for (i = 0; i < n - 2; i++)  
    {  
        min = arr[i];
        min_idx = i;  
        for (j = (i+1); j < n - 1; j++)  
        {
            if (arr[j] < arr[min])  
            {
                min = arr[j];
                min_idx = j;
            }
        }   
        //swap(arr[min_idx], arr[i]);
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;      
    } 
}

之前

10 9 8 7 6 5 4 3 0 0

之后

0 9 7 3 6 4 5 8 10 0

但不胜感激。

Answer 1

您的内部 if 使用了错误的索引。应该是

if (arr[j] < arr[min_idx])

或者，因为 arr[min_idx] 已经存储在 min

if (arr[j] < min)

您的排序还差一个索引。你从不看arr[n - 1].

Answer 2

三个小错误。

你的循环条件错误和一个变量名错误（min 而不是 min_idx）。

修复这三个错误让我们...

void sortArray(int arr[], size_t n)  
{  
    int i;  
    int j;
    int min_idx;   

    for (i = 0; i < n - 1; i++)  
    {  
        min_idx = i;  
        for (j = (i+1); j < n; j++)  
        {
        if (arr[j] < arr[min_idx])  
            {
            min_idx = j;
            }
        }   
        //swap(arr[min_idx], arr[i]);
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;      
    } 
}

还删除了未使用的 min 变量。

Answer 3

函数中至少有两个错误。

第一个是索引为n-1的数组的最后一个元素由于循环中的条件而没有参与数组的排序

for (i = 0; i < n - 2; i++)  
{  
    min = arr[i];
    min_idx = i;  
    for (j = (i+1); j < n - 1; j++)  
    //..

第二个错误是在这个if语句中

if (arr[j] < arr[min])

在操作数 arr[min].

中使用 min 作为索引而不是 min_index

注意当n等于0或者1那么在循环的条件下

for (i = 0; i < n - 2; i++)

表达式 n - 2 将产生一个大的无符号值，导致函数的未定义行为。

还有这些变量

int i;  
int j;
int min_idx;

应具有类型 size_t 而不是类型 int。

还在使用变量的最小范围内声明变量。

函数可以这样定义。

void sortArray( int arr[], size_t n )  
{  
    for ( size_t i = 0; i < n; i++ )  
    {  
        size_t min_idx = i;  

        for ( size_t j = i + 1; j < n; j++ )  
        {
            if ( arr[j] < arr[min_idx] )  
            {
                min_idx = j;
            }
        }   

        if ( i != min_idx )
        {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }      
    } 
}

这是一个演示程序。

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

void sortArray( int arr[], size_t n )  
{  
    for ( size_t i = 0; i < n; i++ )  
    {  
        size_t min_idx = i;  

        for ( size_t j = i + 1; j < n; j++ )  
        {
            if ( arr[j] < arr[min_idx] )  
            {
                min_idx = j;
            }
        }   

        if ( i != min_idx )
        {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }      
    } 
}

int main(void) 
{
    srand( ( unsigned int )time( NULL ) );

    while ( 1 )
    {
        printf( "Enter the size of an integer array: " );

        size_t n = 0;

        if ( scanf( "%zu", &n ) != 1 || n == 0 ) break;

        putchar( '\n' );

        int a[n];

        for ( size_t i = 0; i < n; i++ )
        {
            a[i] = rand() % n;
        }

        printf( "Source array: " );

        for ( size_t i = 0; i < n; i++ )
        {
            printf( "%d ", a[i] );
        }
        putchar( '\n' );

        sortArray( a, n );

        printf( "Sorted array: " );

        for ( size_t i = 0; i < n; i++ )
        {
            printf( "%d ", a[i] );
        }
        putchar( '\n' );

        putchar( '\n' );
    }

    return 0;
}

它的输出可能看起来像

Enter the size of an integer array: 10

Source array: 4 1 1 3 1 8 7 4 0 9 
Sorted array: 0 1 1 1 3 4 4 7 8 9 

Enter the size of an integer array: 0

选择排序排序不正确

selection sort isn't sorting correctly

c

arrays

sorting

insertion-sort