n个数排序，最坏情况下的最小交换次数是多少呢？
什么是最坏情况下？是将“987654321”排成“123456789的情况”？？将逆序排成正序的情况？
有的文章说最少要n-1次，对吗？为什么？
它的证明如下：
证明：一：当未排序元素大于2时，每次交换都至少可以将一个元素放到它正确的位置上；当未排序元素等于2时，只要一次就可以把两个元素放到它正确的位置上。所以，最多需要n-1次。
二：若该序列为整数序列2,3,…,n,1。要将这个数列排序，必须把2到n共n-1个数往后移动。但是，每次交换只能将一个数字往后移动，所以至少需要n-1次交换才能完成排序。
第一步中：“每次交换都至少可以将一个元素放到它正确的位置上”是什么意思？
第二步中，怎么能用“若该序列为整数序列2,3,…,n,1”这样一个具体例子来证明 呢？证明要不失一般性！
你的观点呢？多谢指教
问题点数：20、回复次数：9Top
1 楼csdn2010（陈一凡（上海）（结交所有程序员，尤其））回复于 2004-07-01 13:59:55 得分 0
你在哪里工作啊？
你多大？你叫？
我很想与你成为朋友啊！我叫陈一凡，男，22岁，你可以介绍一下自己吗？
你擅长设么？我的手机：13916316917
收到后发个消息给我吧！！Top
2 楼csdn2010（陈一凡（上海）（结交所有程序员，尤其））回复于 2004-07-01 14:00:06 得分 0
要源代码可以看《数据结构（C语言版）》清华大学出版社，--注意是 黄国瑜 叶乃菁的不是严蔚敏的。
如果是C++的话，〈数据结构C++语言描述〉william Ford william Topp著，清华大学出版社
这两本书都有源代码，不是伪码
程序设计艺术(三卷本)是数据结构原理方面的经典,STL源码是实现的经典!
Top
3 楼futulove（福途￡爱）回复于 2004-07-01 14:26:18 得分 0
4 楼benbebnmao（苯笨猫）回复于 2004-07-01 15:34:46 得分 0
是啊，什么和什么啊？
我也不知道他在干什么？Top
5 楼xjq2003（xjq2003）回复于 2004-07-01 16:58:40 得分 0
UPTop
6 楼mli0080（leslie）回复于 2005-04-02 11:12:57 得分 4
这是一个比较大的算法呢，我现在手中就有一个这样的问题（有7个不同的数，要得到所有按不同位置排列出来的结果），我用过穷举法（通过7个循环），效率太低了，想找一个更好的算法，Top
7 楼huanyun（无妻徒刑）回复于 2005-04-02 11:20:08 得分 3
使用堆排序的话 复杂度恒定 约为N* log2 NTop
8 楼huanyun（无妻徒刑）回复于 2005-04-02 11:21:23 得分 5
这是一个比较大的算法呢，我现在手中就有一个这样的问题（有7个不同的数，要得到所有按不同位置排列出来的结果），我用过穷举法（通过7个循环），效率太低了，想找一个更好的算法，
简单 7个数排序 越大的放前面
比如 9432467 数字排序 9764432 就是最大的Top
9 楼jadeluo（秀峰）回复于 2005-04-02 12:50:59 得分 8
楼主，不同的排序算法，它们的最坏情况是不同的。
设有以下这种交换排序算法:
数组a(1), a(2), a(3), ..., a(n)
如果a(1), ..., a(i-1)是已经按要求排序好了的, 则对a(i), ..., a(n)的排序可以这样进行:
1. 找出a(i), ..., a(n)中的最小值元素的下标j；
2. 交换a(i)和a(j)；
3. 对a(i+1), ..., a(n)继续以上处理，直至全部处理完毕。
对于这种算法, 如果数组初始情况类似于: 2, 3, 4, 5, 6, 7, 8, 9, 1的话, 就是所谓的最坏情况了，此时需要交换的次数是n-1次。
Top
