[算法重构]排序

趁着这学期算法课多，还有某神秘CSP认证，对过往算法进行系统复习和完善，顺便记录下笔者理解

插入排序

思想：遍历数组元素，依次把每个元素插入到前面排好的数组中
最优O(n)，最坏O(n²)

void sort_insertion(vector<int> &arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

快速排序

思想：选择一个基准，把比基准大的和小的放在基准的两边，对两边再递归
最好O(nlogn),最坏O(n²)

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

待更新