7.选择排序-java

[ruotongyu (Dongle)]

选择排序与插入排序类似。

维护有序序列：

# 选择排序
import java.util.Arrays;

public class SelectionSort {
    public void sort(int[] data) {
        int length = data.length;
        if (length <= 1) {
            return;
        }
        for (int i = 0; i < data.length; i++) {
            int minIndex = i;
            int minValue = data[i];
            int j = i;
            for (; j < length; j++) {
                if (data[j] < minValue) {
                    minIndex = j;
                    minValue = data[j];
                }
            }
            data[minIndex] = data[i];
            data[i] = minValue;

        }
    }

    public static void main(String[] args) {
        SelectionSort selectionSort = new SelectionSort();
        int[] data = new int[] { 5, 2, 1, 4, 10, 3, 6, 7 };
        selectionSort.sort(data);
        int[] data2 = new int[] { 1, 2, 3, 4, 5, 6, 7, 10 };
        System.out.println(Arrays.equals(data, data2));

    }
}

时间复杂度

• 最好：O(n²)
• 最坏：O(n²)
• 平均：O(n²)

空间复杂度
O(1)

稳定