|
|
若设R[1...n]为待排序的n个记录,R[1...i-1]已按照主关键字由小到大排序,且任意x∈R[1...i-1],y∈R[i...n]满足x.key≤y.key,则选择排序的主要思路如下。
|
|
|
(1)反复从R[i...n]中选出关键字最小的结点R[k]。
|
|
|
(2)若i≠k,则将R[i]与R[k]交换,使得R[1...i]有序且保持原来的性质。
|
|
|
|
|
|
|
|
可见,选择排序不管原先序列是否有序,其排序需要比较的次数均为n(n-1)/2;同时,由于相等的两个元素,位置相对在前的可能被交换到后面,故该选择排序是不稳定的。
|
|
|
|
|
|
|
|
|
|
|
|