pascal 中 log(n)
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/22 22:01:27
pascal 中 log(n)
pascal 中 log(n)
pascal 中 log(n)
就是排序的平均时间（最快+最慢/2）.
在这个表格中,n是要被排序的纪录数量以及k是不同键值的数量.
稳定的
冒泡排序（bubble sort） — O(n2)
鸡尾酒排序 (Cocktail sort,双向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体
归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体
原地归并排序 — O(n2)
二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体
基数排序 （radix sort）— O(n•k); 需要 O(n) 额外记忆体
Gnome sort — O(n2) \x05
Library sort — O(n log n) with high probability,需要 (1+ε)n 额外记忆体
不稳定
选择排序 （selection sort）— O(n2)
希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望时间,O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情况时间,需要 额外的 O(n + k) 空间,也需要找到最长的递增子序列（longest increasing subsequence）
各算法的时间复杂度
平均时间复杂度
插入排序 O(n2)
冒泡排序 O(n2)
选择排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
基数排序 O(n)
希尔排序 O(n1.25)
其实当你知道某一个排序的算法是就可以用计算器的log算出来了