[已解决]关于选择排列的语法提问

sulley

自己编写的选择排列语法，一直在修改都未获成功。。已经想了一个晚上了，还是不知道错在哪里 望高手指点迷津!

#include <stdio.h>
#define N 10
int main(void)
{
        int i, j, k,l, temp, num[N],max_id;

        printf("Enter 10 numbers: ");
        for (i = 0; i < N; i++)
        {
                scanf_s("%d", &num[i]);
        }
        for (j = N - 1; j >= 0; j--)
        {
                max_id = j;
                for (k =1; k <N - j ; k++)
                {
                        if (num[k] > num[max_id])
                        {
                                max_id = k;
                        }
                }
                if (max_id != j)
                {
                        temp = num[j];
                        num[j] = num[max_id];   
                        num[max_id] = temp;
                }
        }
        for (l = 0; l < N; i++)
        {
                printf("%d", num[l]);
        }
        return 0;
}

最佳答案

月排行榜 / 总排行榜

倒戈卸甲

2020-4-22 21:31:14

选择排序是冒泡排序的一种变形，每次循环都找出一个最大值或最小值，我先简单给出你这个的标准形式，再看看你代码的问题在哪里

 for (j = N - 1; j >= 0; j--)
    {
        max_id = j;
        for (k = j-1; k >=0; k--)
        {
            if (num[k] < num[max_id])
            {
                max_id = k;
            }
        }
        if (max_id != j)
        {
            temp = num[j];
            num[j] = num[max_id];
            num[max_id] = temp;
        }
    }

排序算法部分的改动

跳转到最佳答案楼层

倒戈卸甲

选择排序是冒泡排序的一种变形，每次循环都找出一个最大值或最小值，我先简单给出你这个的标准形式，再看看你代码的问题在哪里

 for (j = N - 1; j >= 0; j--)
    {
        max_id = j;
        for (k = j-1; k >=0; k--)
        {
            if (num[k] < num[max_id])
            {
                max_id = k;
            }
        }
        if (max_id != j)
        {
            temp = num[j];
            num[j] = num[max_id];
            num[max_id] = temp;
        }
    }

排序算法部分的改动

sulley

倒戈卸甲 发表于 2020-4-22 22:01
选择排序是冒泡排序的一种变形，每次循环都找出一个最大值或最小值，我先简单给出你这个的标准形式，再看看 ...

非常感谢你的帮助！修改了第二个for语句的循环条件就能成功运行了！看来我在对嵌套循环的知识了解得还不够透彻，我得继续钻研钻研。

sulley

倒戈卸甲 发表于 2020-4-22 21:31
选择排序是冒泡排序的一种变形，每次循环都找出一个最大值或最小值，我先简单给出你这个的标准形式，再看看 ...

答主不好意思打扰了！我还有一个地方比较迷惑：按理说我是将最大值赋予了最后一位数字，正常情况下不应该是按照从小到大排序吗？可结果怎么就成了从大到小

倒戈卸甲

      if (num[k] < num[max_id])
            {
                max_id = k;
            }
        }
中使用大于号或小于号能分别控制正序逆序

倒戈卸甲

sulley 发表于 2020-4-22 22:26
答主不好意思打扰了！我还有一个地方比较迷惑：按理说我是将最大值赋予了最后一位数字，正常情况下不应该 ...

不过你原先思路应该和我的代码不同，里面的问题我一时半会儿还没找到

sulley

倒戈卸甲 发表于 2020-4-22 22:42
不过你原先思路应该和我的代码不同，里面的问题我一时半会儿还没找到

我试过之后成功了！答主好厉害！！谢谢你！C语言的循环真的好神奇啊！今天实在是麻烦你了！非常感谢!今天长知识了

倒戈卸甲

sulley 发表于 2020-4-22 22:26
答主不好意思打扰了！我还有一个地方比较迷惑：按理说我是将最大值赋予了最后一位数字，正常情况下不应该 ...

    for (int i = 0; i <len; i++)
                {
                        int M = i;
                        for (int j = i+1; j < len; j++)
                        {
                                
                                        if (arr[M] > arr[j]) {
                                                M = j;
                                        }
                        if (i!=M)
                        {
                temp=arr[i];
                arr[i]=arr[M];
                arr[M]=temp;
                        }
                }

上面是最基础的选择排序法，通过if (arr[M] > arr[j])或者if (arr[M] < arr[j])分别实现升序和降序。这个代码的排序逻辑几乎等同于冒泡排序，第一轮排序比较len-1次，在全部len个值中找到最小值，并将其序号设为0，第二轮排序比较len-2次，在剩下len-1个值中找到最小值，并将其序号设为1......通过len-1轮排序就实现了数组排序。
而你的算法很有意思，虽然有错误，但整体思路是：第一轮只比较0次，选择的数序号不变，仍为n-1，第二轮比较1次，把小的那个序号设为n-2... ...最后一轮才比较n-1次，我要好好琢磨一下

倒戈卸甲

倒戈卸甲 发表于 2020-4-22 22:59
for (int i = 0; i  arr[j]) {
                                                M = j;
                                        }

嗯，想明白了，你的思路通过选择排序算法不能实现。因为选择排序每轮只“挑出”最大数或最小数，虽然有多次比较，但比较完只交换下标，最后才进行至多一次实质上的数字交换。但你的这个思路必须要第n轮排序可以交换n次数字才行

sulley

倒戈卸甲 发表于 2020-4-22 23:07
嗯，想明白了，你的思路通过选择排序算法不能实现。因为选择排序每轮只“挑出”最大数或最小数，虽然有多 ...

那么请问下这个修改后能够正确运行的代码本质上是起泡排序吗
#include <stdio.h>
#define N 10
int main(void)
{
        int i, j, k, temp, max_id, num[N];

        printf("Enter 10 numbers: ");
        for (i = 0; i < N; i++)
        {
                scanf_s("%d", &num[i]);
        }
        for (j = N - 1; j >= 0; j--)
        {
                max_id = j;
                for (k = j - 1; k >= 0; k--)
                {
                        if (num[k] > num[max_id])
                        {
                                max_id = k;
                        }
                }
                if (max_id != j)
                {
                        temp = num[j];
                        num[j] = num[max_id];
                        num[max_id] = temp;
                }
        }
        for (i = 0; i < N; i++)
        {
                printf("%d ", num[i]);
        }
}

sulley

倒戈卸甲 发表于 2020-4-22 23:07
嗯，想明白了，你的思路通过选择排序算法不能实现。因为选择排序每轮只“挑出”最大数或最小数，虽然有多 ...

我突然间又变懵了一开始我写的线面的语法老师说是起泡排序，要修改为选择排序。今天下午到现在都在努力分清他们的区别。就目前我的认知层次是，起泡排序是分组两两比较数字，不符合条件的的交换，而选择排序是交换下标。两者似乎都要交换过很多次，实则不然。
我不明白怎么直接将最值与目标下标交换了实在抱歉，又打扰你了
#include <stdio.h>

#define N 10//假设是将10个数字进行排列



int main (void)

{

    int a[N];

    int i, j, k;

    printf("请%d个待排序数字： ",N);

    for (i = 0; i < N; i++)

        scanf_s("%d", &a[i]);



    for (i = 0; i < N; i++)

    {

        for (j = 0; j < N; j++)

            if (a[i] < a[j])

      

            {

                k = a[i];

                a[i] = a[j];

                a[j] = k;

            }

    }

    printf("排序后数字为:\n");

    for (i = 0; i < N; i++)

        printf("%4d", a[i]);

    printf("\n");

    return 0;

}

倒戈卸甲

倒戈卸甲 发表于 2020-4-22 22:59
for (int i = 0; i  arr[j]) {
                                                M = j;
                                        }

void sort(int arr[],int len)
{
        for (int i = 0; i < len-1; i++)
        {
                for (int j = 0; j < len - i - 1; j++)
                {
                        if (arr[j] > arr[j + 1])
                        {
                                int temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
                }
        }
}

这个是冒泡排序，学校都会教这个，跟选择排序相比，冒泡选择每次比较都会更正被比较的两个数的大小关系，拿到较大的那个数参与下一次比较。比较多少次就可能最多交换多少次，一轮比较完得出一个最值。而选择排序法，真正拿到的是每次比较后较大的那个数的下标，然后进行下一次比较。一轮比较完拿到最大的那个数的下标，然后才真正进行一次可能的交换。

倒戈卸甲

sulley 发表于 2020-4-22 23:19
那么请问下这个修改后能够正确运行的代码本质上是起泡排序吗
#include
#define N 10

没有，我不是这个意思。选择排序与冒泡排序绝对是两种不同的算法，我说的几乎等同是指它每轮比较达成的结果，以及每轮进行的比较次数

sulley

倒戈卸甲 发表于 2020-4-22 23:34
没有，我不是这个意思。选择排序与冒泡排序绝对是两种不同的算法，我说的几乎等同是指它每轮比较达成的目 ...

哦哦！恕我愚钝！我终于理解了！！！非常感谢您今天的耐心讲解呀~

倒戈卸甲

sulley 发表于 2020-4-22 23:26
我突然间又变懵了一开始我写的线面的语法老师说是起泡排序，要修改为选择排序。今天下午到现 ...

其实理解起来还是很简单的。举个例子就行。假设数组中最大的数为a[4]，长度为x，只讨论第一轮排序。
冒泡排序进行x-1次比较，第5次比较会将a[4]与a[5]交换，使a[5]变为最大值；第6次比较会将a[5]与a[6]交换，使a[6]变为最大值。。。。第n-1次比较会将将a[n-2]与a[n-1]交换，使a[n-1]变为最大值.
=========
选择排序也进行x-1次比较，但它是用一个变量M来记录下标，最先是令下标为0 ，然后a[1]与a[M]比较，假设a[1]大就令M=1，否则M还是为0。第四次比较的时候，a[4]与a[M]比较，此时M的取值可能为0/1/2/3中的任何一个，谁是前面的最大值，M就等于它的下标。不过没关系，因为a[4]最大，这次比较完后，M的值会一直为4。然后就是 if (i!=M)
                        {
                temp=arr[i];
                arr[i]=arr[M];
                arr[M]=temp;
                        }
这段代码，因为最终M的值为4，并非循环开始时首元素的下标，说明首元素不是最大值。而此时M记录了最大值下标，把a[M]交给首元素就好。

倒戈卸甲

倒戈卸甲 发表于 2020-4-22 23:56
其实理解起来还是很简单的。举个例子就行。假设数组中最大的数为a[4]，长度为x，只讨论第一轮排序。
...

这里举例没仔细去考虑，冒泡排序的结果是升序，选择排序的结果是降序。不过这不影响，选择排序要降序的话，每次比较拿到较小值下标就行，也不要盯着a[4]不放了，去盯着数组中最小的那个数就行

sulley

倒戈卸甲 发表于 2020-4-22 23:56
其实理解起来还是很简单的。举个例子就行。假设数组中最大的数为a[4]，长度为x，只讨论第一轮排序。
...

感激涕零！{:10_254:

倒戈卸甲

sulley 发表于 2020-4-23 00:04
感激涕零！{:10_254:

其实这样我也顺便复习一下排序算法，对我自己挺有好处的

sulley

倒戈卸甲 发表于 2020-4-23 00:07
其实这样我也顺便复习一下排序算法，对我自己挺有好处的

向大佬学习！

倒戈卸甲

sulley 发表于 2020-4-23 00:20
向大佬学习！

其实这个论坛的大佬都在python板块
如果你是用python写的排序算法早就一大群大佬围上来了。
而我学python的时间还不够长，平时用的又少，还有很长的路要走