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被赋值最多次数的公式是对的,2.根据不同数组长度求出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-28 05:09编辑过]