问题的计算复杂度：排序问题
排序算法的效率插入排序冒泡排序：快速排序：二分归并排序：
什么是最好的排序算法？
排序算法的效率
算法最坏情况下平均情况下
插入排序
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
2
)
O(n^2)
O(n2)冒泡排序
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
2
)
O(n^2)
O(n2)快速排序
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)堆排序
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)二分归并排序
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
算法特点： ** 以元素的比较作基本运算**
插入排序
原理：从首元素开始，将前一个元素与后一个元素作比较，如果后元素小于前元素，则前一个元素向后移动，再判断后元素与前前元素的大小，作元素的移动；如果此元素小于后元素，则将后元素插入至此元素的后面。
冒泡排序：
基本操作：巡回 将数组元素从前往后，依次两两比较，如果后者大于前者，则将两者进行交换；直至比较至最后一个元素；一次巡回的结果： 最大数据排序至最后位置；巡回的最大次数： 数组的长度
n
n
n巡回结束的标志： 当巡回中没有元素发生交换时，表示所有元素已排序完毕。
快速排序：
基本操作：递归 选定数组的第一个元素，从数组的前后使用2个指针，一个往前、一个往后对数组进行遍历，往前的找到比首元素大的元素时停止，往后的找到比首元素小的停止，将此2个元素进行交换。一次遍历停止的标志： 两个指针相遇。划分： 将首元素与第1次遍历停止后的交换的那个较小元素进行交换，然后以首元素此时被交换到数组中新的位置，将数组的排序分为前后两个子数组的排序问题；递归： 对这两个子问题，采用上述方法，递归地进行排序；
二分归并排序：
基本操作：递归 将待排序的数组从中间一分为二，通过不断递归将两个子数组排好序；归并： 将两个排好序的子数组从首元素往后依次比较大小，较小者取出来放入排好序的新数组中，直到某个子数组为空，则将剩下待比较的数组直接接在新数组的后面。
什么是最好的排序算法？
时间复杂度排序算法的效率排序问题的难度
