選擇排序（Selection Sort）原理是從待排序的數(shù)據(jù)中選取最小或最大的一個(gè)元素存放在序列的起始位置儿惫，然后在剩余未排序的元素中繼續(xù)尋找最小或最大的元素放到已排序序列末尾舟山，直至待排序的數(shù)據(jù)元素個(gè)數(shù)為0执隧。
復(fù)雜度分析
選擇排序的比較次數(shù)依次為：n - 1形真、n - 2、...、1贡避，等差數(shù)列求和：n * (n - 1 + 1) / 2 = n2 / 2战转，時(shí)間復(fù)雜度O(n2)搜立。
選擇排序和冒泡排序的時(shí)間復(fù)雜度一樣，但因選擇排序?qū)嶋H執(zhí)行的交換操作很少槐秧，最多只有n - 1次啄踊，而冒泡排序最壞情況下要執(zhí)行n2/2次交換，因此選擇排序性能優(yōu)于冒泡排序刁标。
Java 代碼實(shí)現(xiàn)
import java.util.Arrays;
public class SelectionSort {
public static void sort(int[] data) {
for (int i = 0; i < data.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < data.length; j++) {
minIndex = data[minIndex] < data[j] ? minIndex : j;
}
if (minIndex != i) {
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
System.out.println(Arrays.toString(data));
}
}
public static void main(String[] args) {
int[] data = {34, 24, 93, 1, 32, 98, 18, 39};
sort(data);
}
}
運(yùn)行結(jié)果
[1, 24, 93, 34, 32, 98, 18, 39]
[1, 18, 93, 34, 32, 98, 24, 39]
[1, 18, 24, 34, 32, 98, 93, 39]
[1, 18, 24, 32, 34, 98, 93, 39]
[1, 18, 24, 32, 34, 98, 93, 39]
[1, 18, 24, 32, 34, 39, 93, 98]
[1, 18, 24, 32, 34, 39, 93, 98]
