数据结构 - 排序算法对比

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n\log n)\sim O(n^2)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)\sim O(n)$	不稳定

1. 快速排序算法是基于（ ）的一个排序算法。 A 分治法 B 贪心法 C 递归法 D 动态规划法

2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第 8 个记录 45 插入到有序表时，为找到插入位置需比较（ ）次？（采用从后往前比较） A 3 B 4 C 5 D 6

3.以下排序方式中占用 $O(n)$ 辅助存储空间的是 A 简单排序 B 快速排序 C 堆排序 D 归并排序

4.下列排序算法中稳定且时间复杂度为 $O(n^2)$ 的是（ ） A 快速排序 B 冒泡排序 C 直接选择排序 D 归并排序

5.关于排序，下面说法不正确的是 A 快排时间复杂度为 O(N*logN)，空间复杂度为 O(logN) B 归并排序是一种稳定的排序,堆排序和快排均不稳定 C 序列基本有序时，快排退化成冒泡排序，直接插入排序最快 D 归并排序空间复杂度为 O(N), 堆排序空间复杂度的为 O(logN)

6.下列排序法中，最坏情况下时间复杂度最小的是（ ） A 堆排序 B 快速排序 C 希尔排序 D 冒泡排序

7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字 65 为基准而得到的一趟快速排序结果是（） A 34，56，25，65，86，99，72，66 B 25，34，56，65，99，86，72，66 C 34，56，25，65，66，99，86，72 D 34，56，25，65，99，86，72，66

答案：
1.A
2.C
3.D
4.B
5.D
6.A
7.A

排序数组：https://leetcode-cn.com/problems/sort-an-array/ 试试哪个写排序可以跑过这个 OJ 测试