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

sulley · 发表于 2020-4-22 21:31:13

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

望高手指点迷津!

#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;
}
}

复制代码

排序算法部分的改动

跳转到最佳答案楼层

倒戈卸甲 · 发表于 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;
}
}

复制代码

排序算法部分的改动

sulley · 发表于 2020-4-22 22:17:07

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

非常感谢你的帮助！

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

sulley · 发表于 2020-4-22 22:26:59

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

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

倒戈卸甲 · 发表于 2020-4-22 22:41:12

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

倒戈卸甲 · 发表于 2020-4-22 22:42:02

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

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

sulley · 发表于 2020-4-22 22:52:44

本帖最后由 sulley 于 2020-4-22 22:57 编辑

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

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

倒戈卸甲 · 发表于 2020-4-22 22:59:19

本帖最后由倒戈卸甲于 2020-4-23 11:34 编辑

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 23:07:51

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

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

sulley · 发表于 2020-4-22 23:19:50

倒戈卸甲发表于 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);
}
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);
}
}

sulley · 发表于 2020-4-22 23:26:10

本帖最后由 sulley 于 2020-4-22 23:29 编辑

倒戈卸甲发表于 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);

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

{

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

         if (a < a[j])



         {

            k = a;

            a = a[j];

            a[j] = k;

         }

}

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

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

      printf("%4d", a);

printf("\n");

return 0;

}

倒戈卸甲 · 发表于 2020-4-22 23:27:47

本帖最后由倒戈卸甲于 2020-4-22 23:35 编辑

倒戈卸甲发表于 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;
}
}
}
}

复制代码

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

倒戈卸甲 · 发表于 2020-4-22 23:34:09

本帖最后由倒戈卸甲于 2020-4-23 11:33 编辑

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

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

sulley · 发表于 2020-4-22 23:53:01

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

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

倒戈卸甲 · 发表于 2020-4-22 23:56:15

本帖最后由倒戈卸甲于 2020-4-23 00:10 编辑

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;
            arr=arr[M];
            arr[M]=temp;
                     }
这段代码，因为最终M的值为4，并非循环开始时首元素的下标，说明首元素不是最大值。而此时M记录了最大值下标，把a[M]交给首元素就好。

倒戈卸甲 · 发表于 2020-4-23 00:04:18

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

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

sulley · 发表于 2020-4-23 00:04:43

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

感激涕零！{:10_254:

倒戈卸甲 · 发表于 2020-4-23 00:07:17

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

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

sulley · 发表于 2020-4-23 00:20:37

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

向大佬学习！

倒戈卸甲 · 发表于 2020-4-23 00:26:58

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

其实这个论坛的大佬都在python板块

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

账号		自动登录	找回密码
密码			立即注册

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

最佳答案

评分

评分