排序算法（2）

1. 快速排序（Quick Sort）

原理： 快速排序是一种分治算法，它通过选择一个基准元素（通常选择数组的第一个或最后一个元素），将数组分为左右两部分：左边的元素都小于基准值，右边的元素都大于基准值。接着对左右两部分递归执行同样的过程，最终数组会变得有序。

步骤：

1. 选择基准元素（例如数组的第一个元素）。
2. 将数组分为两部分：左边部分所有元素都小于基准值，右边部分所有元素都大于基准值。
3. 分别对左边和右边递归执行快速排序，直到子数组的长度为1。
4. 合并结果。

复杂度：

• 时间复杂度：最优和平均情况下为 O(n log n)，最差情况下为 O(n²)（例如，已经有序的数组每次都选择最大或最小的元素作为基准）。
• 空间复杂度：O(log n)（递归调用栈空间）。

示例： 假设我们要对数组 [8, 3, 7, 4, 2, 6, 5, 1] 进行快速排序：

1. 选择基准值 8，将其分为左边 [3, 7, 4, 2, 6, 5, 1] 和右边空集 []。
2. 对左边部分进行递归，基准值为 3，分为 [2, 1] 和 [7, 4, 6, 5]。
3. 重复递归直到每个部分都只剩一个元素，最后合并为 [1, 2, 3, 4, 5, 6, 7, 8]。

void QuickSort(int array[], int low, int high) {
    int i = low;
    int j = high;
    if(i >= j) {
        return;
    }

    int temp = array[low];  // 基准元素
    while(i != j) {
        while(array[j] >= temp && i < j) {
            j--;  // 从右向左找小于基准的数
        }
        while(array[i] <= temp && i < j) {
            i++;  // 从左向右找大于基准的数
        }
        if(i < j) {
            swap(array[i], array[j]);  // 交换左右找到的两个元素
        }
    }

    // 将基准元素放到正确位置
    swap(array[low], array[i]);

    // 对基准元素左右的部分递归排序
    QuickSort(array, low, i - 1);
    QuickSort(array, i + 1, high);
}

---

2. 希尔排序（Shell Sort）

原理： 希尔排序是对插入排序的优化。插入排序在处理几乎有序的数组时表现非常好，但在乱序的数组中效率较低。希尔排序通过引入一个增量序列（如 n/2, n/4, ..., 1），对相隔这些增量的元素进行插入排序，从而将远距离元素先大致排序，最终使用插入排序将整个数组排好。

步骤：

1. 选择一个增量 gap，例如数组长度的一半。
2. 对每个间隔为 gap 的元素进行插入排序。
3. 缩小 gap，重复步骤2，直到 gap 为 1。
4. 当 gap = 1 时，整个数组已经大部分有序，最后进行一次标准的插入排序即可。

复杂度：

• 时间复杂度：取决于增量序列，平均复杂度为 O(n log n)，最差复杂度为 O(n²)。
• 空间复杂度：O(1)。

示例： 假设我们要对数组 [8, 1, 5, 2, 6, 3, 45, 6, 7] 进行希尔排序，初始 gap = n/2 = 4：

1. 对于每隔4个位置的元素进行插入排序，结果为 [6, 1, 5, 2, 7, 3, 45, 6, 8]。
2. 将 gap 减小为 2，继续对每隔2个位置的元素进行插入排序，结果为 [5, 1, 6, 2, 7, 3, 8, 6, 45]。
3. 最后 gap = 1，对相邻元素进行插入排序，最终结果为 [1, 2, 3, 5, 6, 6, 7, 8, 45]。

void ShellSort(vector<int> & array){
    int len = array.size();
    int currentVlaue, gap = len / 2;

    while(gap > 0){
        for (int i = gap; i < len; ++i) {
            currentVlaue = array[i];
            int preindex = i - gap;

            // 插入排序部分
            while (preindex >= 0 && array[preindex] > currentVlaue) {
                array[preindex + gap] = array[preindex];
                preindex -= gap;
            }
            array[preindex + gap] = currentVlaue;
        }

        cout << "当前增量为: " << gap << endl;
        for (auto c : array) {
            cout << c << " ";
        }
        cout << endl;

        gap /= 2;  // 缩小增量
    }
}

---

3. 归并排序（Merge Sort）

原理： 归并排序也是一种分治算法，它将数组一分为二，分别对两部分进行排序，然后再将两个已经排好序的数组合并成一个有序数组。归并排序的特点是其稳定性和 O(n log n) 的时间复杂度。

步骤：

1. 将数组递归地分为两部分，直到每个部分的长度为1。
2. 将两个排好序的数组合并成一个有序数组。
3. 重复合并操作，直到所有部分合并为一个有序数组。

复杂度：

• 时间复杂度：O(n log n)。
• 空间复杂度：O(n)（需要额外的空间来存储合并后的数组）。

示例： 假设我们要对数组 [8, 1, 5, 2, 6, 3, 45, 6, 7] 进行归并排序：

1. 将数组分为 [8, 1, 5, 2] 和 [6, 3, 45, 6, 7]。
2. 继续分为 [8, 1], [5, 2], [6, 3], [45, 6, 7]。
3. 合并 [8, 1] 为 [1, 8]，合并 [5, 2] 为 [2, 5]，合并 [6, 3] 为 [3, 6]。
4. 最后合并为 [1, 2, 5, 8] 和 [3, 6, 6, 7, 45]，最终合并结果为 [1, 2, 3, 5, 6, 6, 7, 8, 45]。

// 合并两个已排序的数组
vector<int> merge_s(const vector<int>& left, const vector<int>& right) {
    vector<int> res(left.size() + right.size());
    int i = 0, j = 0, index = 0;

    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            res[index++] = left[i++];
        } else {
            res[index++] = right[j++];
        }
    }

    // 将左边剩余的元素加入结果数组
    while (i < left.size()) {
        res[index++] = left[i++];
    }

    // 将右边剩余的元素加入结果数组
    while (j < right.size()) {
        res[index++] = right[j++];
    }

    // 打印合并过程
    cout << "左数组: ";
    for (auto c : left) cout << c << " ";
    cout << endl;

    cout << "右数组: ";
    for (auto c : right) cout << c << " ";
    cout << endl;

    cout << "合并后的数组: ";
    for (auto c : res) cout << c << " ";
    cout << endl;
    cout << "-------" << endl;

    return res;
}

// 归并排序的递归实现
vector<int> MergeSort(vector<int>& array) {
    int size = array.size();
    if (size < 2) return array;  // 数组长度为 1 或 0 时，直接返回

    int mid = size / 2;
    vector<int> left(array.begin(), array.begin() + mid);
    vector<int> right(array.begin() + mid, array.end());

    // 递归对左右部分排序
    left = MergeSort(left);
    right = MergeSort(right);

    // 合并排序后的左右部分
    return merge_s(left, right);
}

---

总结：

1. 快速排序：基于分治的高效排序算法，适合大多数情况，但在极端情况下效率较低。
2. 希尔排序：插入排序的改进版本，通过缩小增量提前将远距离元素排序，提升效率。
3. 归并排序：稳定的分治排序算法，适合大数据量场景，空间复杂度较高。

这三种排序算法各有优缺点，可以根据数据规模、数据特点等需求选择合适的排序算法。例如，归并排序适合数据量较大且要求稳定排序的场景，而快速排序适合一般场景并且需要较高的排序效率。