插入排序 计数排序 堆排序 快速排序 归并排序

插入排序

思想

• 1、从左到右，相邻两数两两比较，若下标小的数大于下标大的数则交换，将最大的数放在数组的最后一位（即下标n-1的位置）
• 2、采用相同的方法，再次遍历数组，将第二大的数，放在数组倒数第二的位置（即n-2的位置），以此类推，直到数组有序
• 3、优化：当数组在整个遍历过程中没有发生交换，说明待排序数组已经有序，此时可以直接结束排序过程（用 bool 类型变量作标记）。

代码

#include<iostream>  
#include<vector>  
#include<memory>  
using namespace std;  

// 插入排序函数  
void Bubble_Sort(vector<int>& vec) {  
    for (int i = 1; i < vec.size(); i++) { // 外层循环，从第二个元素开始  
        int j = i - 1; // j代表有序部分的最后一个元素  
        int index = vec[i]; // index是当前要插入的元素  
        for (; j >= 0; j--) { // 寻找插入的位置  
            if (vec[j] > index) // 如果有序部分的元素大于要插入的元素  
                vec[j + 1] = vec[j]; // 将元素右移，腾出位置  
            else {  
                break; // 找到插入位置  
            }  
        }  
        vec[j + 1] = index; // 进行插入  
    }  
}  

int main() {  
    vector<int> vec = { 2, 3, 5, 8, 9, 7, 4, 6, 1 }; // 初始化一个整数向量  
    Bubble_Sort(vec); // 调用插入排序函数  
    for (auto it : vec) { // 遍历输出排序后的向量  
        cout << it << " ";  
    }  
    return 0; // 程序结束  
}

• 代码总结：

• 排序过程:

• 在 Bubble_Sort 函数中，使用插入排序的算法：

  • 外层循环 (for (int i = 1; i < vec.size(); i++)) 遍历数组，从第二个元素开始。
  • 内层循环 (for (; j >= 0; j–)) 用于比较并寻找当前元素的插入位置，将比当前元素大的元素依次向右移动。
  • 最后，将当前元素插入到找到的位置。

时间复杂度

• 最好的时间复杂度是：O（n） 【不用排序】

• 最坏的时间复杂度是：O（n^2）【全部排序】

空间复杂度

• O（1）

稳定性

• 稳定

计数排序

思想

• 原理：将数值作为桶号，遍历整个数组，将相应的桶进行计数
  • 1、.遍历原数组，找到最大值 max，然后申请max+1个空间（桶），初始化为0（下标为0-max), 即vectorbucket(max+1, 0)
  • 2、再次遍历原数组，找到每个数值对应的桶号，并对桶计数++，即bucket[vec[i]]+
  • 3、遍历桶数组，看对应的桶内计数为几就取出几下下标值（桶号），放到原数组中。

代码

#include<iostream>  
using namespace std;  

const int N = 1e4; // 定义常量 N，表示最大可以处理的数组大小  
int num[N]; // 定义一个整型数组 num，用于存储输入的数字  

// 桶排序函数  
void Bucket_Sort(int n) {  
    // 找最大值  
    int max = num[0]; // 假设第一个元素是最大值  
    for (int i = 1; i < n; i++) // 遍历数组，寻找最大值  
        max = max < num[i] ? num[i] : max;  

    // 创建桶，桶大小为 max + 1，初始化为 0  
    int* bucket = new int[max + 1] {0}; // 动态分配内存用于桶  

    // 将元素放入桶中  
    for (int i = 0; i < n; i++)  
        bucket[num[i]]++; // 每个值对应的桶的计数加 1  

    // 将元素取出并还原到原数组  
    int j = 0; // j 用于跟踪当前填充 num 数组的位置  
    for (int i = 0; i <= max; i++) { // 遍历桶  
        while (bucket[i] > 0) { // 只要桶中有元素，就取出  
            num[j++] = i; // 将桶中的值放回原数组  
            bucket[i]--; // 计数减一  
        }  
    }  

    // 释放动态分配的内存  
    delete[] bucket; // 释放桶的内存  
}  

int main() {  
    int n; // 定义整数 n，用于储存输入的数组大小  
    cin >> n; // 输入数组的大小  
    for (int i = 0; i < n; i++) { // 输入数组的元素  
        cin >> num[i];  
    }  
    Bucket_Sort(n); // 调用桶排序函数  
    for (int i = 0; i < n; i++) { // 输出已排序的数组  
        cout << num[i] << " ";  
    }  
    return 0; // 程序结束  
}

• 代码总结：
• 排序过程:
  • 找最大值: 通过遍历 num 数组，找到最大元素 max。
  • 创建桶: 创建一个大小为 max + 1 的动态数组 bucket，用于统计每个元素的出现次数。
  • 放入桶中: 遍历 num 数组，将每个元素的计数存入相应的桶中。
  • 还原到原数组: 通过遍历桶，将计数值逐个填回 num 数组，形成排序结果。

时间复杂度

• 对于均匀分布的数据，桶排序的平均时间复杂度为 O(n)，但在极端情况下可退化为 O（n^2）。
• 极端情况：如果输入数据的分布非常不均匀，所有元素都集中在一个桶中，而其他桶为空。这种情况下，桶排序的性能会退化，因为在取出元素时需要对这个桶内的所有元素进行排序。
  • 例如，假设我们有一个范围从 0 到 100 的数据集，但所有数据都为 50。在这种情况下，只有一个桶会有所有的元素，其他桶都是空的。此时，桶排序的时间复杂度可能会变为 O（n^2）。

空间复杂度

• O（n）

稳定性

• 稳定

堆排序

基础

• 1.完全二叉树：若设二叉树的深度为h，除第h层外，其他各层(1~h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，只能从最深处最右边从右往左缺省。
• 2.最大堆结构：是一个完全二叉树，堆中每个节点的值总是不大于其父亲节点的值（即根节点总是最大的元素）
• 3.创建最大堆：把所有非终端结点检查一遍，看是否满足最大堆的要求，如果不满足，则进行调整（检查当前结点是否满足：根>=左、右，若有不满足，则将当前结点与更大的一个孩子进行交换，若元素互换破坏了下一级的堆，则采用相同的方式继续往下调整，直至符合最大堆要求）

思想

• 将待排序数组形象成一个最大堆结构，从最后一个父节点(n/2-1)开始将其调整为最大堆
  （父节点下标为i，则左孩子下标为 2i+1 右孩子下标为 2i+2)
• 2.将堆顶元素与待排序数组最后一个元素进行交换
• 3.待排序数组数量减少一个，将待排序数组重新调整成最大堆结构，重复2、3操作n-1次，将所以数据排序完成。

代码

#include<iostream>  
#include<vector>  
using namespace std;  

// 调整最大堆的函数，start表示调整的起始位置，end表示调整的结束位置  
void adjustHeap(vector<int>& vec, int start, int end) {  
    int father = start; // 根节点（父节点）  
    int child = 2 * father + 1; // 左子节点  

    // 在调整最大堆的过程中，可能会破坏子树的结构，需要继续向下调整  
    while (child <= end) {  
        // 找到子树中最大的元素  
        if (child + 1 <= end && vec[child + 1] > vec[child]) {  
            child++; // 右子节点比较  
        }  

        // 如果根节点小于子树的最大元素，则需要交换  
        if (vec[child] > vec[father]) {  
            swap(vec[child], vec[father]); // 交换父节点和子节点的值  
            // 发生交换后，继续向下调整子树  
            father = child; // 更新父节点为 child  
            child = 2 * father + 1; // 更新左子节点  
        }  
        // 如果没有发生交换，退出循环  
        else {  
            return;  
        }  
    }  
}  

// 堆排序主函数  
void HeapSort(vector<int>& vec) {  
    // 从最后一个非叶子节点开始调整，确保初始的最大堆结构  
    for (int i = vec.size() / 2 - 1; i >= 0; i--) { // vec.size()/2 - 1 是最后一个有子节点的节点  
        adjustHeap(vec, i, vec.size() - 1); // 调整从该节点开始的最大堆  
    }  

    // 逐步将最大堆的堆顶元素（当前最大值）放到数组的末尾  
    for (int i = vec.size() - 1; i >= 1; i--) {  
        swap(vec[0], vec[i]); // 将堆顶最大元素与当前元素交换  
        // 重新调整堆  
        adjustHeap(vec, 0, i - 1); // 只需调整根节点，因为其他元素已经在正确位置  
    }  
}  

int main() {  
    vector<int> vec = { 53, 17, 78, 9, 45, 65, 87, 32 }; // 初始化待排序数组  
    HeapSort(vec); // 调用堆排序  
    for (auto it : vec) { // 输出排序后的数组  
        cout << it << " ";  
    }  
    return 0; // 程序结束  
}

• 代码总结：

• 1.adjustHeap 函数:

  • 参数: 接受一个整型向量 vec 和两个整数 start、end，分别表示调整的起始和结束位置。
  • 功能: 该函数用于从给定父节点开始，调整以确保最大堆性质（每个父节点都比其子节点大）。
  • 逻辑:
    • 计算当前父节点的左子节点下标。
    • 根据左子节点和右子节点的值来选择子树中较大的节点。
    • 如果父节点小于最大的子节点，则交换它们，并继续向下调整。

• 2.HeapSort 函数:

  • 功能: 主函数，用于执行堆排序操作。
  • 构建最大堆:
    • 从最后一个非叶子节点开始（vec.size() / 2 - 1），依次调用 adjustHeap 函数，确保整个数组满足最大堆特性。
  • 排序:
    在一个循环中，将堆顶（当前最大元素）与当前未排序部分的最后一个元素交换。
    调整堆结构以使堆顶元素再次成为最大值，继续进行直到所有元素排序完成。

时间复杂度

• O(n*logn)

• n个节点的完全二叉树有log2（n+1）层

空间复杂度

• O（1）

稳定性

• 不稳定
  
• 不会保留相等元素的相对位置。

快速排序

引例：三色旗思想

• 问题描述：
  • 有一个只由0,1, 2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。
• 解题思路：
  定义两个下标left 和 right;
  left 的含义：使数组中<=left 的部分都比1小，left 的初始值为-1;
  right的含义：使数组中>=right的部分都比1大，right的初始值为n;
  从 index=0开始遍历；
  根据 index 所指向的值分别进行不同的操作；
  如果 vec[index]=0, swap（vec[index++], vec[++left]）;
  （这里index++的原因是因为index左边不可能有==2的数据了）
  如果 vec[index]= 1, index++;
  如果 vec[index] =2, swap(vec[index], vec[–right])。
  代码实现：以(0, 1, 2, 0, 0, 1, 2, 1, 0)为例：

代码

#include<iostream>  
#include<vector>  
using namespace std;  

// 该函数用来对给定的范围（L到R）里的0、1、2进行快速排序  
void Quick(vector<int>& vec, int L, int R) {  
    int left = L - 1;  // 左指针，初始化为L的前一个位置  
    int right = R + 1; // 右指针，初始化为R的后一个位置  
    int temp = 1;      // 用于划分的中间值，0、1、2中的基准值  
    int index = 0;     // 当前处理的索引  

    // 使用双指针方法，通过index遍历数组  
    while (index < right) {  
        if (vec[index] == temp) { // 当前元素等于基准值  
            index++;   // 如果是1，则直接移动到下一个元素  
        } else if (vec[index] < temp) {  // 当前元素小于基准值  
            swap(vec[index++], vec[++left]); // 交换，再递增left  
        } else {   
            swap(vec[index], vec[--right]); // 当前元素大于基准值，交换，然后递减right  
        }  
    }  
}  

int main() {  
    vector<int> vec = { 0, 1, 2, 0, 0, 1, 2, 1, 0 }; // 初始化待排序数组  
    Quick(vec, 0, vec.size() - 1); // 调用Quick函数进行排序  
    for (auto it : vec) { // 输出排序后的数组  
        cout << it << " ";  
    }  
    return 0; // 程序结束  
}

• 代码总结：

• Quick 函数:

  • 参数: 接受一个向量 vec，一个起始索引 L 和一个结束索引 R，用于指定要排序的范围。
  • 初始化:
    • left 初始化为 L-1，指向左边的分界线。
    • right 初始化为 R+1，指向右边的分界线。
    • temp 设置为 1，用于规定划分的基准（在这里，划分的值为 1）。
    • index 用于遍历数组，初始值为 0。
  • 双指针遍历:
    • 使用 while (index < right) 循环遍历数组元素。
    • 条件判断:
      • 如果 vec[index] == temp，继续移动到下一个元素。
      • 如果 vec[index] < temp（即小于 1，意味着等于 0），则交换当前元素与左边界下一个元素的内容，同时更新 left 和 index。
      • 如果 vec[index] > temp（即大于 1，意味着等于 2），则交换当前元素与右边界前一个元素的内容，同时更新 right。

思想

• 1.三色旗问题：找一个基准值（这里选取待排序数组最左边的那个值），然后将待排序数组分为三部分：
  • 第一部分：数据全部小于基准值
  • 第二部分：数据全部等于基准值
  • 第三部分：数据全部大于基准值
• 2.将第一部分和第三部分分别用三色旗问题处理，知道index>=j即数组有序

代码

#include<iostream>  
#include<vector>  
using namespace std;  

// 分区函数，将数组按基准值 temp 分区  
pair<int, int> quick(vector<int>& vec, int L, int R) {  
    int i = L - 1;           // 指向小于基准值的子数组的最后一位  
    int j = R + 1;           // 指向大于基准值的子数组的起始位置  
    int index = L;           // 当前索引  
    int temp = vec[L];       // 基准值（选择第一个元素作为基准）  

    // 分区操作  
    while (index < j) {  
        if (vec[index] > temp) {  
            swap(vec[index], vec[--j]); // 如果当前元素大于基准值，将其与右边界前一个元素交换，并移动右边界  
        } else if (vec[index] < temp) {  
            swap(vec[index++], vec[++i]); // 如果当前元素小于基准值，将其与左边界后一个元素交换，并移动左边界  
        } else {  
            index++; // 如果等于基准值，直接移动到下一个元素  
        }  
    }  
    return make_pair(i, j); // 返回小于基准值和大于基准值的边界  
}  

// 快速排序函数  
void quickSort(vector<int>& vec, int L, int R) {  
    if (L >= R) return; // 递归结束条件  
    pair<int, int> p = quick(vec, L, R); // 调用分区函数，这里会进行元素的重新排列  
    quickSort(vec, L, p.first); // 递归排序小于基准值的部分  
    quickSort(vec, p.second, R); // 递归排序大于基准值的部分  
}  

int main() {  
    vector<int> vec = { 49,38,65,97,88,23,45,91 }; // 初始化待排序的数组  
    quickSort(vec, 0, vec.size() - 1); // 调用快速排序函数  
    for (auto it : vec) { // 输出排序后的数组  
        cout << it << " ";  
    }  
    return 0; // 程序结束  
}

• 代码总结：

• 1.quick 函数:

  • 参数: 接收向量 vec 和两个整数 L、R，分别表示当前排序的左和右边界。
  • 初始化:
    • i 用于跟踪小于基准值的区间的末尾，初始为 L - 1。
    • j 用于跟踪大于基准值的区间的开头，初始为 R + 1。
    • index 为当前处理的索引，初始为 L。
    • temp 为基准值，选择当前部分的第一个元素。
  • 分区过程:
    • 使用 while (index < j)循环遍历元素。
    • 根据 vec[index] 和 temp的比较来调整元素的位置：
      • 如果元素大于基准值，移动至右侧并递减 j。
      • 如果元素小于基准值，移动至左侧并递增 i。
      • 如果元素等于基准值，直接移动 index。
  • 返回结果: 返回小于和大于基准的分界点 pair<int, int>。

• 2.quickSort 函数:

  • 递归条件: 当 L >= R 时返回以结束递归。
  • 调用分区函数: 通过 quick函数对数组进行分区，并得到新的边界 p。
  • 递归调用:
    • 对小于基准值的分区进行排序。
    • 对大于基准值的分区进行排序。

• 运行过程说明：

• 该程序首先选择数组的第一个元素作为基准（基准值是49），并利用双指针方法重新排列数组，使得小于基准值的元素在左侧，大于基准值的元素在右侧。

• 随后，递归地对形成的小于和大于基准值的两个子数组进行同样的排序过程。

• 最终数组将被排序并输出。

时间复杂度

• 最好的时间复杂度（每次选取中位数作为基准值)😮(n*logn)
• 最坏的时间复杂度（每次选取最大值或者最小值作为基准值，即正序或者逆序时）：O(n^2)

空间复杂度

• O(logn)或者O(n)

稳定性

• 不稳定

归并排序

基础：二分法

• 二分法查找思想：（适用于有序数组）（如果数组没有排序，我们可以先进行排序，在进行二分查找）
  • (1)首先确定整个查找区间的中间位置 mid=(right-left)/2+left;
  • (2)用待查关键字值与中间位置关键字值进行比较
    • 若相等，则查找成功.
    • 若大于，则在后半个区域中继续进行折半查找。
    • 若小于，则在前半个区域中继续进行折半查找。
• 查找成功，返回关键字所在数组下标，没找到返回-1;

代码

#include <iostream>  
#include <vector>  
#include <algorithm> // 用于排序  
using namespace std;  

// 二分查找函数  
int HalfSearch(vector<int>& vec, int target) {  
    int L = 0;  
    int R = vec.size() - 1;   
    
    while (L <= R) {  
        int mid = (R - L) / 2 + L;   
        if (target < vec[mid]) {  
            R = mid - 1;  
        } else if (target > vec[mid]) {  
            L = mid + 1;  
        } else {  
            return mid; // 返回目标值的索引  
        }  
    }  
    return -1; // 没有找到返回 -1  
}  

int main() {  
    vector<int> vec = { 1,5,7,3,9,0,4,2,8,6 }; // 初始化数组  
    sort(vec.begin(), vec.end()); // 对数组进行排序  
    int target = 8;  
    int index = HalfSearch(vec, target); // 查找目标值 8  
    cout << (index != -1 ? "Found at index: " + to_string(index) : "Not found") << endl; // 输出结果  
    return 0;   
}

• 代码总结：

• 1.HalfSearch 函数:

  • 参数: 接收一个整型向量 vec 和一个整型 target，target 是希望查找的元素。
  • 初始化:
    • L 是左索引，初始值为 0（数组的左边界）。
    • R 是右索引，初始值为 vec.size() - 1（数组的右边界）。
  • 循环迭代: 使用 while (L <= R) 来保持搜索的范围有效。
    • mid 计算当前中间元素的索引。
    • 比较和更新:
      • 如果 target 小于 vec[mid]，则向左子阵查找，更新右索引 R。
      • 如果 target 大于 vec[mid]，则向右子阵查找，更新左索引 L。
      • 如果找到了目标值，返回中间元素。

• 未找到返回: 如果搜索完所有元素仍未找到目标值，则返回 -1。

思想

• 将两个有序数组合并成一个有序数组。
  • 1.将数组进行分解，当分解成单个元素为一组的时候才是组内有序的（将目标数组拆成两个数组，设初始数组最小下标为L，最大下标为R，控制项mid=(R-L)/2+L, 得到两个子数组
    • (vec[L]…, vec[mid])和(vec[mid+1]…vec[R]), 对两个子数组再次进行拆分递归，递归结束条件：L==R，即单个数值。）
  • 2.将两两有序的数组进行合并，先申请等于两个数组合并后大小的空间，然后将两个排序好数组逐一比较，向申请的空间中放入较小元素，直至两个有序数组组合成为一个有序数组。重复第二步，直至排序完成。
    • (对拆分通归后的有序数组进行排序结合生成结果数组，将其中的较小值依次放入结果数组，由于操作的数组本身是有序数组，比较后第一个放入的较小值其实是两个数组的最小值，合并之后的结果数组也是有序数组。数组在逐层区域排序之后，其中的数值完全区域有序，最外层的区域排序将得到最终的结果数组)。

代码

#include<iostream>  
#include<vector>  
using namespace std;  

// 合并两个已排序的子数组  
void Merg(vector<int>& vec, int L, int mid, int R) {  
    // 申请一个辅助数组，大小为 R - L + 1  
    vector<int> temp(R - L + 1);  
    int i = L, j = mid + 1, index = 0;  

    // 比较两个有序数组：L到mid 和 mid+1到R  
    while (i <= mid && j <= R) {  
        if (vec[i] <= vec[j]) {  
            temp[index++] = vec[i++];  
        } else {  
            temp[index++] = vec[j++];  
        }  
    }  

    // 处理剩余的元素  
    while (i <= mid) {  
        temp[index++] = vec[i++];  
    }  
    while (j <= R) {  
        temp[index++] = vec[j++];  
    }  

    // 将辅助数组中的元素还原到原数组中  
    index = L;  
    for (int i = 0; i < temp.size(); i++) {  
        vec[index++] = temp[i];  
    }  
}  

// 归并排序函数  
void MergSort(vector<int>& vec, int L, int R) {  
    if (L >= R) return; // 递归出口  
    int mid = (R + L) / 2; // 计算中间索引  
    MergSort(vec, L, mid); // 递归排序左半部分  
    MergSort(vec, mid + 1, R); // 递归排序右半部分  
    Merg(vec, L, mid, R); // 合并两个已排序部分  
}  

int main() {  
    vector<int> vec = { 49, 38, 65, 97, 76, 13, 27 }; // 初始化待排序的数组  
    MergSort(vec, 0, vec.size() - 1); // 调用归并排序函数  
    // 输出排序结果  
    for (auto it : vec) {  
        cout << it << " "; // 输出排序后的数组  
    }  
    return 0; // 程序结束  
}

• 代码总结：

• 1.Merg 函数:

  • 参数: 接收一个整型向量 vec 以及三个整数 L, mid, R，分别代表当前要合并的子数组的左右边界及中间位置。
  • 创建临时数组: 用 temp 存储合并后的结果，大小为 R - L + 1。
  • 合并操作:
    • 使用 while 循环比较两个有序子数组（左：L 到 mid，右：mid + 1 到 R）中的元素，将较小的元素放入 temp 数组中，逐步移动两个子数组的指针。
  • 处理剩余元素:
    • 在一个子数组元素处理完后，可能另一个子数组还有剩余元素，使用两个额外的 while 循环将剩余的元素填充到 temp 中。
  • 将结果拷贝回原数组: 使用 for 循环把 temp 中的元素依次放回 vec 中，相应位置从 L 开始。

• 2.MergSort 函数:

  • 递归条件: 当 L >= R 时结束递归，因为已经不能再分割。
  • 找中间位置: 计算中间索引 mid。
  • 递归排序:
    • 先对左半部分进行排序 MergSort(vec, L, mid)。
    • 然后对右半部分进行排序 MergSort(vec, mid + 1, R)。
  • 合并已排序部分: 调用 Merg 函数合并两个已排序的子数组。

时间复杂度 O(n*logn)

• 归并排序形态上像一颗倒立的二叉树，n个元素的二叉树，高度为log(n+1)层，即n个元素进行归并排序，会递归 log(n+1)次，（即类似于几个元素进行二分），结合二分时间复杂度可得递归过程时间复杂度为O(logn);而每次递归需要排序的元素为n-k个（与快排类似），其时间复杂度为O(n);
• 综上所述，归并排序所需的时间复杂度为 O(n*logn)

空间复杂度 O（n）

• 每次递归完合并两个有序数组时都会创建辅助数组，但是函数运行完之后辅助数组会自动释放，所以辅助数组空间并不叠加，仅会保留最后一个辅助数组空间，即上图的第三次归并时所创建的辅助数组，其空间复杂度为O(n)；n个无素进行排序会递归log(n+1)次，所以递归所需要的空间复杂度为O(logn)。

• 综上所述，归并排序所需空间复杂度为O(n)+O(logn)=O(n)。

稳定性

• 稳定