Day 9 - Sorting Pre-Knowledge

Day9 - 排序前置知识

1. 排序的介绍

排序是按顺序重新排列给定序列中元素的行为，可以按字典顺序排列，可以按数字的升序或降序排列，也可以按照你指定的规则去排列。

一些基本的时间复杂度为的排序算法，在面试编码的时候尽量不要使用，除非面试官要求你实现一个冒泡排序或选择排序。大部分时候是不太可能要求你从头实现某一个排序算法。一般都是使用语言自带的排序算法，但你需要熟知自己擅长语言中排序算法的原理。排序经常跟二分查找一起出现在面试题中。

一个已排序的元素数组，利用其已排序的属性，使用二分查找可以在O(logn)时间内完成一个指定元素的搜索。二分查找将目标值与数组的中间元素进行比较，来决定是在数组的左半边还是右半边查找目标值，然后在符合条件的半边继续进行二分查找，直到找到目标或符合条件的半边为空。

1.1. Cpp快速排序函数：sort()

std::sort

• 功能： 使用快速排序（IntroSort）对指定范围内的元素排序。

• 时间复杂度： 平均 ，最坏情况 （但引入了堆排序保证不会太差）。

• 定义：

void sort(RandomAccessIterator first, RandomAccessIterator last);

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• 说明：

• • first 和 last 定义待排序范围。

  • 可选参数 comp 是自定义比较函数，用于指定排序规则。

1.2. Python排序函数：sorted()

sorted() 函数

• 适用于任何可迭代对象（如列表、元组等）。

• 返回一个新列表，原对象保持不变。

• 支持自定义排序规则（通过 key 和 reverse 参数）。

1.3. Python排序方法：list.sort()

• 仅适用于列表。

• 就地排序（改变原始列表），不返回新列表。

2. 排序复杂度

算法名称	时间复杂度	空间复杂度
冒泡排序	O(n^2)	O(1)
插入排序	O(n^2)	O(1)
选择排序	O(n^2)	O(1)
快速排序	O(nlogn)	O(logn)
归并排序	O(nlogn)	O(n)
堆排序	O(nlogn)	O(1)
计数排序	O(n + k)	O(k)
基数排序	O(nk)	O(n + k)

上面的复杂度都是平均的复杂度，有些算法的时间复杂度跟给定序列是否基本有序相关，比如快排，越是有序的序列排起序来就越慢。

基于有序序列的二分查找的时间复杂度为O(logn)。

3. 边界的条件

• 给定的序列为空

• 给定的序列只有一个元素

• 给定的序列只有两个元素

• 给定的序列包含重复元素

4. 一些小技巧

1. 当给定的序列是有序的(升序或降序)时，首先应该想到的就是使用二分查找。

2. 计数排序不是基于比较的排序，如果事先知道给定序列值的范围，使用计数排序是一种不错的选择。