[算法重构]排序

趁着这学期学数据结构，还有某神秘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((n^{3/2}))，最坏O(n²)

void sort_shell(vector<int> &arr) {
    int n = arr.size();
    
    for (int gap = n / 2; gap > 0; gap /= 2) {
        
        for (int i = gap; i < n; i++) { //对每个分组分别排序
            int key = arr[i];
            int j = i;
            
            // 注意比较的是 j - gap 位置
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

冒泡排序

思想：相邻比较
最好O((n)),最坏O(n²)

void sort_bubble_optimized(vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool sign = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                sign = 1;
            }
        }
        // 如果本轮没有交换，说明已经有序
        if (!sign) break;
    }
}

快速排序

思想：选择一个基准，把比基准大的和小的放在基准的两边，对两边再递归，这里基准值的选取非常关键，虽然大多数情况下随机取一个或者取头尾就够用了，但是如果希望进一步优化可以考虑取几个数拿到中值再去做比较，这也是工程常用的一种手段。
最好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);
    }
    
}

待更新