比较法排序为何能以最少的对换次数完成证明

首先，设有n个元素且最值不再第一位（仅为方便证明，如在第一位，则问题变成第2位~第n位，不影响） 限制条件：元素归位后不再调换（后面将会证明此条件可达成最小次数） 比较法：将最小（大）的放在第一位后 总比较次数=1+(-1)+x,x∈[0,n-1]。注（1）：(-1)表示在第一次对换后，除了最值归位，还有可能另一个数也归为，那么后面就少对换1次。 非比较法： 将任意一位（非最值且非第一位）对换到第一位 可以看出这一位在后面的过程中还要对换到本位 所以，总比较次数=1+(-1)+1+(-1)+x 所以 比较法次数<=非比较法次数。 证明限制条件： 设：一元素归位后离开 那么总次数=1+(-1)+1+1+(-1)+x 解释：第一个1+(-1） 同理注（1） 这个元素离开后一次，而对换进来的元素本位肯定不是这一位，所以不存在注（1）情况，所以 +1 后这个元素又进来，所以同第一个1+(-1) 若该元素归位后不动，那么 总次数=1+（-1）+x 明显有该限制条件的总次数小。 证毕。