常见排序算法¶

![[Pasted image 20240408115903.png]]

![[Pasted image 20240408150551.png]]

1. 选择排序¶

最快 O(n),本身就是有序数组
最慢 O(n^2)，本身是逆序数组
空间复杂度：O(1)
稳定性：不稳定
- 在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
原地排序，需要关键字 ![[Pasted image 20240408120317.png]]

2. 选择排序之--堆排序--partial_sort()--¶

应用：TOPK

特点¶

每次插入都是将新数据放在数组最后（从下标 1 开始遍历）。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中，在这个过程中要进行比较。

是一个完全二叉树
堆序性：根节点和子节点相对有序（大根、小根）
分为建堆+调整两个步骤 主要操作：
下滤： O(logN): n 个元素每个元素调整最多下降 h-1 次，
上滤： O(logN):主要用于插入到新元素队尾中，逐级向上调整 建堆： 自顶向下建堆法(插入法)--对应上滤：
最快: O(n)--完全有序的建堆，每次插入顺序都是对的
最慢: O(N logN),：一个个依次插入，不停向上检查（上滤） -自下而上建堆法（筛选法*）
先全部放入数组，从倒数第二层（n/2）往上遍历节点开始下滤
最快：O(n)：插入所有有序数据 n，遍历 N/2
最慢：O(N)： N/2 个数都要进行下滤操作。 调整：
堆建好后，形成优先队列。
每次弹出第一个元素(或与最后一个元素交换)，使堆最后一个元素从头节点下滤重建堆，O（NlogN）其他：
空间复杂度：O(n)，非原地排序

不稳定排序：

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

void max_heapify(int arr[], int start, int end) {
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    // 初始化，i從最後一個父節點開始調整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

堆排序¶

堆的定义：
- 完全二叉树
- 分类：
  - 大根堆：所有子节点必须小于根节点
  - 小根堆：所有子节点必须大于根节点
堆的储存：
- 节点下标为 i
- 父节点(i-1)/2
- 左子节点下标为 2i+1;
- 右子节点下标为 2i+2；操作：
- 下滤：顶部插入，这破坏了堆的根序性，需要不断地跟子节点交换直到恢复堆序性，复杂度 O（logN）
- 上滤：底部元素破坏堆地根序性，需要与根节点交换
如何建堆？
- 自顶向下建堆法，复杂度（ONlogN）：
  - 插入堆
  - 上滤
- 自下而上建堆法，O(N)
  - 全部插入
  - 从倒数第二排开始
  - 对每个父结点进行下滤操作。
应用：
- 优先队列--弹出最小元素
- 堆排序 partial_sort()：
  - 平均性能和最差都是 O(nlogn),但实际情况比 sort 慢。可以对容器的一部分数据排序，不稳定
  - 采用三个随机迭代器RandomAccessIterator：
    - first
    - sortEnd 堆排序结束，
    - last 元素范围结束；每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中，在这个过程中要进行比较。
  - 在全部数据中排出前 5：partial_sort(v2.begin(),v2.begin()+5,v2.end());
  - C++语言代码，自下而上建堆法
    - 时间复杂度: O(NlogN)==建堆 O(N) + heapifyO(logN) + 堆排序堆 N 个数进行 heapify：

3.插入排序¶

最快：O(N)，有序
最慢：O(N2),逆序
空间复杂度: O(1)，原地,稳定 ![[Pasted image 20240408145123.png]]

4. 插入排序---希尔排序¶

![[Pasted image 20240408145324.png]] - 核心是分组思想，分组后插入排序 - 时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3—N2） - 稳定性：不稳定

5.交换排序---冒泡排序¶

我觉得就是把插入排序反过来 时间复杂度和插入排序一个样

6.交换排序---快速排序**Quick_Sort¶

平均 Onlogn，最差 O(n^2)
不稳定
空间复杂度：logN，因为递归
越乱，效率越高，有序，退化为冒泡三个版本：
hoare 版本
挖坑法
前后指针版本*

真是看一次忘一次啊

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        quicksort(arr, 0, arr.size()-1);
        return arr;
    }

    int partition(vector<int>&arr,int l,int r)
    {
        int x = arr[l];
        while( l < r)
        {
            while(l<r&&arr[r]>=x){r--;}
            arr[l]=arr[r];
            while(l<r&&arr[l]<=x){l++;}
            arr[r]=arr[l];
        }
        arr[l] = x;
        return l;
    }

    void quicksort(vector<int>&arr,int l,int r)
    {
        if(l<r)
        {
            int mid = partition(arr, l, r);
            quicksort(arr, l,mid-1);
            quicksort(arr,mid+1,r);
        }
        return;
    }
};

7. 归并排序¶

缺点是 O(N)的空间复杂度，是外排序
1. 时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
适用场景：若 n 较大，并且要求排序稳定，则可以选择归并排序；