题目
最坏情况下 insert sort, quick sort ,merge sort 的复杂度分别是多少？
A.O(n*n),O(nlogn),O(n*n)
B.O(n*n),O(n*n),O(nlogn)
C.O(n*n),O(nlogn),O(nlogn)
D.O(nlogn),O(nlogn),O(nlogn)
解答
正确答案是 B
1：简单选择 最好时间 O(n^2) 平均时间O(n^2) 最坏时间 O(n^2)
2：直接插入 最好时间 O(n) 平均时间O(n^2) 最坏时间 O(n^2)
3：冒泡排序 最好时间 O(n) 平均时间O(n^2) 最坏时间 O(n^2)
4：希尔排序 最好时间 O(n) 平均时间O(logn) 最坏时间 O(n^s) 1<s<2
5：快速排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(n^2)
6：堆排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(nlogn)
7：归并排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(nlogn)
快排在有序时会变成最慢的
快排最坏会退化为冒泡，冒泡最好，最差，平均都是n^2。
插入排序在逆序的时候最差为O(n^2);
快速排序在有序的时候最差为O(n^2);
归并排序最好最坏的时候都一样为O(nlogn)