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

选择排序

选择排序就是找到数组中最小的元素，与数组的第一个元素交换，然后将剩余元素相加。找到数组中最小的元素，并与数组的第二个元素交换，以此类推，直到整个数组排序完毕。

算法思想

1. 找到数组中最小的元素，与数组第一个元素交换
2. 找到剩余元素中最小的元素，与数组第二个元素交换，直到整个数组排序

图片来自Visualgo

实现

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)

最坏平均情况：O(N^2)

稳定性

每次使用最小的元素未排序集合A中的x被选中并与A中的第一个元素交换，这样就超出了距离，元素之间的相对位置很可能被破坏，所以选择排序不稳定

总结

选择排序是一种类似气泡类型的。与冒泡排序交换连通数据不同，选择排序是在确定最小数据后才交换

作者：骑摩托车的马斯
链接：https://juejin.im/post/5a448afb6fb9a044fa1a2992
来源：掘金
版权属于作者。如需商业转载，请联系作者以获得许可。非商业转载请注明出处。