1.7 堆排序
堆是一种特殊的树形数据结构，其每个结点都有一个值，通常提到的堆都是指一棵完全二叉树，根结点的值小于（或大于）两个子结点的值，同时根结点的两个子树也分别是一个堆。
1.7.1 算法思想：
对于给定的序列，初始把这些记录看成一刻顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素进行交换后，堆的最后一个元素即为最大记录；接着将前(n-1)个元素重新调整为一个大顶堆，在将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩一个元素为止，该记录即为最小记录，此时可得到一个有序序列。
过程：1. 构建堆；2. 交换堆顶元素与最后一个元素的位置
1.7.2 实现
def heapify(unsorted, index, heap_size): largest = index left_index = 2 * index + 1 right_index = 2 * index + 2 if left_index < heap_size and unsorted[left_index] > unsorted[largest]: largest = left_index if right_index < heap_size and unsorted[right_index] > unsorted[largest]: largest = right_index if largest != index: unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest] heapify(unsorted, largest, heap_size) def heap_sort(unsorted): """堆排序""" length = len(unsorted) for i in range(length // 2 - 1, -1, -1): heapify(unsorted, i, length) for i in range(length - 1, 0, -1): unsorted[0], unsorted[i] = unsorted[i], unsorted[0] heapify(unsorted, 0, i) return unsorted if __name__ == '__main__': gList = [5, 4, 2, 1, 7, 3, 6] print("-----yuzhou1su-----", gList) print("-----堆排序后:", heap_sort(gList))
1.7.3 堆排序分析
时间复杂度： 主要耗费在创建堆和反复调整堆上，最坏情况下，时间复杂度也为O(nlogn)
空间复杂度：O(1)
稳定性： 不稳定
1.8 计数排序
1.8.1 算法思想
对于某种整数 K，计数排序假定每个元素都是 1 到 K 范围内的整数。 计数排序的基本思想是为每个输入元素 x 确定小于 x 的元素数量， 此信息可用于直接将其放置在正确的位置。 例如，如果 10 个元素小于 x，则 x 属于输出中的位置 11。
1.8.2 实现
# -*- coding: utf-8 -*- # @Author : 宇宙之一粟 # @File : counting_sort.py def counting_sort(unsorted): """计数排序 :param unsorted：给定一组序列 :return: 升序序列 """ if unsorted is []: return [] # 根据给定序列求信息 coll_len = len(unsorted) coll_max = max(unsorted) coll_min = min(unsorted) # 创建计数数组 counting_arr_length = coll_max + 1 - coll_min counting_arr = [0] * counting_arr_length # 计数操作 for number in unsorted: counting_arr[number - coll_min] += 1 # 将每个位置与它的前一个相加。counting_arr[i]统计出多少个 # element <= i的元素 for i in range(1, counting_arr_length): counting_arr[i] = counting_arr[i] + counting_arr[i - 1] # 创建保存升序结果的数组 ordered = [0] * coll_len for i in reversed(range(0, coll_len)): ordered[counting_arr[unsorted[i] - coll_min] - 1] = unsorted[i] counting_arr[unsorted[i] - coll_min] -= 1 return ordered if __name__ == '__main__': gList = [5, 4, 2, 1, 3, 6] print("-----yuzhou1su：", gList) print("-----计数排序后:", counting_sort(gList))
1.8.3 计数排序分析
时间复杂度: O(n)ifK=O(n)
空间复杂度：O(n)ifK=O(n)
Ps: 如果 K 特别大，时间复杂度会很高；如果面试官让你设计数据规模小的线性排序算法，可能就是考察计数排序
1.9 桶排序
1.9.1 算法思想
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
1.9.2 实现
# -*- coding: utf-8 -*- import math def insertion_sort(collection): for i in range(1, len(collection)): temp = collection[i] index = i while index > 0 and temp < collection[index - 1]: collection[index] = collection[index-1] index -= 1 collection[index] = temp def bucket_sort(collection): code = hashing(collection) buckets = [list() for _ in range(code[1])] for i in collection: x = rehashing(i, code) buck = buckets[x] buck.append(i) for bucket in buckets: insertion_sort(bucket) ndx = 0 for buc in range(len(buckets)): for val in buckets[buc]: collection[ndx] = val ndx += 1 return collection def hashing(collection): m = collection[0] for i in range(1, len(collection)): if m < collection[i]: m = collection[i] result = [m, int(math.sqrt(len(collection)))] return result def rehashing(i, code): return int(i / code[0] * (code[1] - 1)) if __name__ == '__main__': gList = [5, 4, 2, 1, 3, 6] print("-----yuzhou1su：", gList) print("-----桶排序后:", bucket_sort(gList))
1.9.3 桶排序分析
- 时间复杂度:O(n)
- 空间复杂度:O(n)
1.10 基数排序
1.10.1 算法思想
与计数排序/桶排序类似，基数排序跟输入元素相关。比如：根据基数 d 对给定序列进行排序，这意味着所有的数字都是 d 位数。过程：
- 取每个元素的最低有效位
- 根据该数字对元素列表进行排序，但保持相同数字的元素顺序
- 用更高有效位重复排序，直到最高位
1.10.2 实现
def radix_sort(unsorted): radix = 10 max_len = False tmp, placement = -1, 1 while not max_len: max_len = True buckets = [list() for _ in range(radix)] for i in unsorted: tmp = int(i / placement) buckets[tmp % radix].append(i) if max_len and tmp > 0: max_len = False a = 0 for b in range(radix): buck = buckets[b] for i in buck: unsorted[a] = i a += 1 # move to next digit placement *= radix return unsorted if __name__ == '__main__': gList = [5, 4, 2, 1, 3, 6] print("-----yuzhou1su：", gList) print("-----基数排序后:", radix_sort(gList))
1.10.3 基数排序分析
基数排序适用于位数小的数字序列。
- 时间复杂度: O(nlog(r)m)，其中 r 为所采取的基数，而 m 为堆数
- 稳定性：稳定
1.11 其他排序
- 拓扑排序：在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。
- 外部排序：大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
- 位图排序：当待排序数据规模较大，而堆内存大小又没有限制时，位图排序则最高效。
- Tim-sort：Python 的 list 标准排序算法，由 Tim Peters 设计。本质上是一种自下而上的归并排序，利用一些数据的初始运行，之后进行额外的插入排序。Tim-sort 也成为 Java7 中数组排序的默认算法。
2. 各种排序算法比较？
根据上图总结：
- 不稳定算法有：选择、快速、希尔、堆 ( 记忆口诀："快选七(希)堆不稳定的排序")
- 时间复杂度O(n2)：选择、冒泡、插入
- 时间复杂度O(nlogn)：快速、归并、堆、希尔
- 时间复杂度O(n)：计数、桶
- 空间复杂度O(1)：选择、插入、冒泡、希尔、堆
- 空间复杂度O(n)：归并、计数、桶
- 空间复杂度O(logn)：快速排序
3.总结
一定要根据数据的规模、规律来给出合适的算法，不能觉得快速排序名字就以为是快速的，切记不能什么排序问题都回答快排。
- 虽然插入排序和冒泡排序平均速度较慢，但当初始序列整体或局部有序时，这两者效率较高
- 排序数据较小，且不要求稳定的情况下，选择排序效率较高；要求稳定，选择冒泡排序。
- 堆排序在更大的序列上往往优于快速排序和归并排序。
- 针对小数据追求线性时间复杂度，考虑计数排序和桶排序
- 除了上面几种常见的排序算法，还有众多其他排序算法，每种排序算法都有其最佳适用场合。具体情况具体分析。
