2 jian yun rui Jian_Yun_Rui 于 2016.09.23 22:48 提问

C++算法中有关排序的问题

给定一组无序的数 比如{8,9,1,5,6,3,4},如何可以实现求得让其从小到大排序并且移动元素的次序最小,设计思想是什么???

2个回答

leewers
leewers   2016.09.23 23:25
已采纳

想了一下,还是选择排序移动元素次数最少

Jian_Yun_Rui
Jian_Yun_Rui 回复leewers: 谢谢 对的,理解了,十分感谢
大约一年之前 回复
leewers
leewers 回复JIAN_BOY_RISE: 其实要明确一点,这道题最终目的还是要排序,但是需要排序的方法移动元素的次数是最少的。其实排序的方法也就是那么几种,而根据题意又限制在了原址排序,那就限定在了冒泡排序,选择排序,插入排序,堆排序和快速排序这几种。其中选择排序的思想是,每次将数组剩余部分中最小的元素移动(其实准确来说应该是交换,因为中间的元素并没有移动)到数组左边已经有序的部分的末端,那么最坏情况下,也就只需要移动n次即可完成排序。而快速排序中partiton(数组划分)的步骤其实进行了大量的元素交换,最坏情况下每次partition要进行o(n)次交换,而且快速排序大多数情况下并不止一次partition。因此选择排序的思想移动次数还是比较少的。
大约一年之前 回复
Jian_Yun_Rui
Jian_Yun_Rui 不好意思可能是我表述的不太清楚,本意并不是说要用哪种具体的算法来设计才可以,而是意思是自己设计一种算法,让其类似的无序数每次排成从小到大的有序数所需要移动的此数是最小的
大约一年之前 回复
caozhy
caozhy   Ds   Rxr 2016.09.23 23:43

无序数,在典型情况下,用快速排序比较/移动次数最少。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!