一 概述
设所排序序列的记录个数为n,i 取 1,2,…,n-1 。 从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小(或最大)的记录,与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。
二 性能分析
在简单选择排序过程中,所需移动记录的次数比较少。
最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。
最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。
简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。
当i=1时,需进行n-1次比较;
当i=2时,需进行n-2次比较;
依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为O(n^2),进行移动操作的时间复杂度为O(n)。
简单选择排序是不稳定排序。
三 程序实践
以排序数组{3,2,1,4,6,5}为例
static int selectSort(int[] a, int length){
if (a == null || length <= 1){
return -1;
}
if (length > a.length){
return -1;
}
for (int i = 0; i < length; i++){
int min = a[i];
int index = 0;
for (int j = i + 1; j < length; j++){
if (a[j] < min){
min = a[j];
index = j;
}
}
if (index > 0){
int tmp = a[i];
a[i] = a[index];
a[index] = tmp;
}
}
return 0;
}
网友评论