快速排序(泛型版)

作者：追风剑情发布于：2019-3-15 23:08 分类：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);
 
            Console.WriteLine("\n排序后:");
 
            foreach (var foo in arr)
            {
                Console.Write(foo.score+" ");
            }
 
            Console.Read();
        }
    }
 
    public class QuickSortHelper<T> where T : IComparer<T>
    {
 
        public static void Sort(T[] arr)
        {
            RecursionSort(arr, 0, arr.Length - 1);
        }
 
        // 递归方式实现
        private static void RecursionSort(T[] arr, int p, int r)
        {
            if (p >= r) //结束递归
                return;
            int q = Partition(arr, p, r);
            RecursionSort(arr, p, q - 1); //对左侧排序
            RecursionSort(arr, q + 1, r); //对右侧排序
        }
 
        /// <summary>
        /// 将主元arr[r]放到合适的位置
        /// </summary>
        /// <returns>返回主元所在的新位置</returns>
        private static int Partition(T[] arr, int p, int r)
        {
            T x = arr[r];//主元
            int i = p;
            for (int j = p; j < r; j++)
            {
                if (arr[j].Compare(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 class Foo : IComparer<Foo>
    {
        public int score;
 
        public int Compare(Foo a, Foo b)
        {
            if (a.score > b.score)
                return 1;
            else if (a.score < b.score)
                return -1;
            return 0;
        }
    }
}