C++不使用内置sort实现数组排序时运行异常问题求助

这是代码逻辑错误导致的，和编译器无关，核心问题是你写的冒泡排序存在数组越界访问的未定义行为。

具体错误分析 #

你提供的排序代码中，内层循环的边界判断写为i < size，当i = size - 1时，i + 1 = size，此时访问array[i+1]已经超出了数组的合法索引范围（数组索引从0到size-1）。越界访问的内存区域存储的数值是不确定的，对该区域的读写都会触发未定义行为：

• 升序看起来能正常运行只是侥幸，越界区域的数值刚好没有对排序结果产生明显影响
• 降序排序时数值异常、和升序搭配使用时首元素变成异常大的数值，都是越界读写修改了未知内存数据的典型表现

代码修正方案 #

基础修正版（解决越界问题） #

只需要修改内层循环的边界条件即可：

void min_sort(int array[], const unsigned int size){
    for(int k = 0; k < size; k++) {
        // 把i < size改成i < size - 1，避免访问i+1时越界
        for(int i = 0; i < size - 1; i++) {
            if(array[i] > array[i+1]){
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
         }
     }
}

优化版（减少冗余比较） #

每一轮外循环都会把当前未排序区间的最大元素沉到区间末尾，所以内层循环不需要每次都遍历到末尾：

void min_sort(int array[], const unsigned int size){
    for(int k = 0; k < size; k++) {
        // 末尾k个元素已经是有序的，不需要再比较
        for(int i = 0; i < size - 1 - k; i++) {
            if(array[i] > array[i+1]){
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
         }
     }
}

降序实现 #

修正边界后，只需要把比较符号改成小于号即可正常工作：

void max_sort(int array[], const unsigned int size){
    for(int k = 0; k < size; k++) {
        for(int i = 0; i < size - 1 - k; i++) {
            // 降序只需要修改比较符号
            if(array[i] < array[i+1]){
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
         }
     }
}

额外说明 #

你提到的「内置sort无法很好适配自定义object或struct场景」的说法是不准确的，C++标准库的std::sort支持传入自定义比较函数/仿函数/Lambda表达式，完全可以满足自定义类型的排序需求，非学习场景下不需要自己手动实现排序算法。

内容的提问来源于stack exchange，提问作者user16790886