如何用希尔排序、戈拉排序、快速排序仅对数组奇数元素排序

任务要求：使用希尔排序、梳排序（注：你提到的“戈拉排序”应为梳排序Comb Sort的翻译误差）和快速排序处理数组，但仅对数组中的奇数元素进行排序，偶数元素保持原有位置不变。已掌握冒泡排序的实现方式，但不清楚如何修改这三种排序算法，现有一段希尔排序的C++代码，需要修改以满足需求。

一、修改希尔排序实现仅排奇数 #

原希尔排序会对所有元素做比较交换，我们需要在逻辑中加入奇数判断，只处理奇数元素，同时修正原代码的语法和索引偏差问题：

#include <iostream>
using namespace std;

void print_array_num(int mas[], int size_mas) {
    for (int i = 0; i < size_mas; ++i) {
        cout << mas[i] << " ";
    }
    cout << endl;
}

void shell_Sort_odd_only(int mas[], int size_mas) {
    int incr = size_mas / 2;
    while (incr > 0) {
        for (int i = incr; i < size_mas; ++i) {
            int j = i - incr;
            // 向前跳过偶数，定位到前一个奇数
            while (j >= 0 && mas[j] % 2 == 0) {
                j -= incr;
            }
            // 当前元素是奇数时才执行插入逻辑
            if (mas[i] % 2 == 1) {
                int temp = mas[i];
                // 仅在奇数元素间比较移动
                while (j >= 0 && mas[j] > temp) {
                    mas[j + incr] = mas[j];
                    j -= incr;
                    while (j >= 0 && mas[j] % 2 == 0) {
                        j -= incr;
                    }
                }
                mas[j + incr] = temp;
            }
        }
        incr /= 2;
    }
    cout << "数组经过希尔排序（仅奇数）后：\n";
    print_array_num(mas, size_mas);
}

// 测试示例
int main() {
    int arr[] = {8, 3, 6, 5, 2, 9, 4, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "原数组：\n";
    print_array_num(arr, size);
    shell_Sort_odd_only(arr, size);
    return 0;
}

关键修改点： #

• 增加奇数判断逻辑，仅对奇数元素执行排序操作
• 遍历过程中自动跳过偶数，确保只在奇数元素间做比较和移动
• 修正原代码的起始索引偏差与语法错误（如缺少分号）

二、梳排序（Comb Sort）实现仅排奇数 #

梳排序是冒泡排序的改进版，通过递减步长减少逆序对。我们只需在比较交换时限制为奇数元素即可：

void comb_Sort_odd_only(int mas[], int size_mas) {
    int gap = size_mas;
    bool swapped = true;
    const double shrink_factor = 1.3; // 步长缩小因子

    while (gap > 1 || swapped) {
        if (gap > 1) {
            gap = static_cast<int>(gap / shrink_factor);
        }
        swapped = false;

        for (int i = 0; i + gap < size_mas; ++i) {
            // 仅当两个元素都是奇数时，才比较交换
            if (mas[i] % 2 == 1 && mas[i + gap] % 2 == 1) {
                if (mas[i] > mas[i + gap]) {
                    swap(mas[i], mas[i + gap]);
                    swapped = true;
                }
            }
        }
    }
    cout << "数组经过梳排序（仅奇数）后：\n";
    print_array_num(mas, size_mas);
}

核心逻辑： #

• 保留梳排序的步长递减逻辑
• 仅对步长两端的奇数元素执行比较交换操作，偶数元素完全不参与

三、快速排序实现仅排奇数 #

快速排序的核心是分区操作，我们需要修改分区逻辑，仅对奇数元素做分区，偶数保持原位：

// 找到从start开始的第一个奇数的索引
int find_next_odd(int mas[], int start, int end) {
    for (int i = start; i <= end; ++i) {
        if (mas[i] % 2 == 1) {
            return i;
        }
    }
    return end + 1; // 无奇数时返回超出范围的索引
}

// 仅处理奇数的分区函数
int partition_odd(int mas[], int low, int high) {
    int pivot_idx = find_next_odd(mas, low, high);
    if (pivot_idx > high) return low; // 区间无奇数，直接返回
    int pivot = mas[pivot_idx];
    swap(mas[pivot_idx], mas[high]); // 将基准移到末尾

    int i = low - 1;
    for (int j = low; j < high; ++j) {
        // 仅对小于等于基准的奇数元素做交换
        if (mas[j] % 2 == 1 && mas[j] <= pivot) {
            i++;
            swap(mas[i], mas[j]);
        }
    }
    swap(mas[i + 1], mas[high]);
    return i + 1;
}

void quick_Sort_odd_only(int mas[], int low, int high) {
    if (low < high) {
        int pi = partition_odd(mas, low, high);
        quick_Sort_odd_only(mas, low, pi - 1);
        quick_Sort_odd_only(mas, pi + 1, high);
    }
}

// 对外调用的包装函数
void quickSortOdd(int mas[], int size_mas) {
    quick_Sort_odd_only(mas, 0, size_mas - 1);
    cout << "数组经过快速排序（仅奇数）后：\n";
    print_array_num(mas, size_mas);
}

关键修改： #

• 新增find_next_odd函数定位基准奇数元素
• 分区过程仅对奇数元素做比较交换，偶数直接跳过
• 递归自动忽略无奇数的区间，避免无效计算

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