1.帮我证明单向选择排序的Min/Max最大赋值次数公式是对的,2.求根据不同数组长度求出Min/Max最大赋值次数的组合一共有多少种的(公式)

#2

rjsp2025-11-27 15:34

最多赋值次数:比如长度是5个元素的数列组合,就有6种如下所示的数列:
3,5,4,2,1
5,4,1,3,2
5,4,2,1,3
4,5,3,2,1
5,4,3,1,2
5,4,3,2,1

看不懂
你例子中的 5 4 3 2 1 -> 1 4 3 2 5 -> 1 2 3 4 5 只需要 2 次
而不在例子中的 2 4 1 5 3 -> 1 4 2 5 3 -> 1 2 4 5 3 -> 1 2 3 5 4 -> 1 2 3 4 5 需要 4 次

#3

huangzhenfan2025-11-27 21:29

回复 2楼 rjsp

版主你好!
1.求助帮我证明根据不同数组长度求出Select被赋值最多数次的数列组合一共有多少种的(公式)

程序代码：

void SelectSort(int a[])
{
    unsigned LoopTotal = 0, SwapCount = 0, Select, SelectCount = 0;
    for (int Index = 0; Index < N - 1; ++Index)
    {
        Select = Index;
        for (int Traverse = Index + 1; Traverse < N; ++Traverse)
        {
            if (a[Select] > a[Traverse])
            {
                Select = Traverse;
                ++SelectCount;
            }
            ++LoopTotal;
        }
        if (Select != Index)
        {
            a[Select] ^= a[Index];
            a[Index] ^= a[Select];
            a[Select] ^= a[Index];
            ++SwapCount;
        }
    }
}

我说的是Select被赋值最多次数,内循环Select被赋值最多次数计算公式为:(N-1)公差为2的等差数列求和,帮我证明他是对的,2.数组长度有5个元素及5个元素以上,比如1,2,3,4,5 这5个元素有120种组合,其中有6种组合是Select被赋值次数最多的,而6个元素有720种组合,其中有x种组合是Select被赋值最多次数的,帮我把这种数列组合数量的公式算出来(比如:6个元素时Select被赋值最多次数有多少种数列组合,7个元素时Select被赋值最多次数有多少种数列组合...,已知5个元素是6种)

比如长度是5个元素的数列组合,就有6种如下所示的数列,Select被赋值次数是最多的,在外循环Select被赋值为N-1次,在内循环Select最多赋值次数计算公式:(N-1)公差为2的等差数列求和;
如:
3,5,4,2,1 :第一轮循环:Select=3=2=1(内循环赋值两次),第二轮循环:Select=5=4=2(内循环赋值两次),第三轮循环:Select=4=3(内循环赋值一次),第四轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
5,4,1,3,2 :第一轮循环:Select=5=4=1(内循环赋值两次),第二轮循环:Select=4=3=2(内循环赋值两次),第三轮循环:Select=5=3(内循环赋值一次),第四轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
5,4,2,1,3 :第一轮循环:Select=5=4=2=1(内循环赋值三次),第二轮循环:Select=4=2(内循环赋值一次),第三轮循环:Select=4=3(内循环赋值一次),第四轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
4,5,3,2,1 :第一轮循环:Select=4=3=2=1(内循环赋值三次),第二轮循环:Select=5=3=2(内循环赋值两次),第三轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
5,4,3,1,2 :第一轮循环:Select=5=4=3=1(内循环赋值三次),第二轮循环:Select=4=3=2(内循环赋值两次),第三轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
5,4,3,2,1 :第一轮循环:Select=5=4=3=2=1(内循环赋值四次),第二轮循环:Select=4=3=2(内循环赋值两次),内循环共6次赋值

[此贴子已经被作者于2025-11-29 03:14编辑过]

#4

yiyanxiyin2025-11-28 10:46

倒序那种应该就是最大赋值次数, 内循环,每循环一轮就会去掉两个数, 所以是(N-1)公差为2的等差数列的和

#5

huangzhenfan2025-11-29 01:16

回复 4楼 yiyanxiyin

5个元素时,有6种组合是最多赋值次数,多数情况不倒序是最多赋值次数,有5种组合不是倒序,仅有一种组合是倒序,怎么证明数列的长度和最大赋值组合(组合的数量关系,比如5个元素已知6种组合是min最多赋值次数,6个元素时min最多赋值组合有多少个,7个元素时该组合有多少个...,帮我把公式算出来,就像证明全逆序的内循环赋值次数是公差为2的等差数列求和一样),谢谢!
主要DeepSeek和百度AI不给力,他们给出的所有公式都是错的,比如4个数列的min最多赋值次数为4次,百度AI为(n-1)*(n-2)/2=(4-1)*(4-2)/2=3次

只有本站会员才能查看附件，请登录

[此贴子已经被作者于2025-11-29 03:27编辑过]

#6

rjsp2025-11-30 10:50

以下是引用huangzhenfan在2025-11-27 21:29:17的发言：

3,5,4,2,1 :第一轮循环:Select=3=2=1(内循环赋值两次),第二轮循环:Select=5=4=2(内循环赋值两次),第三轮循环:Select=4=3(内循环赋值一次),第四轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
5,4,1,3,2 :第一轮循环:Select=5=4=1(内循环赋值两次),第二轮循环:Select=4=3=2(内循环赋值两次),第三轮循环:Select=5=3(内循环赋值一次),第四轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
5,4,2,1,3 :第一轮循环:Select=5=4=2=1(内循环赋值三次),第二轮循环:Select=4=2(内循环赋值一次),第三轮循环:Select=4=3(内循环赋值一次),第四轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
4,5,3,2,1 :第一轮循环:Select=4=3=2=1(内循环赋值三次),第二轮循环:Select=5=3=2(内循环赋值两次),第三轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
5,4,3,1,2 :第一轮循环:Select=5=4=3=1(内循环赋值三次),第二轮循环:Select=4=3=2(内循环赋值两次),第三轮循环:Select=5=4(内循环赋值一次),内循环共6次赋值
5,4,3,2,1 :第一轮循环:Select=5=4=3=2=1(内循环赋值四次),第二轮循环:Select=4=3=2(内循环赋值两次),内循环共6次赋值

那么 4,3,5,2,1 呢？
第一轮循环: Select=4=3=2=1(内循环赋值3次), 余下 3,5,2,4
第二轮循环: Select=3=2(内循环赋值1次), 余下 5,3,4
第三轮循环: Select=5=3(内循环赋值1次), 余下 5,4
第三轮循环: Select=5=4(内循环赋值1次), 余下 5
内循环共6次赋值

#7

rjsp2025-11-30 15:58

程序代码：

#include <stdio.h>

size_t SelectSort( int a[], size_t n )
{
    size_t SelectCount = 0;
    for( size_t i=0; i+1<n; ++i )
    {
        size_t Select = i;
        for( size_t j=i+1; j!=n; ++j )
        {
            if( a[Select] > a[j] )
            {
                Select = j;
                ++SelectCount;
            }
        }

        int t = a[i];
        a[i] = a[Select];
        a[Select] = t;
    }
    return SelectCount;
}

//////////// 以下测试代码是用 C++ 写的 ////////////
#include <vector>
#include <algorithm>
#include <ranges>
#include <print>

void foo( size_t n )
{
    size_t max_result = 0;
    std::vector<std::vector<int>> max_seqs;
    auto a = std::views::iota(1,(int)(n+1)) | std::ranges::to<std::vector>();
    for( bool c=true; c; c=std::ranges::next_permutation(a).found )
    {
        std::vector<int> b = a;
        size_t r = SelectSort( &b[0], b.size() );
        if( r > max_result )
        {
            max_seqs.clear();
            max_result = r;
        }
        if( r == max_result )
            max_seqs.push_back( a );
    }

    printf( "N=%zu, 最大赋值次数%zu, 一共%zu种:\n", n, max_result, max_seqs.size() );
    for( const auto& s : max_seqs )
        std::println( "    {{{:n}}}", s );
}

int main( void )
{
    for( size_t n=1; n!=13; ++n )
        foo( n );
}

输出

程序代码：

N=1, 最大赋值次数0, 一共1种:
    {1}
N=2, 最大赋值次数1, 一共1种:
    {2, 1}
N=3, 最大赋值次数2, 一共3种:
    {2, 3, 1}
    {3, 1, 2}
    {3, 2, 1}
N=4, 最大赋值次数4, 一共3种:
    {3, 4, 2, 1}
    {4, 3, 1, 2}
    {4, 3, 2, 1}
N=5, 最大赋值次数6, 一共7种:
    {3, 5, 4, 2, 1}
    {4, 3, 5, 2, 1}
    {4, 5, 3, 2, 1}
    {5, 4, 1, 3, 2}
    {5, 4, 2, 1, 3}
    {5, 4, 3, 1, 2}
    {5, 4, 3, 2, 1}
N=6, 最大赋值次数9, 一共7种:
    {4, 6, 5, 3, 2, 1}
    {5, 4, 6, 3, 2, 1}
    {5, 6, 4, 3, 2, 1}
    {6, 5, 4, 1, 3, 2}
    {6, 5, 4, 2, 1, 3}
    {6, 5, 4, 3, 1, 2}
    {6, 5, 4, 3, 2, 1}
N=7, 最大赋值次数12, 一共11种:
    {4, 7, 6, 5, 3, 2, 1}
    {5, 7, 6, 4, 3, 2, 1}
    {6, 5, 4, 7, 3, 2, 1}
    {6, 5, 7, 4, 3, 2, 1}
    {6, 7, 5, 4, 3, 2, 1}
    {7, 6, 5, 1, 4, 3, 2}
    {7, 6, 5, 3, 2, 1, 4}
    {7, 6, 5, 4, 1, 3, 2}
    {7, 6, 5, 4, 2, 1, 3}
    {7, 6, 5, 4, 3, 1, 2}
    {7, 6, 5, 4, 3, 2, 1}
N=8, 最大赋值次数16, 一共11种:
    {5, 8, 7, 6, 4, 3, 2, 1}
    {6, 8, 7, 5, 4, 3, 2, 1}
    {7, 6, 5, 8, 4, 3, 2, 1}
    {7, 6, 8, 5, 4, 3, 2, 1}
    {7, 8, 6, 5, 4, 3, 2, 1}
    {8, 7, 6, 5, 1, 4, 3, 2}
    {8, 7, 6, 5, 3, 2, 1, 4}
    {8, 7, 6, 5, 4, 1, 3, 2}
    {8, 7, 6, 5, 4, 2, 1, 3}
    {8, 7, 6, 5, 4, 3, 1, 2}
    {8, 7, 6, 5, 4, 3, 2, 1}
N=9, 最大赋值次数20, 一共15种:
    {5, 9, 8, 7, 6, 4, 3, 2, 1}
    {6, 9, 8, 7, 5, 4, 3, 2, 1}
    {7, 9, 8, 6, 5, 4, 3, 2, 1}
    {8, 7, 6, 5, 9, 4, 3, 2, 1}
    {8, 7, 6, 9, 5, 4, 3, 2, 1}
    {8, 7, 9, 6, 5, 4, 3, 2, 1}
    {8, 9, 7, 6, 5, 4, 3, 2, 1}
    {9, 8, 7, 6, 1, 5, 4, 3, 2}
    {9, 8, 7, 6, 4, 3, 2, 1, 5}
    {9, 8, 7, 6, 5, 1, 4, 3, 2}
    {9, 8, 7, 6, 5, 3, 2, 1, 4}
    {9, 8, 7, 6, 5, 4, 1, 3, 2}
    {9, 8, 7, 6, 5, 4, 2, 1, 3}
    {9, 8, 7, 6, 5, 4, 3, 1, 2}
    {9, 8, 7, 6, 5, 4, 3, 2, 1}
N=10, 最大赋值次数25, 一共15种:
    {6, 10, 9, 8, 7, 5, 4, 3, 2, 1}
    {7, 10, 9, 8, 6, 5, 4, 3, 2, 1}
    {8, 10, 9, 7, 6, 5, 4, 3, 2, 1}
    {9, 8, 7, 6, 10, 5, 4, 3, 2, 1}
    {9, 8, 7, 10, 6, 5, 4, 3, 2, 1}
    {9, 8, 10, 7, 6, 5, 4, 3, 2, 1}
    {9, 10, 8, 7, 6, 5, 4, 3, 2, 1}
    {10, 9, 8, 7, 6, 1, 5, 4, 3, 2}
    {10, 9, 8, 7, 6, 4, 3, 2, 1, 5}
    {10, 9, 8, 7, 6, 5, 1, 4, 3, 2}
    {10, 9, 8, 7, 6, 5, 3, 2, 1, 4}
    {10, 9, 8, 7, 6, 5, 4, 1, 3, 2}
    {10, 9, 8, 7, 6, 5, 4, 2, 1, 3}
    {10, 9, 8, 7, 6, 5, 4, 3, 1, 2}
    {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
N=11, 最大赋值次数30, 一共19种:
    {6, 11, 10, 9, 8, 7, 5, 4, 3, 2, 1}
    {7, 11, 10, 9, 8, 6, 5, 4, 3, 2, 1}
    {8, 11, 10, 9, 7, 6, 5, 4, 3, 2, 1}
    {9, 11, 10, 8, 7, 6, 5, 4, 3, 2, 1}
    {10, 9, 8, 7, 6, 11, 5, 4, 3, 2, 1}
    {10, 9, 8, 7, 11, 6, 5, 4, 3, 2, 1}
    {10, 9, 8, 11, 7, 6, 5, 4, 3, 2, 1}
    {10, 9, 11, 8, 7, 6, 5, 4, 3, 2, 1}
    {10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1}
    {11, 10, 9, 8, 7, 1, 6, 5, 4, 3, 2}
    {11, 10, 9, 8, 7, 5, 4, 3, 2, 1, 6}
    {11, 10, 9, 8, 7, 6, 1, 5, 4, 3, 2}
    {11, 10, 9, 8, 7, 6, 4, 3, 2, 1, 5}
    {11, 10, 9, 8, 7, 6, 5, 1, 4, 3, 2}
    {11, 10, 9, 8, 7, 6, 5, 3, 2, 1, 4}
    {11, 10, 9, 8, 7, 6, 5, 4, 1, 3, 2}
    {11, 10, 9, 8, 7, 6, 5, 4, 2, 1, 3}
    {11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2}
    {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
N=12, 最大赋值次数36, 一共19种:
    {7, 12, 11, 10, 9, 8, 6, 5, 4, 3, 2, 1}
    {8, 12, 11, 10, 9, 7, 6, 5, 4, 3, 2, 1}
    {9, 12, 11, 10, 8, 7, 6, 5, 4, 3, 2, 1}
    {10, 12, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1}
    {11, 10, 9, 8, 7, 12, 6, 5, 4, 3, 2, 1}
    {11, 10, 9, 8, 12, 7, 6, 5, 4, 3, 2, 1}
    {11, 10, 9, 12, 8, 7, 6, 5, 4, 3, 2, 1}
    {11, 10, 12, 9, 8, 7, 6, 5, 4, 3, 2, 1}
    {11, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
    {12, 11, 10, 9, 8, 7, 1, 6, 5, 4, 3, 2}
    {12, 11, 10, 9, 8, 7, 5, 4, 3, 2, 1, 6}
    {12, 11, 10, 9, 8, 7, 6, 1, 5, 4, 3, 2}
    {12, 11, 10, 9, 8, 7, 6, 4, 3, 2, 1, 5}
    {12, 11, 10, 9, 8, 7, 6, 5, 1, 4, 3, 2}
    {12, 11, 10, 9, 8, 7, 6, 5, 3, 2, 1, 4}
    {12, 11, 10, 9, 8, 7, 6, 5, 4, 1, 3, 2}
    {12, 11, 10, 9, 8, 7, 6, 5, 4, 2, 1, 3}
    {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2}
    {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

#8

huangzhenfan2025-12-01 10:46

回复 7楼 rjsp

首先感谢版主！
第一帮请您我证明最多赋值次数公式是对的,也就是说所有最多赋值的组合为什么不能超过全逆序的赋值次数
第二帮请您我证明最多赋值次数的组合数量随数列长度关系的公式

[此贴子已经被作者于2025-12-1 10:48编辑过]

#9

yiyanxiyin2025-12-01 10:56

“所有最多赋值的组合为什么不能超过全逆序的赋值次数”: 因为你算法决定了全逆序赋值次数最多，你也找找不到反例

#10

huangzhenfan2025-12-02 08:59

回复 9楼 yiyanxiyin

版主你好!
请您在数学和算法上证明,其它组合的最多赋值次数为什么要等于全逆序的，你如何确定更长的数列也是这样的情况

[此贴子已经被作者于2025-12-2 11:00编辑过]

#11

yiyanxiyin2025-12-02 09:49

证明题只要你能说服人，不管用什么方法都行，你动脑筋想想：
外层第一次循环，内层a[Select] > a[Traverse]最多比较N-1次，假设每次都是前一个数大，那么Select赋值次数为最多，就是N-1次(不可能比这个数更大了)，
外层第二次循环，内层a[Select] > a[Traverse]最多比较N-4次，但是不是每次都是前一个数大，因为肯定最大的数在其中 , 也就是至少存在一次a[Select] <= a[Traverse], 那么Select赋值次数最多是N-3次(不可能比这个数更大了)，
外层第三次循环，内层a[Select] > a[Traverse]最多比较N-3次，但是不是每次都是前一个数大，因为肯定有两个最大的数在其中 , 也就是至少存在两次a[Select] <= a[Traverse], 那么Select赋值次数最多是N-5次(不可能比这个数更大了)，
.....

Select总赋值次数N-1 +N-3 + N-5.....,  这还不明显吗

[此贴子已经被作者于2025-12-2 10:11编辑过]

1.帮我证明单向选择排序的Min/Max最大赋值次数公式是对的,2.求根据不同数组长度求出Min/Max最大赋值次数的 组合一共有多少种的(公式)