选择排序采用了我们在生活中常用的一种方式,同样以扑克牌为例对桌上的5张扑克牌进行升序排序。
这一次,我们纵观全局并选出最小的一张。在刚才那组扑克中可以发现梅花3是最小的:
我们将其取出拿到手上,其余牌则继续放在桌上:
然后重复之前的操作,可以得到第二大的牌“梅花5”:
将其拿起并放在“梅花3”的右边。
当桌面上所有的牌都拿起后,我们手上的牌将会以从小到大的顺序放置。
选择排序就与此过程类似。只是说在代码实现中,我们实际只在一个列表中完成整个操作。选择排序同样会在序列中多次迭代,但与冒泡排序不同的是,它在每一次迭代中仅会做一次交换。下面是一个简单的示例代码:
# Sorts a sequence in ascending order using the selection sort algorithm. def selectionSort( theSeq ): n = len( theSeq ) for i in range( n - 1 ): # Assume the ith element is the smallest. smallNdx = i # Determine if any other element contains a smaller value. for j in range( i + 1, n ): if theSeq[j] < theSeq[smallNdx] : smallNdx = j # Swap the ith value and smallNdx value only if the smallest value is # not already in its proper position. Some implementations omit testing # the condition and always swap the two values. if smallNdx != i : theSeq[i], theSeq[smallNdx] = theSeq[smallNdx], theSeq[i]
从性能的角度来看,选择排序会对一个列表执行n - 1次循环,其时间复杂度依然是O(n2)。它与冒泡排序唯一不同的是将元素互换的复杂度将至O(n)。
更多请参考:Rance D. Necaise - 《Data Structures and Algorithms Using Python》