排序算法之选择排序：java、Kotlin、python代码实现

选择排序(Selection Sort)

选择排序就是找到数组中最小元素将其和数组第一个元素交换位置，然后在剩下的元素中找到最小元素并将其与数组第二个元素进行交换，以此类推，直至整个数组排序结束。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4495.html

算法思路

1. 找到数组中最小元素并将其和数组第一个元素交换位置
2. 在剩下的元素中找到最小元素并将其与数组第二个元素交换，直至整个数组排序

图片源自Visualgo文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4495.html

实现

Java

public class SelectionSort {

    public static void main(String[] args) {
        int[] unsortedArray = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
        selectionSort(unsortedArray);
        System.out.println("After sorted: ");
        for (int number : unsortedArray) {
            System.out.print(" " + number);
        }
    }

    private static void selectionSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        int min;
        int temp;
        for (int i = 0; i < length - 1; i++) {

            min = i;
            for (int j = length - 1; j > i; j--) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }

            if (array[i] > array[min]) {
                temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
    }
}
复制代码

Kotlin

object SelectionSortKt {

    fun selectionSort(array: IntArray) {
        if (array.isEmpty()) {
            return
        }

        val size = array.size
        var min: Int

        for (i in 0 until size - 1) {

            min = i
            (size - 1 downTo i)
                    .asSequence()
                    .filter { array[min] > array[it] }
                    .forEach { min = it }

            if (array[min] < array[i]) {
                val temp = array[i]
                array[i] = array[min]
                array[min] = temp
            }
        }
    }
}

fun main(args: Array<String>) {
    val unsortedArray = intArrayOf(6, 5, 3, 1, 8, 7, 2, 4)
    SelectionSortKt.selectionSort(unsortedArray)
    println("After sorted: ")
    unsortedArray.forEach {
        print(" $it")
    }
}
复制代码

Python3

#!/usr/bin/env python
# coding=utf-8


def selection_sort(arrayList):
    length = len(arrayList)
    minIndex = 0

    for i in range(length - 1):
        minIndex = i

        for j in range(length - 1, i, - 1):
            if (arrayList[minIndex] > arrayList[j]):
                minIndex = j

        if (arrayList[i] > arrayList[minIndex]):
            arrayList[i], arrayList[minIndex] = arrayList[minIndex], arrayList[
                i]


if __name__ == "__main__":
    arrayList = [6, 5, 3, 1, 8, 7, 2, 4]
    print("orgin array list: {0}".format(arrayList))
    selection_sort(arrayList)
    print("after sorted list: {0}".format(arrayList))

复制代码

时间复杂度

最好情况：交换 0 次，但是每次都要找到最小的元素，因此大约必须遍历 N*N 次，因此为 O(N^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4495.html

最坏情况 & 平均情况下：O(N^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4495.html

稳定性

由于每次都是选取未排序序列 A 中的最小元素 x 与 A 中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4495.html

总结

选择排序是和冒泡排序差不多的一种排序。和冒泡排序交换相连数据不一样的是，选择排序只有在确定了最小的数据之后，才会发生交换文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4495.html