一. 算法描述
选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成。
以下面5个无序的数据为例:
56 12 80 91 20(文中仅细化了第一趟的选择过程)
第1趟:12 56 80 91 20
第2趟:12 20 80 91 56
第3趟:12 20 56 91 80
第4趟:12 20 56 80 91
二. 算法分析
平均时间复杂度:O(n2)
空间复杂度:O(1) (用于交换和记录索引)
稳定性:不稳定 (比如序列【5, 5, 3】第一趟就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)
三. 算法实现
public class SelectionSort { public static void main(String[] args) { int len = 15; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; jary[j]) { minIndex = j; //记录较小的索引 compareCount++; } } if (minIndex != i) {//如果跟左边的记录索引不同,则交换 ary[i] = ary[minIndex] + (ary[minIndex] = ary[i]) * 0; changeCount++; } } System.out.println("\n-------升序排序后------比较次数:" + compareCount + ",交换次数" + changeCount); for (int j = 0; j
打印
-------排序前------ 125 350 648 789 319 699 855 755 552 489 187 916 596 731 852 -------降序排序后------比较次数:26,交换次数13 916 855 852 789 755 731 699 648 596 552 489 350 319 187 125 -------升序排序后------比较次数:56,交换次数7 125 187 319 350 489 552 596 648 699 731 755 789 852 855 916