当前位置: 首页 >> 科技 >
选择排序的特点是?一组无序数据原理是什么?
来源:创视网     时间:2023-04-11 09:38:27

选择排序的特点

最好、最坏和平均时间复杂度都是 O(n^2) ; 空间复杂度是 O(1) , 它是一个原地排序算法

选择排序不是一个稳定的排序算法,因为每次的交换会改变相等元素之间的相对位置

运行时间与输入无关,因为每次扫描并不能为下一次扫描提供什么有用的信息

数据的移动是最少的,只有 n 次,交换次数等于数组的长度,这种线性性质是很多排序方法做不到的

一组无序数据原理

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变。再比较a[3]与a[4],以此类推,最后比较a[n-1]与a[n]的值。这样处理一轮后,a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮,以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似,若a[1]小于a[2]则交换两者的值,否则不变,后面以此类推。 总的来讲,每一轮排序后最大(或最小)的数将移动到数据序列的最后,理论上总共要进行n(n-1)/2次交换。[2]

推荐新闻 +
猜您喜欢 +

X 关闭

X 关闭