选择排序 | Wpz's Blog

选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序是表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度，所以用到它的时候，数据规模越小越好。选择排序还有一个好处就是不占用额外的内存空间。

算法描述

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1, 2 , 3, …, n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]。该趟排序从当前无序区中选出最小元素（按升序排序），将它与无序区的第1个记录交换，交换结束后，当前有序区和无序区分别为R[1..i]和R[i+1..n]；
重复步骤2，当n-1趟结束后，数组有序化了。

动图演示

算法分析

最佳情况：T(n) = O(n²)
最差情况：T(n) = O(n²)
平均情况：T(n) = O(n²)

代码实现

Java

Java 实现

import java.util.Arrays;

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            if (index != i) {
                int t = arr[index];
                arr[index] = arr[i];
                arr[i] = t;
            }
            System.out.printf("排序第%2d次后数组为：%s\n", i + 1, Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        System.out.printf("原始数组：%s\n", Arrays.toString(arr));
        selectionSort(arr);
        System.out.printf("排序后数组：%s\n", Arrays.toString(arr));
    }
}

Python

Python 实现

def selection_sort(arr):
    for i in range(0, len(arr) - 1):
        index = i
        for j in range(i + 1, len(arr)):
            if arr[index] > arr[j]:
                index = j
        if index != i:
            arr[index], arr[i] = arr[i], arr[index]
        print('排序第%2d次后数组为：%s' % (i + 1, arr))


if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print('原始数组：', arr)
    selection_sort(arr)
    print('排序后数组：', arr)

Go

Go 实现

package main

import (
    "fmt"
)

func SelectionSort(arr *[15]int) {
    for i := 0; i < len(arr)-1; i++ {
        index := i
        for j := i + 1; j < len(arr); j++ {
            if arr[index] > arr[j] {
                index = j
            }
        }
        if index != i {
            arr[index], arr[i] = arr[i], arr[index]
        }
        fmt.Printf("排序第%2d次后数组为：%v\n", i+1, *arr)
    }
}

func main() {
    arr := [15]int{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
    fmt.Printf("原始数组：%v\n", arr)
    SelectionSort(&arr)
    fmt.Printf("排序后数组：%v\n", arr)
}