Data Structure & Algorithms

作者： toutou / 2024年4月18日

reference: 黑书，https://zhuanlan.zhihu.com/p/536470404

其实感觉没太大复习的必要了……不过主要的算法思想还是记忆一下，多刷leetcode保持手感吧！

第一部份：基础

这一部份主要复习算法性能分析和10大排序
时间复杂度（Time Complexity）:列出递推式，然后用主定理(Master theorem)解决，注意第二种情况的时候要多✖️logn。当然还有一写常见的递推式可以直接看出来时间复杂度。注意三个符号表示上界，下界，紧确界。单调性（monotonicity）,单调递增（monotonically increasing）。
插入排序（Insertion Sort）：最优O(N),最坏O(N^2),类比打牌边摸牌边整理牌。
归并排序（Merge Sort）：类比左右手摸切好的牌然后比较。
快速排序（Quick Sort）：选好一个pivot然后根据pivot分成两部份再递归下去
堆排序(Heap Sort)：建堆，取头节点，不断维护堆的排序过程
桶排序(Bucket Sort)：一个桶放一定范围的元素，空间换时间
冒泡排序(Bubble Sort)：不断把最大的元素沉底
选择排序(Selection Sort)：不断迭代选最小的元素
希尔排序(Shell Sort)：定一个gap数值，然后gap不断二分下来
基数排序(Radix Sort)：从最低位依次开始比较(个位->十位->百位->.....)
计数排序(Counting Sort)：最经典的用空间换时间

Insertion Sort

#include<bits/stdc++.h>
using namespace std;
void insertionSort(int arr[], int n){
    int i , j , key;
    for(int i = 1; i < n; i++){
        key = arr[i];
        j = i - 1;  // j指向已排好序的子数组的最后一个元素
        while(j >= 0 && arr[j] > key){ // 不断找key放下的位置
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;    // 放下key
    }
}

void printArray(int arr[], int n){
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printArray(arr, n);
    return 0;
}
//5 6 11 12 13
//最好情况：当输入数组已经是排序好的情况，插入排序只需要进行 n−1次比较，没有元素交换的操作。所以最好情况下的时间复杂度为 O(n)
//最坏情况：当输入数组是逆序的情况，每次插入都需要比较和移动所有的已排序元素。所以最坏情况下的时间复杂度为 O(n2)

Merge Sort

#include<bits/stdc++.h>
using namespace std;

void merge(int arr[], int l, int m, int r){
    int i, j , k;
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];  // 创建两个临时数组
    // 复制数据到临时数组
    for(int i = 0; i < n1; i++) L[i] = arr[l + i];
    for(int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    // 合并临时数组回原数组
    i = 0;
    j = 0;
    k = l;
    while(i < n1 && j < n2){
        if(L[i] < R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while(i < n1) arr[k++] = L[i++]; // 复制剩余的L[]，如果有的话
    while(j < n2) arr[k++] = R[j++]; // 复制剩余的R[]，如果有的话
}

void mergeSort(int arr[], int l, int r){
    if(l < r) {
        int m = l + (r - l) / 2;   // 找到中间索引
        mergeSort(arr, l, m);      // 分治两个子数组
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);      // 归并
    }
}
// 打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, arr_size - 1);
    cout << "排序后的数组：\n";
    printArray(arr, arr_size);
    return 0;
}
//排序后的数组：
//5 6 11 12 13
//归并排序的时间复杂度是比较稳定的，无论是最好情况、最坏情况，还是平均情况，时间复杂度都是（nlogn）

Quick Sort

#include<bits/stdc++.h>
using namespace std;

int partition(vector<int>& arr, int low, int high){
    int pivot = arr[high];
    int i = low - 1;
    for(int j = low; j < high; j++){
        if(arr[j] < pivot){
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high){
    if(low < high){
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main(){
    vector<int> arr = {38, 23, 10, 6, -100, 40};
    int n = (int)arr.size();
    quickSort(arr, 0, n - 1);
    for(auto x : arr) cout << x << " ";
    return 0;
}
//-100 6 10 23 38 40
//时间复杂度根据递归树深度，最深的时候就是已排好的数组，最好的时候每次都对半划分
//最坏O(n^2), 最优O(nlogn)

Heap Sort

#include<bits/stdc++.h>
using namespace std;
// 建的最大堆
void heapify(vector<int>& arr, int n, int i){
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if(left < n && arr[left] > arr[largest]) largest = left;
    if(right < n && arr[right] > arr[largest]) largest = right;
    if(largest != i){
        swap(arr[largest], arr[i]);
        heapify(arr, n, largest);    //递归下去，调整堆
    }
}

void heapsort(vector<int>& arr){
    int n = (int)arr.size();
    for(int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);    // 从非叶子节点开始建堆
    for(int i = n - 1; i >= 0; i--){
        swap(arr[i], arr[0]);   // 交换头节点
        heapify(arr, i, 0);     // 继续建堆，有在减小规模
    }
}

int main(){
    vector<int> arr = {-41, 27, 89, 0, 2, 7, 10};
    heapsort(arr);
    for(auto x : arr) cout << x << " ";
    return 0;
}
//-41 0 2 7 10 27 89
// 建堆O(N), 每次删除元素调整堆O(logN)
// 时间复杂度是稳定的O(NlogN)

Bubble Sort

#include<bits/stdc++.h>
using namespace std;
void bubbleSort(vector<int>& arr){
    int n = (int)arr.size();
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - i - 1; j++){
            if(arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
        }
    }
}
int main(){
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    for(auto x : arr) cout << x << " ";
    return 0;
}
//11 12 22 25 34 64 90
//最好情况O(N)：当输入数组已经是排序好的（即完全升序或降序），冒泡排序只需要进行一次遍历就可以确认排序已完成。
//最坏情况O(N^2)：当输入数组是完全反序的（即完全降序或升序）

Selection Sort

#include<bits/stdc++.h>
using namespace std;
void selectionSort(vector<int>& arr){
    int n = (int)arr.size();
    for(int i = 0; i < n - 1; i++){
        int min_idx = i; //找到最小元素的索引
        for(int j = i + 1; j < n; j++){
            // 更新最小元素索引
            if(arr[j] < arr[min_idx]) min_idx = j;
        }
        swap(arr[min_idx], arr[i]);
    }
}
int main(){
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    selectionSort(arr);
    for(auto x : arr) cout << x << " ";
    return 0;
}
//11 12 22 25 34 64 90
// 稳定的O(N^2)

Bucket Sort