Hello,我是 Alex 007,一个热爱计算机编程和硬件设计的小白,为啥是007呢?因为叫 Alex 的人太多了,再加上每天007的生活,Alex 007就诞生了。 最近有一位小学妹 Coco 入坑了算法,结果上来就被几个排序算法给整懵逼了,各种排序眼花缭乱,也分不清什么时候该用什么排序了,于是哭着来找我来了。 在开始正式讲解之前呢,先来介绍一个工具,对数器: 拿第一个要讲的冒泡排序为例: 假如说 当然,一次验证的结果可能存在偶然性,所以我们可以多验证几次,如果对于大量随机的结果来说,我们的algorithm输出结果都正确,那么就有很大把握确定这个algorithm是right的。 比较类排序还是比较好理解的,就是两个元素之间比大小然后排队嘛,比较常规。 在算法层面,比较类排序由于其时间复杂度不能突破 冒泡排序是一种非常简单易懂的排序算法,它在遍历整个数列的过程中,一次次的比较相邻的两个元素的大小,如果顺序错误就将其交换过来。 冒泡排序每次都可以将一个当前最大的数移动到数列的最后,就好像冒泡泡一样,算法的名字也是由此而来。 先来看一张动图演示: 可以看到,冒泡排序必须通过两层循环,并且循环的次数与待排序数组的长度有关,因此其时间复杂度为O(n2)。 冒泡排序每次都要比较完所有的相邻的两个数,但实际上,如果在某一次比较过程没有交换发生的话,即可证明数列已经有序的,因此我们可以在这点下文章,稍微优化一下。 如果待排序的数列本身就是有序的,那么 选择排序的思路比较类似于我们人类的想法,它的工作原理:首先在未排序数列中找到最小或最大的元素,交换到已排序数列的末尾,然后再从剩余未排序数列中继续寻找最小的元素或最大的元素继续做交换,以此类推,直到所有元素都排序完。 还是先来看一个动图演示: 选择排序是最稳定的排序算法之一,任何数列放进去都是O(n2)的时间复杂度,所以适用于数据规模比较小的数列,不过选择排序不占用额外的内存空间。 插入排序的思想类似于我们打扑克的时候抓牌,保证手里的牌有序,当抓到一张新的牌时,按照大小排序将牌插入到适当的位置。 来看动图演示: 插入排序在实现中采用 希尔排序(Shell Sort),这是一个以人命名的排序算法,1959年由Shell发明,这是第一个时间复杂度突破O(2)的排序算法,它是简单插入排序的改进版,与其不同之处在于 动图演示: Shell Sort 的核心在于增量序列的设定,既可以提前设定好增量序列,也可以在排序的过程中动态生成。 快速排序的基本思想比较有意思,它通过一趟排序将待排记录分割成两部分,其中一部分数列均比关键字小,另一部分均比关键字大,然后继续对这个两部分进行快速排序,最终达到整个数列有序。 动图演示: 随机快速排序的一次划分从数列的两头开始交替搜索,知道left和right重合,因此其时间复杂度为O(n)。 快速排序算法的时间复杂度与划分的趟数有关系,理想的情况是每次划分所选择的基准值恰好是当前数列的中位数,经过log2n趟划分,便可得到长度为1的数列,因此快速排序的时间复杂度为O(nlog2n)。 最坏的情况是,每次所选的基准值是当前数列的最大或最小值,这使得每次划分的数列中有一个为空,另一个数列的长度为原数列的长度减去基准值数列的长度,这样,长度为n的数列的快速排序需要经过n趟划分,这时整个随机快速排序的时间复杂度为O(n2)。 从空间性能上看,随机快速排序可以在数列内部进行交换,因此随机快速排序的空间复杂度为O(1)。 归并排序采用分治法(Divide and Conquer),将已有序的子数列合并,得到完全有序我的数列,即先使每个子数列有序,再使子数列间有序,将两个有序数列合并成一个有序数列成为2-路归并。 动图演示: 归并排序的性能不受输入数据的影响,时间复杂度始终是O(nlogn),然而代价是需要额外的内存空间。 其实归并排序的额外空间复杂度可以变成O(1),采用归并排序内部缓存法,但是非常难。 堆排序这个算法就比较有意思了,利用堆这种数据结构,其实就是将数列想象成一个完全二叉树,然后根据最大堆或者最小堆的性质做调整,即可将数列排序。 动图演示: 计数排序是一种统计排序,而不是比较排序了,计数排序需要知道待排序数列的范围,然后统计在范围内每个元素的出现次数,最后按照次数输出即是排序结果。 动图演示: 计数排序的速度非常快,但是它需要知道数列的元素范围,如果数列元素的范围非常大,则需要创建非常大的额外空间。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。 计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时,时间复杂度是O(n+k),空间复杂度也是O(n+k),其排序速度快于任何比较排序算法。 当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。 桶排序在计数排序的方法上利用了函数的映射关系进行改进,不需要知道数列元素的范围,但也需要额外创建一个序列空间,空间中的每个区间存放属于该范围的有序元素,最后遍历整个空间,从小到大输出即是有序数列。 动图演示: 桶排序的最佳时间复杂度为线性时间O(n),平均时间复杂度取决于桶内数据排序的时间复杂度,因为其它部分的时间复杂度都是O(n),所以桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少,但相应消耗的空间就会增大。 基数排序的实现原理比较特别,对于数列中的每个元素,先按照它的个位进行排序,然后按照十位进行排序,以此类推。 动图演示: 基数排序是稳定的,但是性能要比桶排序略差,每一次元素的桶分配都需要O(n)的时间复杂度,而且分配之后得到新的数列又需要O(n)的时间复杂度,假如待排数列可以分为K个关键字,则基数排序的时间复杂度将是O(d*2n),当然d要远小于n,因此基本上是线性级别的。
咳咳,我是一个没有感情的coder,只是单纯的给她讲了算法。
今天呢,就在这一下我给小学妹讲十大经典排序算法的过程。
好吧,那我们就先来看一下十大经典排序算法是哪些:
排序算法大致可以分为两大类,一种是比较类排序,即通过元素之间的比较来决定相对次序;另一种是非比较类排序,运行时间比较快,但是也有诸多限制。
比如说我们写了一个比较NB的Algorithm,但是又不确定right or wrong的时候,就可以通过对数器来验证。import copy import random def bubbleSort(arr: list): length = len(arr) for trip in range(length): for index in range(length - trip - 1): if arr[index] > arr[index + 1]: arr[index], arr[index + 1] = arr[index + 1], arr[index] if __name__ == '__main__': flag = True for i in range(100): list1 = [random.randint(0, 100) for _ in range(random.randint(0, 100))] list2 = copy.deepcopy(list1) list3 = copy.deepcopy(list1) bubbleSort(list2) list3.sort() if list2 != list3: flag = False print(list1) print(list2) print(list3) break print("Nice" if flag else "Fuck")
bubbleSort
是我们自己编写的一个算法,但是我不确定结果是不是正确,这时候,我们可以随机造一堆数据,然后拷贝一份,第一份用Python
内置的排序算法进行排序,第二份用我们自己编写的algorithm进行排序,如果两个算法排序的结果一样的话,就可以大致证明我们的算法正确。一、比较类排序
O(nlogn)
,所以也被称为非线性时间复杂度排序。1.冒泡排序
Bubble Sort
实现思路
Code
def bubbleSort(arr: list): length = len(arr) for trip in range(length): for index in range(length - trip - 1): # 相邻的两个元素,如果顺序错误,就交换两个的位置 if arr[index] > arr[index + 1]: arr[index], arr[index + 1] = arr[index + 1], arr[index]
算法分析
def bubbleSortV1(arr: list): length = len(arr) for trip in range(length): # 交换标志 exChange = False for index in range(length - trip - 1): # 相邻的两个元素,如果顺序错误,就交换两个的位置 if arr[index] > arr[index + 1]: # 如果有交换发生, 标记为 True exChange = True arr[index], arr[index + 1] = arr[index + 1], arr[index] # 如果没有交换发生,说明数列已经有序了 if not exChange: break
bubbleSortV1
走一遍就可以了,即最好时间复杂度为O(n),如果待排序的数列本身是逆序的,那么时间复杂度还是O(n2)。2.选择排序
Select Sort
实现思路
Code
def selectSort(array: list): length = len(array) for trip in range(length - 1): for index in range(trip + 1, length): if array[index] < array[trip]: array[trip], array[index] = array[index], array[trip]
算法分析
3.插入排序
Insert Sort
实现思路
Code
def insertSort(arr: list): for trip in range(1, len(arr)): for index in range(trip - 1, -1, -1): if arr[index] > arr[index + 1]: arr[index], arr[index + 1] = arr[index + 1], arr[index]
算法分析
in-place
排序,从后往前扫描的过程中需要反复将已排序元素向后移动为新元素提供插入空间,因此时间复杂度也为O(n2)。4.希尔排序
Shell Sort
Shell Sort
会优先比较距离较远的元素,所以也叫缩小增量排序。
实现思路
Shell Sort
是把数列按照一定的间隔分组,在每组内使用直接插入排序,随着间隔的减小,整个数列将会变得有序。
Code
def shellSort(array: list): length, gap = len(array), len(array) // 2 while gap > 0: for trip in range(gap, length): for index in range(trip - gap, -1, -gap): if array[index] > array[index + gap]: array[index], array[index + gap] = array[index + gap], array[index] gap //= 2
算法分析
5.快速排序
实现思路
Code
def randomQuickSort(array: list): if len(array) < 2: return _randomQuickSort(array, 0, len(array) - 1) def _randomQuickSort(array: list, left: int, right: int): if left < right: # less, more 分别表示与基准值相等的数列的左右边界 less, more = partition(array, left, right, array[random.randint(left, right)]) _randomQuickSort(array, left, less) _randomQuickSort(array, more, right) def partition(array: list, left: int, right: int, pivot: int): """将比基准值小的数放在左边,相等的放中间,大的放右边""" less, more = left - 1, right + 1 while left < more: if array[left] < pivot: less += 1 array[left], array[less] = array[less], array[left] left += 1 elif array[left] > pivot: more -= 1 array[left], array[more] = array[more], array[left] else: left += 1 return less, more
算法分析
6.归并排序
实现思路
Code
def mergeSort(arr: list, left: int, right: int): if left == right: return # 通过位运算计算可以加快计算效率,下式可以避免溢出 mid = left + ((right - left) >> 1) # 递归排序子数列 mergeSort(arr, left, mid) mergeSort(arr, mid + 1, right) # 将排序好的子数列合并 merge(arr, left, mid, right) def merge(arr: list, left: int, mid: int, right: int): helpList, p1, p2 = [], left, mid + 1 # 合并两个子数列直至一个数列为空 while p1 < mid + 1 and p2 < right + 1: if arr[p1] < arr[p2]: helpList.append(arr[p1]) p1 += 1 else: helpList.append(arr[p2]) p2 += 1 # 将剩下的数列全部添加到合并数列的末尾 while p1 < mid + 1: helpList.append(arr[p1]) p1 += 1 while p2 < right + 1: helpList.append(arr[p2]) p2 += 1 # 将合并数列拷贝到原数列 for index in range(len(helpList)): arr[left + index] = helpList[index]
算法分析
7.堆排序
实现思路
Code
def heapInsert(array: list, index: int): while array[(index - 1) // 2] < array[index] and index > 0: array[(index - 1) // 2], array[index] = array[index], array[(index - 1) // 2] index = (index - 1) // 2 def heapify(arr: list, index: int, length: int): left = 2 * index + 1 while left < length: # 左右子节点中的最大值索引 largest = left + 1 if (left + 1 < length) and (arr[left + 1] > arr[left]) else left # 节点与子节点中的最大值索引 largest = largest if arr[largest] > arr[index] else index if largest == index: # 如果节点即为最大值则无需继续调整 break else: # 否则交换节点与最大值节点 arr[index], arr[largest] = arr[largest], arr[index] index = largest left = 2 * index + 1 def heapSort(array: list): length = len(array) if length < 2: return for index in range(1, length): heapInsert(array, index) for index in range(length - 1, -1, -1): array[0], array[index] = array[index], array[0] heapify(array, 0, index)
二、非比较类排序
1.计数排序
实现思路
Code
def countSort(array: list): count = [0 for _ in range(max(array) + 1)] for value in array: count[value] += 1 array.clear() for index, values in enumerate(count): for _ in range(values): array.append(index)
算法分析
2.桶排序
实现思路
Code
def randomQuickSort(array: list): if len(array) < 2: return _randomQuickSort(array, 0, len(array) - 1) def _randomQuickSort(array: list, left: int, right: int): if left < right: less, more = partition(array, left, right, array[random.randint(left, right)]) _randomQuickSort(array, left, less) _randomQuickSort(array, more, right) def partition(array: list, left: int, right: int, pivot: int): less, more = left - 1, right + 1 while left < more: if array[left] < pivot: less += 1 array[left], array[less] = array[less], array[left] left += 1 elif array[left] > pivot: more -= 1 array[left], array[more] = array[more], array[left] else: left += 1 return less, more def bucketSort(array: list): length = len(array) if length < 2: return bucketNumber = 10 maxNumber, bucket = max(array), [[] for _ in range(bucketNumber)] for item in array: index = min(item // (maxNumber // bucketNumber), bucketNumber - 1) bucket[index].append(item) randomQuickSort(bucket[index]) array.clear() for value in bucket: array.extend(value)
算法分析
3.基数排序
实现思路
Code
def radixSort(array: list): length, maxNumber, base = len(array), max(array), 0 while 10 ** base <= maxNumber: buckets = [[] for _ in range(10)] for value in array: buckets[(value // 10 ** base) % 10].append(value) array.clear() for bucket in buckets: array.extend(bucket) base += 1
算法分析
三、总结
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算