BasicSort 之 SelectSort

一、选择排序

核心：不断地选择剩余元素中的最小者。

找到数组中最小元素并将其和数组第一个元素交换位置。在剩下的元素中找到最小元素并将其与数组第二个元素交换，直至整个数组排序。

性质：

比较次数=(N-1)+(N-2)+(N-3)+...+2+1~N^2/2交换次数=N运行时间与输入无关数据移动最少

二、实现

　　实现方式一：

package sort; public class SelectSort { /** * 选择排序： 不断地选择剩余元素中的最小者。 * 1、找到数组中最小元素并将其和数组第一个元素交换位置。 2、在剩下的元素中找到最小元素并将其与数组第二个元素交换，直至整个数组排序。 复杂度分析： n^2/2 交换N次 ， 运行时间与输入无关，数据移动最少 */ public static void main(String[] args) { int[] unsortedArray = new int[]{8, 5, 2, 6, 9, 3, 1, 4, 0, 7} ; selectSort(unsortedArray) ; System.out.println("After sort: "); for (int item : unsortedArray) { System.out.print(item + " "); } } public static void selectSort(int[] array){ int len = array.length ; for (int i = 0; i < len; i++) { for (int item : array) { System.out.print(item + " "); } System.out.println(); int min_index = i ; for (int j = i+1; j < len; j++) { if (array[j] < array[min_index]) { min_index = j ; } } int temp = array[min_index] ; array[min_index] = array[i]; array[i] = temp ; } } }

　　实现方式二：

　　定义一个类，进行存储元素和排序、显示等操作。

package selectSort; public class ArraySel { private long[] a ; // ref to Array a private int nElems ; // number of data items public ArraySel(int max){ // constructor a = new long[max] ; // create the array nElems = 0 ; // no items yet } public void insert(long value){ // put element into array a[nElems] = value ; // insert it nElems++ ; // increment size } public void display(){ // display array contents for (int i = 0; i < nElems; i++) { System.out.print(a[i] + " "); } System.out.println(); } public void selectSort(){ int out , in , min; for (out = 0; out < nElems-1; out++) {// outer loop min = out ; // minimum for(in = out+1; in < nElems; in++){ // inner loop if(a[in] < a[min]){ min = in ; // we have a new min } } swap(out,min); // swap them } } private void swap(int one, int two) { long temp = a[one] ; a[one] = a[two] ; a[two] = temp ; } }

　　定义主函数入口main函数。

package selectSort; public class SelectSort { public static void main(String[] args) { int maxSize = 100 ; ArraySel arr ; arr = new ArraySel(maxSize) ; arr.insert(0); arr.insert(6); arr.insert(5); arr.insert(3); arr.insert(1); arr.insert(8); arr.insert(7); arr.insert(2); arr.insert(4); arr.insert(9); arr.display(); arr.selectSort(); arr.display(); } }

　　注意：下标在小于或等于out的位i置的元素总是有序的。

　　部分内容参考Github。https://algorithm.yuanbin.me/zh-hans/basics_sorting/selection_sort.html

 

转载于:https://www.cnblogs.com/Wyao/p/7043613.html

相关资源：JAVA上百实例源码以及开源项目