一)选择排序定义
选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。常用的选择排序方法有简单选择排序和堆排序。
二)简单选择排序的实现(java)
package com.fox; import java.util.Random; public class SelectionSort { public static void sort(int[] a) { for (int i = 0; i < a.length; i++) { int min = a[i]; int loc = i; for (int j = i + 1; j < a.length; j++) { if (a[j] < min) { min = a[j]; loc = j; } } if (loc != i) { a[loc] = a[i]; a[i] = min; } } } /** * @param args */ public static void main(String[] args) { int[] a = new int[100]; Random random = new Random(); for (int i = 0; i < a.length; i++) { a[i] = random.nextInt(100000); } // a = new int[] { 6, 7, 51, 2, 52, 8 }; long bt = System.currentTimeMillis(); SelectionSort.sort(a); System.out.println(System.currentTimeMillis() - bt); for (int a_ : a) System.out.println(a_); } }
该算法的时间复杂度为 O(n2)。并且排序是稳定的。