[算法重构]排序 - rk3588's 小破站

趁着这学期学数据结构，还有某神秘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 partition(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_quick(vector<int>& arr,int low,int high) {
    if (low < high) {
        int mid = partition(arr, low, high);
        sort_quick(arr, low, mid-1);
        sort_quick(arr, mid+1, high);
    }
    
}

堆排序

思想：利用堆的特性进行排序。首先将待排序数组构建成一个大顶堆，此时堆顶元素为最大值。将堆顶与堆末尾元素交换，堆大小减1，然后对堆顶进行下沉调整，重复此过程直到堆为空。核心操作是下沉和建堆。

时间复杂度：

最好 O(n log n)
最坏 O(n log n)
平均 O(n log n)

空间复杂度：O(1)（原地排序，不依赖递归）

稳定性：不稳定（堆调整过程中可能改变相同元素的相对顺序）

void heapify(vector<int>& arr, int n, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != root) {
        swap(arr[root], arr[largest]);
        heapify(arr, n, largest);  // 递归下沉
    }
}

void sort_heap(vector<int>& arr) {
    int n = 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[0], arr[i]);
        heapify(arr, i, 0);
    }
}

注意事项：

建堆时从 n/2 - 1 开始，因为叶子节点无需堆化。
堆排序虽然时间复杂度很稳定，但实际常数较大，在数据量较小时不如快速排序快。
递归的 heapify 可以改为迭代版本以避免递归开销。

归并排序

思想：采用分治法。将数组递归地分成两半，分别排序，然后将两个有序子数组合并成一个有序数组。核心在于合并过程，需要借助额外的临时数组。

时间复杂度：

最好 O(n log n)
最坏 O(n log n)
平均 O(n log n)

空间复杂度：O(n) 需要与原数组等大的临时数组

稳定性：稳定

// 合并两个有序子数组
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    // 创建临时数组
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    
    // 合并
    int i = 0, j = 0, k = left;
    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++];
    while (j < n2) arr[k++] = R[j++];
}

void sort_merge(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;  // 防止溢出
    sort_merge(arr, left, mid);
    sort_merge(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

void sort_merge_wrapper(vector<int>& arr) {
    sort_merge(arr, 0, arr.size() - 1);
}