选择排序(Selection Sort)
选择排序就是找到数组中最小元素将其和数组第一个元素交换位置,然后在剩下的元素中找到最小元素并将其与数组第二个元素进行交换,以此类推,直至整个数组排序结束。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4495.html
算法思路
- 找到数组中最小元素并将其和数组第一个元素交换位置
- 在剩下的元素中找到最小元素并将其与数组第二个元素交换,直至整个数组排序
图片源自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
作者:骑摩托马斯
链接:https://juejin.im/post/5a448afb6fb9a044fa1a2992
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4495.html