# 冒号排序

# 基本算法思路：
# 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
# 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
# 针对所有的元素重复以上的步骤，直到没有任何一对数字需要比较。# print('未排序',nums)
# # 对比出元素中的最大值， 元素的个数 - 1
# for m in range(len(nums)-1):
#     # 最大值的次数需要  m-1轮 因为每一轮对比出的 最大值无需大此对比所以减一；
#     for n in range(len(nums)-m-1):
#         if nums[n]  > nums[n+1]:
#             nums[n],nums[n
#                          +1] = nums[n+1],nums[n]
# print('已经排序好了',nums)# 时间复杂度
#1. 这个时间复杂度还是很好计算的：外循环和内循环以及判断和交换元素的时间开销；
#2. 最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[n(n - 1)] / 2；所以最优的情况时间复杂度为：O(n ^ 2)；
#3.最差的情况也就是开始的时候元素是逆序的，那么每一次排序都要交换两个元素，则时间花销为：[3n(n - 1)] / 2；（其中比上面最优的情况所花的时间就是在于交换元素的三个步骤）；所以最差的情况下时间复杂度为：O(n ^ 2)；
#
#            综上所述：
#
#. 最优的时间复杂度为：O(n ^ 2) ；有的说
# .O(n)，下面会分析这种情况；
# .最差的时间复杂度为：O(n ^ 2)；
# .平均的时间复杂度为：O(n ^ 2)；
## 空间复杂度
#
# 1. 空间复杂度就是在交换元素时那个临时变量所占的内存空间；
#2. 最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；
#3. 最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
# 4.平均的空间复杂度为：O(1)；
#5. 最优时间复杂度n

                        #选择排序# 基本算法思路：
#1.找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置；
# 2.在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置;
# 3.如此循环，直到整个数组排序完成。
# 4.若是由大到小也是同样方法，只需要修改比较大小的符号；
# print('未排序；',nums)
#   每一轮都找出一个最小 的 和默认第一个最小的元素交换位置;
#
# ln = len(nums)
# # 两两对比  只需要 对比  ln - 1 轮即可
# for i in range(ln-1):
#     # 默认第一个为最大的
#     min_index =  i
#     # i+1 是给下一个元素进行对比
#     for j in range(i+1,ln):
#         # 进行对比  比出最大的
#         if nums[j]  >  nums[min_index]:
#             min_index =  j
#             # 通过下标 将做大的元素 和 最小的元素进行 交换位置
#             nums[min_index],nums[i] =  nums[i],nums[min_index]
# print('已排序',nums)# 时间复杂度
#         选择排序的时间复杂度不像前面几种排序方法那样，前面几种排序方法的时间复杂度不是一眼就能看出来的，而是要通过推导计算才能得到的。一般会涉及到递归和完全二叉树，所以推导也不是那么容易。但是选择排序就不一样了，你可以很直观的看出选择排序的时间复杂度：就是两个循环消耗的时间；
#        比较时间：T = （n-1)）+ （n -2）+（n - 3）.... + 1;  ===>>  T =  [n*(n-1) ] / 2；
#       交换时间：最好的情况全部元素已经有序，则 交换次数为0；最差的情况，全部元素逆序，就要交换 n-1 次；
#        所以最优的时间复杂度  和最差的时间复杂度   和平均时间复杂度  都为 ：O(n^2)
#
# 空间复杂度
#         空间复杂度，最优的情况下（已经有顺序）复杂度为：O(0) ；最差的情况下（全部元素都要重新排序）复杂度为：O(n );；平均的时间复杂度：O(1)