数据结构与算法：选择排序(原理讲解+python实现)

选择排序

选择排序是一种经典、简便的排序算法。在初级软件工程师的笔试面试中也经常出现是基础入门的算法之一

原理讲解

Python实习

 1 def selectionSort(arr, n):
 2     for i in range(n):
 3         min = i
 4         for j in range(i+1, n):
 5             if arr[j] < arr[min]:
 6                 min = j
 7 
 8         if min != i:
 9             arr[min], arr[i] = arr[i], arr[min]
10 
11 
12 if __name__ == '__main__':
13     # 将数组升序拍戏
14     # 1.将第一个元素作为min元素 在数组中第二个到最后的元素中找一个更小的元素 与min调换
15     # 2.第一个元素为数组最小元素 在第三个到最后元素中找最小元素与第二个元素替换
16     # 循环上一次步骤 至最后元素 得到排好序的数组
17     arr = [30, 40, 60, 50, 10, 20]
18     n = len(arr)
19     selectionSort(arr, n)
20     print(arr)

时间、空间复杂度、稳定性分析

选择排序的时间复杂度是O(n2) 当列表有序时排序次数n-1次 O(n) 当列表倒序时排序次数(n-1)(n-2)/2次 O(n2) 平均复杂度O(n2).

选择排序的空间复杂度是O(1) 期间没有涉及到新建列表唯一需要新的内存是存储交换元素时存放临时变量的内容。

选择排序是不稳定的排序在有序表与无序表元素交换的过程中，会破坏相等元素的前后顺序比如[5, 5, 3, 8, 9] 第一躺需要交换第一个5和3时两个5的顺序就相反了

总结

总体来讲，和冒泡排序在效率性能上是极为相似的不同是选择排序是不稳定的排序也正因为如此应用上冒泡排序占些优势。当对于初学算法的童鞋来讲这些基本的排序都应该能够深入理解起原理才行。