首页 > 代码库 > Java 实现选择排序
Java 实现选择排序
选择排序:
原理:依次从数组最左边取一个元素,与之后的位置上的元素比较,如果大于/小于(取决于需要升序排还是降序排),则保存较大/较小元素的索引
当一轮比较后,将保存的较大/较小元素的索引与 这轮开始比较的左边元素置换
改进了冒泡排序,交换次数从O(N^2)减少到O(N), 而比较次数还是O(N^2)
/** * 选择排序 * 比较次数 O(N^2), 交换O(N) * @author stone * */ 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; j < len; j++) { ary[j] = random.nextInt(1000); } System.out.println("-------排序前------"); // ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //测试交换次数 // ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //测试交换次数 for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } selectDesc(ary); selectAsc(ary); } /* * 选择排序:降序 */ static void selectDesc(int[] ary) { int compareCount = 0;//比较次数 int changeCount = 0;//交换次数 int len = ary.length; int maxValueIndex = -1; //记录一轮比较下来的最小值索引 for (int i = 0; i < len - 1; i++) { maxValueIndex = i; //从0开始 for (int j = i + 1; j < len; j++) { if (ary[maxValueIndex] < ary[j]) { maxValueIndex = j; //记录较大的索引 compareCount++; } } // System.out.println("minValueIndex==" + maxValueIndex); ary[i] = ary[maxValueIndex] + (ary[maxValueIndex] = ary[i]) * 0;//一步交换 changeCount++; } System.out.println("\n-------降序排序后------比较次数:" + compareCount + ",交换次数" + changeCount); for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } } /* * 选择排序:升序 */ static void selectAsc(int[] ary) { int compareCount = 0, changeCount = 0; int len = ary.length; int minIndex = -1; for (int i = 0; i < len - 1; i++) { minIndex = i; for (int j = i + 1; j < len; j++) { if (ary[minIndex] > ary[j]) { minIndex = j; //记录较小的索引 compareCount++; } } ary[i] = ary[minIndex] + (ary[minIndex] = ary[i]) * 0; changeCount++; } System.out.println("\n-------升序排序后------比较次数:" + compareCount + ",交换次数" + changeCount); for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } } }
打印
-------排序前------ 221 503 967 760 366 453 279 673 959 896 845 974 972 983 313 -------降序排序后------比较次数:25,交换次数14 983 974 972 967 959 896 845 760 673 503 453 366 313 279 221 -------升序排序后------比较次数:56,交换次数14 221 279 313 366 453 503 673 760 845 896 959 967 972 974 983
Java 实现选择排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。