python数据结构和算法(4)

排序算法

• 所谓排序，是一串记录，按照其中的某个关键字的大小，递增或递减的排列起来的操作
• 排序算法，就是如何使得记录按照要求排列的方法
• 排序算法的重要性
  • 在大量数据处理方面，一个优秀的算法可以节省大量的资源
  • 在各个领域中考虑到数据的各种限制和规范，要的到一个符合实际的优秀算法，得经过大量的推理和分析

算法的稳定性

具有相同关键字的记录经过排序后，相对位置保持不变，这样的算法是稳定性算法

• 不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
• 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

冒泡排序

冒泡排序是重复的走访要排序的元素列，依次比较两个相邻的元素，如果顺序(如从大到小，首字母从Z到A)错误，就把它们交换过来，走访元素的工作是重复进行的，直到没有相邻元素需要交换，则说明该元素列已经排序完成。

相邻的两个元，两两进行比较，第1轮比较完毕后，最大的元素，就会处于最大索引处

关注点：

1. 比较的总轮数
2. 每轮比较的次数
3. 哪两个元素进行了比较交换

总结：5个数字进行排序,共进行了 4 轮，以变量 i 代表轮数，则 i 的取值范围为 0,1,2,3，即range(0,4),如果n个元素进行排序，轮数i的取值范围为range(0,n-1)；以变量j 表示每轮比较的索引
第 1 轮 i = 0，进行了 4 次比较,j 的取值范围为 0,1,2,3
第 2 轮 i = 1，进行了 3 次比较,j 的取值范围为 0,1,2
第 3 轮 i = 2，进行了 2 次比较,j 的取值范围为 0,1
第 4 轮 i = 3，进行了 1 次比较,j 的取值范围为 0,1

j的最大取值范围为0,1,2,3,并且逐轮递减，即range(0,n-i-1)

# 冒泡排序
array = [5,3,4,7,2]
n = len(array)
for i in range(0,n - 1):
    print(i)
    for j in range(0,n-i-1):
        if array[j] > array[j+1]:
        	temp = array[j]
            array[j] = array[j+1]
            array[j+1] = temp
        

时间复杂度

最优时间复杂度 $O(n)$
最坏时间复杂度$O(n^2)$

选择排序

从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小(大)元素，然后放到已排序的序列的末尾，以此类推，直到全部待排序的数据元素的个数为零

array = [5,3,4,7,2]
n = len(array)
for i in range(0,n-1):
    min_index = i
    for j in range(i + 1,n):
        if array[j] < array[min_index]:
            min_index = j
    temp = array[i]
    array[i] = array[min_index]
    array[min_index] = temp