简单的选择排序程序。 85% 的时间完美运行，但有时无法排序

Question

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

main()
{
    int ctr, inner, outer, didSwap, temp;
    int nums[10];
    time_t t;

    srand(time(&t));

    for (ctr = 0; ctr < 10; ctr++) {
        nums[ctr] = (rand() % 99) + 1;
    }

    printf("\nHere is the list before the sort:\n");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%3d", nums[ctr]);
    }

    // Sorting the array
    for (outer = 0; outer < 9; outer++) {
        didSwap = 0;

        for (inner = outer + 1; inner < 10; inner++) {
            if (nums[inner] < nums[outer]) {
                temp = nums[inner];
                nums[inner] = nums[outer];
                nums[outer] = temp;
                didSwap = 1;
            }
        }

        if (didSwap == 0) {
            break;
        }
    }

    printf("\n\nHere is the list after sorting:\n");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%3d", nums[ctr]);
    }

    printf("\n");

    return 0;
}

大部分时间它都能正常工作，但有时排序不正确，有时根本不排序。

P.S。如果代码不正确，那么为什么它在 85% 的时间都有效。

错误快照

Answer 1

出于某种原因，您 break 如果没有对任何特定元素进行交换，从而使其他元素未排序：

if (didSwap == 0) {
    break;
}

您需要删除上述条件以使其起作用并对所有元素进行排序。在标准的选择排序算法中也不需要这样的条件。

Answer 2

没有交换时，您正在打破外循环。这不会起作用，所以删除 didSwap 并删除下面的代码

if (didSwap == 0) {
    break;
}

程序应该可以正常工作。

Answer 3

您的代码是错误的冒泡排序实现。

如果数组的第一个元素较小，如您问题中的示例代码

if (didSwap == 0) {
    break;
}

在第一回合就打破了循环，没有什么是排序的。

冒泡排序中存在类似于didSwap的测试，但实现不同，它不做if (nums[inner] < nums[outer])而是将每个元素与下一个.

If the code is incorrect then why does it work 85% of the times

我不知道这 85% 是从哪里来的（而且很可能是假的），当然一切都取决于数组中的值，但是当 nums[outer] 小于具有 a 的所有元素时更大的索引您的程序停止，并且不对具有更大索引的元素进行排序。在您问题的示例中，第一个元素是数组中较小的一个，因此根本没有排序。

所以有两种可能：

删除所有关于didSwap
实现冒泡排序

要让冒泡排序修改您的内部循环，例如：

for (inner = outer + 1; inner < 8; inner++) {
    if (nums[inner] > nums[inner + 1]) {
        temp = nums[inner];
        nums[inner] = nums[inner + 1];
        nums[inner + 1] = temp;
        didSwap = 1;
    }
}

例如使用您在问题中给出的值：

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

int main()
{
    int ctr, inner, outer, didSwap, temp;
#if 1
    int nums[10] = { 4, 6, 25, 9, 60, 59, 44, 65, 59, 90};
#else
    int nums[10];
    time_t t;

    srand(time(&t));

    for (ctr = 0; ctr < 10; ctr++) {
        nums[ctr] = (rand() % 99) + 1;
    }
#endif

    puts("\nHere is the list before the sort:");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%3d", nums[ctr]);
    }

    // Sorting the array
    for (outer = 0; outer < 9; outer++) {
        didSwap = 0;

        for (inner = outer + 1; inner < 8; inner++) {
            if (nums[inner] > nums[inner + 1]) {
                temp = nums[inner];
                nums[inner] = nums[inner + 1];
                nums[inner + 1] = temp;
                didSwap = 1;
            }
        }

        if (didSwap == 0) {
            break;
        }
    }

    puts("\n\nHere is the list after sorting:");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%3d", nums[ctr]);
    }

    putchar('\n');

    return 0;
}

编译与执行：

pi@raspberrypi:/tmp $ gcc -Wall c.c
pi@raspberrypi:/tmp $ ./a.out

Here is the list before the sort:
  4  6 25  9 60 59 44 65 59 90

Here is the list after sorting:
  4  6  9 25 44 59 59 60 65 90
pi@raspberrypi:/tmp $

简单的选择排序程序。 85% 的时间完美运行，但有时无法排序

Simple Selection Sort program. Works flawlessly 85% of times but sometimes doesn't sort

c

sorting

selection-sort