如何在C#中使用多线程实现奇偶排序算法？

问题根源 #

• 原逻辑死循环原因：result 变量仅在第一次发生交换时被设为false，后续循环从未重置为true，循环条件!result永远成立，线程不会退出。
• 加result = true后排序错误原因：
  1. 奇偶排序的核心规则是偶数索引交换趟和奇数索引交换趟必须交替执行，两个线程独立无协调运行时，会出现同时修改列表的竞态条件，数据读写不一致。
  2. 两个线程各自判断自己的交换状态，不知道对方是否修改过列表，可能某一趟自己没交换就提前退出，但另一线程刚做了交换需要继续迭代，导致排序未完成就终止。
  3. List<T>不是线程安全类型，多线程无锁读写会产生不可预期的结果。

修复方案 #

调整逻辑要点 #

1. 加全局锁保护列表操作，避免竞态条件
2. 协调两个线程执行顺序，严格交替执行偶数趟、奇数趟
3. 用全局标记统计每一轮（偶+奇趟）是否发生过交换，只有连续一轮都没有交换才判定排序完成

完整修复代码 #

using System;
using System.Collections.Generic;
using System.Threading;

class Program
{
    // 全局锁保护共享列表
    private static object _lockObj = new object();
    // 全局交换标记
    private static bool _hasSwap = false;
    // 线程同步事件：偶数趟完成、奇数趟完成
    private static ManualResetEventSlim _evenDone = new ManualResetEventSlim(false);
    private static ManualResetEventSlim _oddDone = new ManualResetEventSlim(false);

    static void Sort(int startPosition, List<int> list)
    {
        while (true)
        {
            bool currentSwap = false;
            lock (_lockObj)
            {
                for (int i = startPosition; i <= list.Count - 2; i += 2)
                {
                    if (list[i] > list[i + 1])
                    {
                        (list[i], list[i + 1]) = (list[i + 1], list[i]);
                        currentSwap = true;
                    }
                }
            }

            // 偶数线程执行完偶趟
            if (startPosition == 0)
            {
                lock (_lockObj)
                {
                    _hasSwap |= currentSwap;
                }
                _evenDone.Set();
                _oddDone.Wait();
                _oddDone.Reset();
            }
            // 奇数线程执行完奇趟
            else
            {
                lock (_lockObj)
                {
                    _hasSwap |= currentSwap;
                }
                _oddDone.Set();
                _evenDone.Wait();
                _evenDone.Reset();
            }

            // 本轮（偶+奇）无交换，排序完成，退出
            if (!_hasSwap)
            {
                break;
            }

            // 重置当前轮交换标记，准备下一轮
            if (startPosition == 0)
            {
                lock (_lockObj)
                {
                    _hasSwap = false;
                }
            }
        }
    }

    static void Main(string[] args)
    {
        bool isOddSorted = false;
        bool isEvenSorted = false;

        List<int> list = new List<int>();
        // Random实例要提到外面，避免循环快速生成相同随机数
        Random rnd = new Random();
        while (list.Count < 15)
        {
            list.Add(rnd.Next(0, 20));
        }

        Console.WriteLine("排序前：");
        Console.WriteLine(string.Join(",", list));

        var evenThread = new Thread(() =>
        {
            Sort(0, list);
            isEvenSorted = true;
        });
        evenThread.Start();

        var oddThread = new Thread(() =>
        {
            Sort(1, list);
            isOddSorted = true;
        });
        oddThread.Start();

        while (true)
        {
            if (isEvenSorted && isOddSorted)
            {
                Console.WriteLine("排序后：");
                Console.WriteLine(string.Join(",", list));
                break;
            }
        }

        // 释放同步资源
        _evenDone.Dispose();
        _oddDone.Dispose();
    }
}

内容的提问来源于stack exchange，提问作者C. H.