选择排序

介绍

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

python描述

import random

def find_min_one(array, start, end):
    index = start
    small = array[start]
    for i in range(start, end):
        if array[i] < small:
            small = array[i]
            index = i
    return index 

def select_sort(array):
    for i in range(len(array)):
        start = i
        end = len(array)
        index = find_min_one(array, start, end)
        array[i], array[index] = array[index], array[i]
    return array

array = [random.randint(0, 100) for i in range(10)]
print("初始数组",array)
res = select_sort(array)
print("排序后",res)

java描述

public class Selection {
    
    // 实现了Comparable接口的都可以比较
    public static void sort(Comparable[] a){
        int N = a.length;
        for (int i = 0; i < N; i++){
            int min = i;
            for (int j = i + 1; j < N; j++){
                if(less(a[j], a[min])){
                    min = j;
                }
            }
            exch(a, i, min);
        }   
    }
    
    public static void main(String[] args) {
        Integer[] a = {2, 3, 1, 3, 4, 8, 6, 10};
        sort(a);
        assert isSorted(a);
        show(a);
    }
    
    public static boolean less(Comparable V , Comparable W){
        return V.compareTo(W) < 0;
    }
    
    public static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++){
            System.out.print(a[i] + " ");   
        }
        System.out.println();
    }
    
    // 测试数组元素是否有序
    public static boolean isSorted(Comparable[] a){
        for (int i = 1; i < a.length; i++){
            if(less(a[i], a[i-1])){
                return false;
            }
        }
        return true;
    }
}

算法分析

第一次需要检查n个元素，但随后检查的元素数依次为n – 1, n – 2, …, 2和1，所以选择排序的最坏时间复杂度是O(n²)