排序算法
排序算法是我们会遇到的最基本的算法之一，算法分为了内部排序和外部排序。所谓内部排序就是数据记录在内存并且进行排序，外部排序就是因为排序的数据量太大了，不能全都在内存中完成，需要访问磁盘等工具进行辅助。
内部排序
常见的内部排序算法有：冒泡排序、选择排序、插入排序、快速排序、堆排序、希尔排序
外部排序
外部排序有：归并排序、桶排序、基数排序
冒泡排序
原理
简单来说，冒泡排序就是挨个比较相邻的两个元素，如果前面的元素大于后面的元素则交换他们的位置，每一轮比较都会把当前最大的数移动到末尾，完成一轮之后重复以上步骤，并且每次排除最后一个元素缩小范围。
实现
/**
* @name BubbleSort()
* @param std::vector<int>& nums
* 两个数挨个对比，然后将较小的数放到前面,大的放在后面，即交换位置
* 时间复杂度O(n^2) 空间复杂度O(1)
* */
void BubbleSort(std::vector<int> nums)
{
for(int i = 0; i < nums.size() - 1; i++)
{
for(int j = 0; j < nums.size() - 1 - i; j++)
{
if(nums[j] > nums[j + 1]) // 前一个数比后一个数大
{
// 这里也可以直接 swap()，一样的思想
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
std::cout << "after BubbleSort " << std::endl;
show(nums);
}
其中show()只是辅助函数，打印出数组元素
复杂度分析
每一次比较都会遍历整个数组，并且会比较直到最后一个元素，所以时间复杂度应该是O(n^2)，没有使用外部空间，空间复杂度为O(1)
优缺点
优点：实现非常简单，大家都可以很容易就理解了，并且是原地排序，不需要额外开辟空间
缺点：效率不高，并且如果已经接近有序的原始数组，会进行多次的无效比较
当输入数据是从大到小依次排列的时候，效率是最慢的，要把所有的元素位置翻转。
选择排序
原理
选择排序就是每次选择一个数（我们可以默认选择第一个数）作为最大或者最小（实际可以看需要），后面的数依次跟选择的这个数进行比较，满足对应条件也是进行交换操作，循环直到全部排序完成。
实现
/**
* @name ChoiceSort()
* @param std::vector<int>& nums
* 选择排序
* 将第一个当作最大或者最小，以此用后面的元素与第一个进行比较，如果发现更小或者更大的就交换两数
* 时间复杂度O(n^2) 空间复杂度O(1)
* */
void ChoiceSort(std::vector<int> nums)
{
for(int i = 0; i < nums.size(); i++)
{
int minVal = nums[i];
int index = i;
for(int j = i + 1; j < nums.size(); j++)
{
if(nums[j] < minVal)
{
minVal = nums[j];
index = j;
}
}
// 交换位置
// swap(nums[index], nums[i]);
int temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
}
std::cout << "after ChoiceSort " << std::endl;
show(nums);
}
复杂度分析
选择排序其实基本上也会每次遍历整个数组，所以时间复杂度也是O(n^2)，空间复杂度是O(1)。
优缺点
选择排序的实现方式比较简单，并且是原地排序，不需要额外空间，但是时间复杂度太高，不适合大规模的数据，同时也是不稳定的排序算法。
适合于数据较少，性能要求也不高的场景。
插入排序
插入排序建立在部分有序的序列基础之上（一个元素也是有序的），然后后面那些未排序的元素，会在已排序的序列上从后往前依次扫描，找到了相对应的位置就插入。
主要步骤：
- 首先将序列划分为已排序和未排序状态，可以取第一个元素为已排序序列，其余的为未排序序列；
- 从未排序的序列取出第一个元素
- 在已排序序列上，从后往前依次比较，找到第一个比这个未排序序列中取出的这个数小的元素，然后插入到其后面
- 重复直到全部完成排序
实现
/**
* @name InsertSort()
* @param std::vector<int>& nums
* 插入排序
* 假定前面有一个有序序列，后面的数依次插入到第一个比该数小的数之后
* 时间复杂度O(n^2) 空间复杂度O(1)
* */
void Insert(std::vector<int>& nums) {
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < nums[i-1]) {
int val = nums[i];
int j = i - 1;
// 在已经排序的序列中搜索
for (; j >= 0 && nums[j] >= val; j--) {
nums[j + 1] = nums[j]; // 将找到正确的插入位置前遇到的已经排序的数据往后挪
}
nums[j + 1] = val;
}
}
}
复杂度分析
插入排序适合数据已经趋于有序的情况，在这种情况排序效率可以趋于线性排序。时间复杂度是O(n^2)，空间复杂度为O(1)
插入排序算法是稳定的不会改变相同数据的相对位置，可以作为一些复杂算法的辅助算法，比如std::sort()底层就使用了插入排序作为辅助排序方式。
希尔排序
原理
如果数据趋于有序，插入排序是所有排序算法中，效率最高的排序算法，但是插入排序每次都是移动一个数据，所以在插入排序的基础上改进得到了希尔排序。
希尔排序将整个序列利用分治的思想，划分为多个子序列，分别进行插入排序，然后对整体的序列进行直接插入排序。
步骤
- 选择一个增量将原始列表分为若干个子列表，初始增量一般为(n/2)
- 分组进行插入排序
- 逐步缩小增量，重复分组和排序过程，直到增量为1
- 对整个序列进行插入排序
实现
/**
* @name ShellSort()
* @param std::vector<int>& nums
* 希尔排序
* 如果数据趋于有序，插入排序是所有排序算法中，效率最高的排序算法---> 插入排序的思想
* 那么希尔排序就是插入排序的基础上做优化：即将数据尽可能在全局趋于有序
* 方法： 分组进行插入排序
* 二分缩小范围 初始gap = size / 2， 之后每一次分组 gap /= 2 直到 gap = 0退出
* 时间复杂度O(n^2) 空间复杂度O(1)
* */
void ShellSort(std::vector<int>& nums) {
// 在插入排序基础上划分gap
foe (int gap = nums.size(); gap > 0; gap / 2) {
for (int i = gap; i < nums.size(); i += gap) {
if (nums[i] < nums[i-gap]) {
int val = nums[i];
int j = i - gap;
foe (; j >= 0 && nums[j] >= val; j -= gap) {
nums[j + gap] = nums[j];
}
nums[j + gap] = val;
}
}
}
}
复杂度分析
希尔排序的时间复杂度取决于选取的增量序列，如果是在最坏的情况下，时间复杂度为O(n^2)，最好的情况下是O(nlogn)，平均下来就在这两者之间。
希尔排序没有开辟额外的空间，所以空间复杂度是O(1)；
优缺点
相对于直接插入排序，效率更高，适用更大规模的数据集，也不需要开辟额外的内存空间，但是依赖于增量序列的选择，这也是一种不稳定的排序算法。
快速排序
原理
快速排序是一种基于分治思想的排序算法，核心原理是通过选择一个基准元素，然后将列表分为大于基准和小于基准的序列，再递归对这两部分排序。
步骤
- 从列表中选择一个元素作为基准，一般可以选择第一个元素、中间元素、随机元素或者最后一个元素。
- 将列表重新排列，使得所有小于基准的元素在基准的左侧，所有大于基准元素的元素都在基准右侧，在每轮排列之后基准元素就是空出来的位置
- 对基准元素左侧和右侧的子序列进行递归快速排序
- 最后将所有的子序列进行合并
实现
/**
* @name FastSort()
* @param std::vector<int>& nums
* 快速排序 二分+递归的思想
* 1、找到一个基准点L = 0， R = nums.size() - 1 val = nums[L]
* 2、从R开始向前找到第一个小于val的值，放到L处， L++
* 3、从L开始向后找到第一个大于val的值，放到R处，R--
* 4、循环重复 2 、3
* */
int pos(std::vector<int>& nums, int left, int right) {
// 选择基准点
int val = nums[left];
while(left < right) {
// 从右往左找到第一比基准数小的，放到left位置
while (left < right && nums[right] > val) {
right--;
}
// 此时已经找到了第一个比基准数小的元素
if (left < right) {
nums[left++] = nums[right];
}
// 现在开始步骤三
while (left < right && nums[left] < val) {
left++;
}
if (left < right) {
nums[right--] = nums[left];
}
}
nums[left] = val;
return left;
}
// 快速排序辅助函数
void subFastSort(std::vector<int>& nums, int left, int right) {
if (left >= right) {
return ;
}
int postion = pos(nums, left, right);
subFastSort(nums, left, pos - 1);
subFastSort(nums, pos + 1, right);
}
void FastSort(std::vector<int>& nums) {
subFastSort(nums, 0, nums.size() - 1);
}
复杂度分析
其实采用的二分思想，递归的层数就是O(logn)，需要O(n)的时间来合并排序后的子列表，所以时间复杂度应该是O(nlogn)，但是在最坏的情况下会退化到O(n^2).
以上都是在同一个数组中实现的，所以原地排序，空间复杂度为O（1）
优缺点
快速排序的核心是选择基准元素，将序列划分为 “小于基准”“等于基准”“大于基准” 三部分，但划分过程中可能破坏相等元素的相对顺序，所以是一种不稳定的算法。
优点是很快，适合大规模数据
归并排序
原理
归并排序采用分治思想将一个问题划分为多个问题，然后分别进行解决最后汇总起来。
所以归并排序首先会将序列进行分组，然后对分组之后的子序列进行递归排序，最后再进行合并。
步骤
- 首先利用二分法进行分组递归，递归终止条件是遇到叶子节点：即
left >= right - 左右两边的子序列再递归
- 在归的过程中进行合并排序，
实现
/**
* @name MergeSort(std::vector<int>& nums) 归并排序主接口
* SubMergeSort(std::vector<int>& nums, int left, int right, std::vector<int>& p) 递归过程接口
* Merge(std::vector<int>& nums, int left,int mid, int right, std::vector<int>& p) 归排序过程接口
* @param std::vector<int>& nums
* 归并排序
* 1、在递归的过程中进行数据合并与排序，首先利用二分法进行分组递归，递归终止条件是遇到叶子节点：即 left >= right
* 2、左右分别进行递归
* 3、在归的过程中进行合并排序，即开辟一块新内存，对左右子树的数据进行比较，从小到大依次放入新开辟的空间，然后将此空间中排序后的元素拷贝回原始数组中[left, right]区间内
* */
void Merge(std::vector<int>& nums, int left,int mid, int right, std::vector<int>& p) {
// 此时左右两边子树分别是已经有序了，现在需要进行合并，那么就是比较这俩子树的大小，然后依次添加到p数组中
int index = 0, i = left, j = mid + 1;
while (i <= mid && j <= right) {
// 分别开始遍历添加到p数组中
if (nums[i] < nums[j]) {
p[index++] = nums[i];
} else {
p[index++] = nums[j];
}
}
// 若左边子树还有剩余，则将其直接添加到p数组末尾
while (i <= mid) {
p[index++] = nums[i];
}
while (j <= right) {
p[index++] = nums[j];
}
// 将p数组中的元素拷贝回nums数组
for (j = 0, i = left; i <= right; i++, j++) {
nums[i] = p[j];
}
}
void SubMergeSort(std::vector<int>& nums, int left, int right, std::vector<int>& p) {
// 递归终止条件
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
// 左右子树递归
SubMergeSort(nums, left, mid, p);
SubMergeSort(nums, mid + 1, right, p);
Merge(nums, left, mid, right, p);
}
void MergeSort(std::vector<int>& nums) {
std::vector<int>& p(nums.size());
SubMergeSort(nums, 0, nums.size() - 1, p);
}
复杂度分析
整体的时间复杂度是O(ologn)，情况与快排类似。
因为开辟了额外的数组p，所以空间复杂度为O(n)
优缺点
适合大规模排序，同时归并排序也可以适用于外部排序，当海量数据时，利用分治思想，分别处理，然后合并。
是稳定的排序算法
堆排序
堆排序是一种基于堆这种数据结构的排序算法，利用了堆的特性实现排序。
这里先介绍一下堆
堆
堆其实是一颗特殊的完全二叉树，它的主要性质是：子树的键值总是小于（大于）父节点的键值，所以就有两种堆，分别是：
- 大顶堆：每个父节点的值 ≥ 子节点的值（根节点是最大值）
- 小顶堆：每个父节点的值 ≤ 子节点的值（根节点是最小值）。
堆通常都是使用数组实现的，对于下标为i的节点，它的左右节点以及父节点的坐标分别是：
- 父节点：
(i-1) // 2 - 左节点：
2*i+1 - 右节点：
2*i+2
堆的实现
堆就是一个优先级队列
class PriorityQueue {
public:
using Comp = std::function<bool(int, int)>;
PriorityQueue(int cap = 20,
Comp comp = std::greater<int>() /*默认使用从大到小，也可以自己传lambda表达式表示排列顺序*/);
// 重载，用户只需要传入比较规则
PriorityQueue(Comp comp);
// 析构函数
~PriorityQueue();
public:
// 以下是一些公共接口，比如 push pop top empty size等
void push(int val);
void pop();
bool empty() const;
int size() const;
int top();
private:
// 上浮调整
void ShiftUp(int i, int val);
// 下沉调整
void ShiftDown(int i, int val);
private:
int *que_; // 可动态扩容的数组
int size_; // 数组中的实际元素个数
int cap_; // 数组的最大容量
Comp comp_; // 比较器
};
首先是构造与析构，都是开辟基础的空间，然后初始化一些变量
PriorityQueue::PriorityQueue(int cap, Comp comp) : cap_(cap) , size_(0), comp_(comp) {
que_ = new int[cap_];
}
PriorityQueue::PriorityQueue(Comp comp) : cap_(20) , size_(0), comp_(comp) {
que_ = new int[cap_];
}
// 释放堆上开辟的数组空间
PriorityQueue::~PriorityQueue() {
delete[]que_;
que_ = nullptr;
}
压入队列与弹出
入队前首要判断队列是否已满，需要扩容，出队前判断队列是否为空，避免在空地址上进行操作，造成未定义行为
void PriorityQueue::push(int val) {
// 判断数组是否已满，是否需要扩容
if (size_ == cap_) {
int *p = new int[2 * cap_];
// void * __cdecl memcpy(void * __restrict__ _Dst,const void * __restrict__ _Src,size_t _Size)
memcpy(p, que_, cap_ * sizeof(int)); // 拷贝原来的数据
delete que_;
que_ = p;
cap_ = 2 * cap_;
}
// 如果只有一个元素，不需要上浮调整
if (size_ == 0) {
que_[size_] = val;
} else {
// 进行上浮操作
ShiftUp(size_, val);
}
size_++;
}
void PriorityQueue::pop() {
if (size_ == 0) {
// 数组为空，弹出元素，抛出异常
throw "que_ size_ = 0!";
}
size_--;
// 如果还有元素，需要调整
if (size_ > 0) {
// 删除堆顶元素，还有剩余的元素，要进行堆的下沉调整
ShiftDown(0, que_[size_]);
}
}
上浮：当向堆中插入新元素时，将元素放在堆的末尾，然后通过 “上浮” 调整，使其移动到符合堆特性的位置，保证堆的结构不被破坏。当新元素比父节点大时上浮
// 上浮调整：将下标i处的元素（值为val）向上调整到正确位置
void PriorityQueue::ShiftUp(int i, int val) {
// 前提是不能超过根节点（i=0时为根，无需上浮）
while (i > 0) {
int father = (i - 1) / 2; // 计算父节点下标（完全二叉树的性质）
// 比较当前元素与父节点的大小（通过比较器comp_）
if (comp_(val, que_[father])) {
// 若满足比较条件（例如：val > 父节点值，对于大顶堆）
// 则父节点下移（腾出位置给当前元素）
que_[i] = que_[father];
i = father; // 更新当前元素位置为父节点位置，继续向上比较
} else {
// 若不满足条件，说明当前位置已符合堆特性，停止上浮
break;
}
}
// 循环结束后，i即为当前元素的正确位置，放入val
que_[i] = val;
}
下沉调整:
当堆顶元素被移除（或替换）后，将末尾元素移到堆顶，然后通过 “下沉” 调整，使其移动到符合堆特性的位置，保证堆的结构不被破坏。
// 下沉调整：将下标i处的元素（值为val）向下调整到正确位置
void PriorityPriorityQueue::ShiftDown(int i, int val) {
// 循环条件：i必须是非叶子节点（叶子节点无需下沉）
// size_/2 是最后一个非叶子节点的下标（完全二叉树的性质）<---> i <= (size_ - 1 - 1)/2
while (i < size_ / 2) {
// 左孩子下标（默认与左孩子比较）
int child = 2 * i + 1;
// 若右孩子存在，且右孩子更符合堆特性（通过comp_判断），则选择右孩子
if (child + 1 < size_ && comp_(que_[child + 1], que_[child])) {
child = child + 1; // 切换到右孩子
}
// 比较当前元素与选中的孩子节点
if (comp_(que_[child], val)) {
// 若孩子节点更符合堆特性（例如：孩子 > 当前值，对于大顶堆）
// 则孩子节点上移
que_[i] = que_[child];
i = child; // 更新当前元素位置更新为孩子节点位置，继续向下比较
} else {
// 若当前位置已符合堆特性，停止下沉
break;
}
}
// 循环结束后，i即为当前元素的正确位置，放入val
que_[i] = val;
}
以上两个辅助函数的关键在于：优先选择更符合堆性质的孩子节点，确保堆的性质不被破坏，通过比较器 comp_ 灵活支持大顶堆和小顶堆，通过数组下标计算父子节点位置，维护堆的特性。
这两个操作的时间复杂度均为 O(log n)（堆的高度为 log n），因此基于堆的优先队列的插入和删除操作也都是 O (log n) 级别的操作
堆排序
核心思想
-
构建堆：将无序数组转换为大顶堆（或小顶堆）。
-
交换与调整
- 将堆顶元素（最大值）与末尾元素交换，此时末尾为有序区。
- 缩小堆的范围（排除已排序的末尾元素），重新调整剩余元素为大顶堆。
-
重复步骤 2：直到整个数组有序。
完整实现
/**
* @name HeapSort(std::vector<int>& nums) 堆排序主接口
* SiftDown(std::vector<int>& nums, int i, int size_) 下沉过程接口
*
* @param std::vector<int>& nums
* 堆排序
* 1、从第一个非叶子结点开始，将二叉堆调整为一个最大堆
* 2、将堆顶元素和最后一个元素交换，依次下沉调整，每次比较的时候除去最后的元素
*
*
* */
// 下沉调整
void SiftDown(std::vector<int>& nums, int i, int size)
{
int val = nums[i];
while(i < size / 2 /*i <= (size_ - 1 - 1)/2*/)
{
// 找到其左右孩子节点的下标
int child = 2 * i + 1; // 默认左孩子，后续比较左右孩子的大小，更新较大的孩子的下标
if( child + 1 < size && nums[child + 1] > nums[child])
{
// 此时说明右边孩子比左边孩子大
child = child + 1;
}
// 接下来比较孩子节点和调整节点的值
if(nums[child] > val)
{
nums[i] = nums[child];
i = child;
}else{
break;
}
}
nums[i] = val;
}
void HeapSort(std::vector<int>& nums)
{
int n = nums.size() - 1;
// 对第一个非叶子节点开始调整为最大堆
for(int i = (n - 1)/2; i >= 0; i--)
{
SiftDown(nums, i, nums.size());
}
// 将堆顶元素与末尾元素进行交换，从堆顶开始进行下沉操作
for(int i = n; i > 0; i--)
{
swap(nums[0], nums[i]);
// 进行下沉操作
SiftDown(nums, 0, i);
}
}
时间复杂度分析
构建堆的过程为O(n)，但是调整堆的位置的时间复杂度为O(logn)，一共需要调整n-1次，所以一共是O(ologn)，所以总的时间复杂度为O(nlogn)；
堆排序属于原地排序，时间复杂度为O(1);但是不是一个稳定的排序算法。
适用于数据量特别大的场景，外部排序