排序算法对比

zedo2022/8/13大约 2 分钟约 645 字

排序算法对比

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	$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 lo g n) \sim O (n^{2})$	$O (n^{1.3})$	$O (n^{2})$	$O (1)$	不稳定
堆排序	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	不稳定
归并排序	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	稳定
快速排序	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	$O (lo g 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 lo g N)$ ，空间复杂度为 $O (lo g N)$
B、归并排序是一种稳定的排序，堆排序和快排均不稳定
C、序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D、归并排序空间复杂度为 $O (N)$ ，堆排序空间复杂度的为 $O (lo g N)$

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 测试