鸟语天空

快速排序(非递归实现)

作者：追风剑情 发布于：2019-3-17 17:21 分类：Algorithms

示例

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TSortTest
{
    class Program
    {
        static void Main(string[] args)
        {
            // 生成测试数据
            List<Foo> foos = new List<Foo>();
            Random random = new Random();
            for (int i = 0; i < 10; i++)
            {
                Foo foo = new Foo();
                foo.score = random.Next(0, 100);
                foos.Add(foo);
            }

            Foo[] arr = foos.ToArray();

            Console.WriteLine("排序前:");

            foreach (var foo in arr)
            {
                Console.Write(foo.score + " ");
            }

            QuickSortHelper<Foo>.Sort(arr, Compare);

            Console.WriteLine("\n排序后:");

            foreach (var foo in arr)
            {
                Console.Write(foo.score + " ");
            }

            Console.Read();
        }

        private static int Compare(Foo a, Foo b)
        {
            if (a.score > b.score)
                return 1;
            else if (a.score < b.score)
                return -1;
            return 0;
        }
    }

    // 测试类
    public class Foo
    {
        public int score;
    }

    /// <summary>
    /// 快速排序帮助类
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public sealed class QuickSortHelper<T>
    {
        private static Stack<Record> stack = new Stack<Record>();

        public delegate int Compare(T a, T b);

        /// <summary>
        /// 非递归实现快速排序
        /// </summary>
        /// <param name="arr">等排序数组</param>
        /// <param name="compareFun">比较函数</param>
        public static void Sort(T[] arr, Compare compareFun)
        {
            int left = 0;
            int right = arr.Length - 1;
            if (left >= right)
                return;

            // 主元位置
            int pivot = Partition(arr, left, right, compareFun);

            if (pivot - 1 > left)
            {
                stack.Push(new Record(left, pivot - 1));
            }

            if (pivot + 1 < right)
            {
                stack.Push(new Record(pivot + 1, right));
            }

            while (stack.Count > 0)
            {
                Record record = stack.Pop();
                pivot = Partition(arr, record.left, record.right, compareFun);
                if (pivot - 1 >= record.left)
                {
                    stack.Push(new Record(record.left, pivot - 1));
                }
                if (pivot + 1 <= record.right)
                {
                    stack.Push(new Record(pivot + 1, record.right));
                }
            }
        }

        /// <summary>
        /// 将主元arr[r]放到合适的位置
        /// </summary>
        /// <returns>返回主元所在的新位置</returns>
        private static int Partition(T[] arr, int p, int r, Compare compareFun)
        {
            T x = arr[r];//主元
            int i = p;
            for (int j = p; j < r; j++)
            {
                if (compareFun(arr[j], x) < 0)
                {
                    Exchange(arr, i, j);
                    i++;
                }
            }
            //将主元放入正确的位置
            //此时,主元左侧的数据都小于主元,主元右侧的数据都大于主元
            Exchange(arr, i, r);
            return i;
        }

        // 将第r号元素插入到i号位置,其它元素依次后移
        private static void Exchange(T[] arr, int i, int r)
        {
            if (i >= r)
                return;
            T x = arr[r];
            for (int j = r; j > i; j--)
            {
                arr[j] = arr[j - 1];
            }
            arr[i] = x;
        }

        public sealed class Record
        {
            public int left;
            public int right;

            public Record(int left, int right)
            {
                this.left = left;
                this.right = right;
            }
        }
    }
}

运行测试

标签: Algorithms