void SelectSort(int a[])
{/* 第一次从待排序的数组元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾;以此类推,直到所有元素均排序完毕;
1.选择排序是不稳定的排序方法(相同数有可能因交换而改变原前后次序);5个元素选择排序为总次数为(4的等差数列之和)10次;
  一次比较两个数找出最小(大)元素:内循环比较最后1对数只需要1次;外循环每次再将比较范围缩小1个;
2.循环次数的等差数列求和公式:S = 1 +2 +3 +… +(n-1) +n;将n项加数反序:S = n +(n-1) +(n-2) +… +2 +1;将前两个公式正反序的加数1对1相加为:2S = (n+1)× n项;得S = (n+1)×n/2;
  如果n要减小一个数为:N×(N-1)/2;
3.4轮内循环次数统计:第一轮Select为[0]比较4次Traverse为[1～4],Select存新下标;第二轮Select为[1]比较3次Traverse为[2～4],Select存新下标;
  第三轮Select为[2]比较2次Traverse为[3～4],Select存新下标;第四轮Select为[3]比较1次Traverse为[4],Select存新下标;
4.交换次数:已经是有序状态如:12345,无需再交换;逆序时如:54321,交换n/2次,奇数量中间的元素不必交换(已遍历交换它的前后);
  最坏情况如:51234、53124及35214...所有位置都要换,交换n-1次(最后1对只交换一次);赋值总次数:交换次数×3
5.Select赋值次数:最好情况数列有序的 或全部相同是0次,最坏情况是反序(不会超过反序的,因为错的会减少赋值次数):
  每赋值一轮,赋值范围就缩小2个(公差为-2),总次数 = (项数:(N-1)/2) /2 × [2×(首项:(N-1)) + ((项数:(N-1)/2) - 1)×公差:-2]   + 外循环N-1次;  */
    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使用大于号是找出最小数,用小于号是找出最大数;
            {
                Select = Traverse;        // 交换下标只要赋值一次
                ++SelectCount;            // 统计Select被赋值总次数;最坏的情况是反序,每赋值一轮,赋值范围就缩小2个(公差为-2),用等差数列求和公式:总和 = (项数 / 2)x[2×首项 + (项数 - 1)×公差];再加外循环N-1次;
            }//最坏情况赋值总次数:#define N 6; (6-1)/2/2 * (2*(6-1) + ((6-1)/2-1) *-2 ) = 8.75次;精确到有小数为1次即9次; +5次 =14次        
            ++LoopTotal;                // 统计循环总次数:(n+1)*n/2;
        }
        if (Select != Index)            // Select值改变时才交换:每交换一个元素赋值为3次。1.用异或交换律; 
        {//已经是有序状态如:12345交换,每轮循环无需进行交换;逆序时如:54321,交换n/2次因奇数量中间的元素不必交换(已遍历交换该前后);最坏情况如:51234、53124及35214...所有位置都要换,交换n-1次(最后1对只交换一次)
            a[Select] ^= a[Index];        // 注意:不能自身与自身异或,否则为0;(含结果值)任意序的两两异或必定等于其第三值;
            a[Index] ^= a[Select];
            a[Select] ^= a[Index];
            ++SwapCount;                // 统计元素交换次数,每交换一次赋值3次
        }
    }
}
最多赋值次数:比如长度是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

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

看不懂
你例子中的 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 次

版主你好!
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编辑过]

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

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编辑过]

那么 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次赋值

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

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

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

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

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

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