C++排序算法，把希尔排序和快速排序结合起来之后出错了

Question

代码是这样的：

void Sort(int TargetArr[], int StartPos, int EndPos) {
    EndPos--;//防止调用出数组外
    if (StartPos + 50 >= EndPos) {//如果数组大小小于等于50(较小)
        for (int i = StartPos + 1; i <= EndPos; i++) {//使用插入排序排完剩下的50个元素
            int Key = TargetArr[i];
            int j = i - 1;
            while (j >= StartPos && TargetArr[j] > Key) {
                TargetArr[j + 1] = TargetArr[j];
                j--;
            }
            TargetArr[j + 1] = Key;
        }
        return;
    }
    int MidNumPos = StartPos + (EndPos - StartPos) / 2;//三数取中
    if (TargetArr[StartPos] > TargetArr[MidNumPos]) {
        int SwapTemp = TargetArr[StartPos];
        TargetArr[StartPos] = TargetArr[MidNumPos];
        TargetArr[MidNumPos] = SwapTemp;
    }
    if (TargetArr[MidNumPos] > TargetArr[EndPos]) {
        int SwapTemp = TargetArr[MidNumPos];
        TargetArr[MidNumPos] = TargetArr[EndPos];
        TargetArr[EndPos] = SwapTemp;
        if (TargetArr[StartPos] > TargetArr[MidNumPos]) {
            int SwapTemp = TargetArr[StartPos];
            TargetArr[StartPos] = TargetArr[MidNumPos];
            TargetArr[MidNumPos] = SwapTemp;
        }
    }
    int Pivot = TargetArr[MidNumPos];//设置基准数
    int LessPivot = StartPos;//小于基准的边界
    int GreaterPivot = EndPos;//大于基准的边界
    int i = StartPos;//当前元素的索引

    while (i <= GreaterPivot) {
        if (TargetArr[i] < Pivot) {//将当前元素交换到小于基准的部分
            int SwapTemp = TargetArr[i];
            TargetArr[i] = TargetArr[LessPivot];
            TargetArr[LessPivot] = SwapTemp;
            LessPivot++;
            i++;
        } else if (TargetArr[i] > Pivot) {//将当前元素交换到大于基准的部分
            int SwapTemp = TargetArr[i];
            TargetArr[i] = TargetArr[GreaterPivot];
            TargetArr[GreaterPivot] = SwapTemp;
            GreaterPivot--;
        } else {
            i++;
        }
    }

    EndPos++;//这个时候已经不怕溢出了，因为希尔排序计算过程中已经-1了，所以再给他加回来
    //对较小的数组执行希尔排序，对较大的数组执行递归计算，既减少了快速排序的递归次数，又减少了希尔排序的调用次数，使得速度提高
    if (((LessPivot - 1) - StartPos) < (EndPos - (GreaterPivot + 1))) {
        //希尔排序start=StartPos, end=(LessPivot - 2)
        int n = (LessPivot - 2) - StartPos + 1;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = StartPos + gap; i <= (LessPivot - 2); i++) {
                int Temp = TargetArr[i];
                int j;
                for (j = i; j >= StartPos + gap && TargetArr[j - gap] > Temp; j -= gap) {
                    TargetArr[j] = TargetArr[j - gap];
                }
                TargetArr[j] = Temp;
            }
        }
        //递归较大数组
        Sort(TargetArr, GreaterPivot + 1, EndPos);
    } else if (((LessPivot - 1) - StartPos) > (EndPos - (GreaterPivot + 1))) {
        //希尔排序start=(GreaterPivot + 1), end=(EndPos - 1)
        int n = (EndPos - 1) - (GreaterPivot + 1) + 1;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = (GreaterPivot + 1) + gap; i <= (EndPos - 1); i++) {
                int Temp = TargetArr[i];
                int j;
                for (j = i; j >= (GreaterPivot + 1) + gap && TargetArr[j - gap] > Temp; j -= gap) {
                    TargetArr[j] = TargetArr[j - gap];
                }
                TargetArr[j] = Temp;
            }
        }
        //递归较大数组
        Sort(TargetArr, StartPos, LessPivot - 1);
    } else {//如果两数组大小相等，则一起递归
        Sort(TargetArr, StartPos, LessPivot - 1);
        Sort(TargetArr, GreaterPivot + 1, EndPos);
    }
}

现在排序出的结果只能大概排出一个范围，有些地方（相邻或者接近相邻）的地方会出错，能帮忙看看是哪里的问题嘛，非常感谢！

Answer 1

【以下回答由 GPT 生成】

问题分析:

该算法在使用插入排序时，只对大小小于等于50的数组进行排序，对于大于50的数组则使用快速排序进行排序。在快速排序的过程中使用了三数取中的方法选择基准元素，并采用分区的方式将小于基准的元素放在基准的左边，大于基准的元素放在基准的右边。但是，代码中存在一些问题。

问题一: 在选择基准元素时，正确的做法是选择数组的第一个元素作为基准。而在代码中使用的方法是将数组的第一个元素与中间位置的元素进行交换，这是错误的。

问题二: 在递归调用快速排序时，对小于基准的部分和大于基准的部分进行排序时，有一个下标错误。正确的做法是对小于等于基准的部分进行排序，并且递归调用的时候，范围应该是[StartPos, LessPivot-1]和[GreaterPivot+1, EndPos]，而不是[StartPos, LessPivot-1]和[GreaterPivot, EndPos]。

解决方案:

下面是修改后的代码:

void Sort(int TargetArr[], int StartPos, int EndPos) {
    EndPos--;
    if (EndPos - StartPos <= 50) { // 如果数组大小小于等于50(较小)
        for (int i = StartPos + 1; i <= EndPos; i++) { // 使用插入排序排完剩下的50个元素
            int Key = TargetArr[i];
            int j = i - 1;
            while (j >= StartPos && TargetArr[j] > Key) {
                TargetArr[j + 1] = TargetArr[j];
                j--;
            }
            TargetArr[j + 1] = Key;
        }
        return;
    }
    int MidNumPos = StartPos + (EndPos - StartPos) / 2; // 三数取中
    int Pivot = TargetArr[StartPos]; // 设置基准数
    int LessPivot = StartPos;
    int GreaterPivot = EndPos;
    int i = StartPos + 1; // 当前元素的索引

    while (i <= GreaterPivot) {
        if (TargetArr[i] < Pivot) { // 将当前元素交换到小于等于基准的部分
            int SwapTemp = TargetArr[i];
            TargetArr[i] = TargetArr[LessPivot+1];
            TargetArr[LessPivot+1] = SwapTemp;
            i++;
            LessPivot++;
        } else if (TargetArr[i] > Pivot) { // 将当前元素交换到大于基准的部分
            int SwapTemp = TargetArr[i];
            TargetArr[i] = TargetArr[GreaterPivot];
            TargetArr[GreaterPivot] = SwapTemp;
            GreaterPivot--;
        } else { // 当前元素等于基准元素
            i++;
        }
    }
    // 将基准元素放到正确的位置上
    int SwapTemp = TargetArr[StartPos];
    TargetArr[StartPos] = TargetArr[LessPivot];
    TargetArr[LessPivot] = SwapTemp;

    Sort(TargetArr, StartPos, LessPivot - 1); // 对小于等于基准的部分递归排序
    Sort(TargetArr, LessPivot + 1, EndPos); // 对大于基准的部分递归排序
}

优化方案:

除了上述解决方案中的修改，还可以对插入排序进行优化。可以使用希尔排序的增量序列来改进插入排序的性能。具体实现如下:

void ShellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

此外，还可以根据具体情况对算法进行调优，比如设置合适的基准选择方法、调整插入排序和快速排序的阈值等。

希望以上解决方案能解决您的问题，如有任何疑问，请随时追问。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7708264
• 你也可以参考下这篇文章：C++解决给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出
• 您还可以看一下 夏曹俊老师的C++ 11 14 17 20内存管理-指针、智能指针和内存池课程中的 图示进程的内存空间划分分析代码区_堆栈_内核空间小节, 巩固相关知识点
  
• 除此之外, 这篇博客: C++使用引用的方法向函数传递数组,避免因传入函数而导致退化为指针，正确在函数中计算数组的大小。中的 方法1——用基本语法 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^