java 选择排序算法。java 中可以使用compareTo实现对象的比较.因此可以实现一个方法对员工按照姓名的排序,以下使用选择排序算法实现:

void sortByName(Employee[] emploees, int employeeCount) {

for (int i = 0; i < employeeCount – 1; i++) {

int minIndex = i;

// Find smallest name

for (int j = i + 1; j < employeeCount; j++) {

Employee e1 = emploees[j];

Employee e2 = emploees[minIndex];

// Compare two employee

if (e1.compareTo(e2) < 0) {

minIndex = j;

}

}

// Swap employees if necessary

if (minIndex != i) {

Emploee temp = employees[i];

emploees[i] = employees[minIndex];

employees[minIndex] = temp;

}

}

}

 

 

 

 

 

选择排序包含了一个嵌套的循环,我们使用其中的比较作为代表指令进行分析.以大小为n的数组为例,外循环执行n-1次.第一次执行循环,内循环执行n-1次,第二次执行外循环,内循环执行n-2次,最后一次执行外循环,内循环执行1次.因此,大小为n的数组进行的比较总次数为

 

(n-1)+(n-2)+…+1=n(n-1)/2=1/2n2-1/2n

 

因此选择排序在任何情况下都是O(n2).对于很大的数据集,用于交换元素的开销相当大,因为数据交换是在外循环中执行.因此这样的额外开销对于最差情况和平均情况都是线性的.