排序算法（3）——选择排序

vlambda
2020-05-21

排序算法（3）——选择排序

今天介绍选择排序的两种排序方法，简单选择排序和堆排序。

选择排序

概念：

选择排序是一种很简单的排序算法，无论用什么数据进行排序，时间复杂度都是 O(n²) 。所以用到它的时候，数据规模越小越好。

算法步骤：

（1）首先，遍历所有元素，在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

（2）再从剩余未排序元素中继续搜索最小（大）元素，然后放到已排序序列的末尾。

（3）重复第二步，直到所有元素均排序完毕。

算法复杂度：

时间复杂度----平均：O(n^2) | 最坏：O(n^2) | 最好：O(n^2)

空间复杂度----O(1)

稳定性----不稳定

排序算法（3）——选择排序

实例：

（1）递归版本

def select_sort(list1, count): # 用来存储最大元素 max = list1[0] for i in range(count): if list1[i] < max: continue else: max = list1[i] maxi = i # 最大值放到列表最后一个位置，最后一个位置的元素交换到最大值的位置存放。 list1[count-1], list1[maxi] = list1[maxi], list1[count-1] while count > 1: count -= 1 select_sort(list1, count) return list1
if __name__ == '__main__': list1 = [34, 23, 78, 35, 98, 34, 18, 88, 47, 51] print(list1) sort_list = select_sort(list1, len(list1)) print(sort_list)

（2）常规循环版本

def select_sort2(ls): for i in range(len(ls) - 1): # 记录最小数的索引 Min_index = i for j in range(i + 1, len(ls)): if ls[j] < ls[Min_index]: Min_index = j # i 不是最小数时，将 i 和最小数进行交换 if i != Min_index: ls[i], ls[Min_index] = ls[Min_index], ls[i] return ls
if __name__ == '__main__': list1 = [34, 23, 78, 35, 98, 34, 18, 88, 47, 51] print(list1) sort_list = select_sort2(list1) print(sort_list)

堆排序

概念：

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。元素堆积的结构是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
如果不理解，建议先看一下二叉树相关知识
https://blog.csdn.net/Tonywu2018/article/details/89480282

算法实现过程：

（1）创建一个堆 H[0……n-1]；

（2）把堆首（最大值）和堆尾互换；

（3）把堆的尺寸缩小 1，目的是把新的数组顶端数据调整到相应位置；

（4）重复步骤 2，直到堆的尺寸为 1。

排序算法（3）——选择排序

算法复杂度：

时间复杂度----平均： Ο(nlogn) | 最坏： Ο(nlogn) | 最好： Ο(nlogn)

空间复杂度----O(1)

稳定性----不稳定

实例：

def buildMaxHeap(ls): import math # 建立堆结构，根据元素总数，分为左右两边 # 以下for循环为了遍历每个子树结构中的父节点 for i in range(math.floor(len(ls) / 2), -1, -1): heapify(ls, i)# 以下函数对堆结构中的每一个子树结构中元素进行排序def heapify(ls, i): # i代表父节点的索引 left = 2*i+1 right = 2*i+2 largest = i # 因为建立的是完全二叉树，所以元素个数为偶数时， # 可能存在超出元素个数的索引，所以要写上left < ls_len if left < ls_len and ls[left] > ls[largest]: largest = left if right < ls_len and ls[right] > ls[largest]: largest = right
 if largest != i: # 子树结构中较大的数会被交换到当前子树的父节点上 trans(ls, i, largest) # 然后以最大值为子树的父节点继续比较它与子节点元素大小 # （有左右两个子节点，假如是右子节点比较大被交换位置到父节点，它还需要与左子节点比较大小） heapify(ls, largest)
def trans(ls, i, j): ls[i], ls[j] = ls[j], ls[i]
def heap_sort(ls): global ls_len ls_len = len(ls) buildMaxHeap(ls) for i in range(len(ls) - 1, 0, -1): # 把堆首的最大值和堆尾的值交换，堆尾就是二叉树结构的右叶子结点 trans(ls, 0, i) # 最大值到列表最后一位以后就不管它了，把列表长度减一 ls_len -= 1 # 此时堆首元素变了，可能不是最大，又再次进行排序 heapify(ls, 0) return ls
if __name__ == '__main__': list1 = [34, 23, 78, 35, 98, 34, 18, 88, 47, 51] print(list1) sort_list = heap_sort(list1) print(sort_list)