排序

🚧施工中🚧

排序之间的比较

排序算法	时间复杂度			空间复杂度	稳定性	适合链式存储？
	最好情况	平均情况	最坏情况
直接插入排序					✅	折半插入：❌；直接插入：✅
冒泡排序						✅
简单选择排序					❌	✅
希尔排序						❌
快速排序						❌
堆排序						❌
二路归并排序					✅	✅
基数排序						✅

习题

有序的排序

(没好好看题全做错了)
对 n 个基本有序的整数进行排序：

1. 若采用插入排序算法，则时间和空间复杂度分别为（ ）；
2. 若采用快速排序算法，则时间和空间复杂度分别为（ ）。

正确答案

1. 插入排序：时间复杂度 ，空间复杂度 .
2. 快速排序：时间复杂度 ，空间复杂度 .

解析

1. 插入排序：

   • 时间复杂度：当数据基本有序时，插入排序只需进行少量的比较和移动操作，因此时间复杂度为
   • 空间复杂度：插入排序只需常数级的额外空间（如临时变量等），因此空间复杂度为 .

2. 快速排序：

   • 时间复杂度：快速排序在最坏情况下（如数据已完全有序），每次划分只能将数组分成一个元素和 个元素的两部分，此时递归深度为 ，时间复杂度为 .
   • 空间复杂度：快速排序主要是在原数组上进行操作，无需额外的存储空间，因此空间复杂度为 .