c#冒泡、快速、选择和插入排序算法的项目应用

c#冒泡、快速、选择和插入排序算法的项目应用2010-12-19 博客园 Jeff Wong在之前的一篇文章里，我们简单地实现了对一维数组的四种排序算法，但是在实际的项目中，我们排序的方式可能（几乎是一定）不止仅仅按照数字排序，我们常常按照合适的需要的排序方式进行排序，比如航班信息可能按时间排序，商品信息可能按价格排序等等。下面改进之前的那一篇“c#实现冒泡、快速、选择和插入排序算法”里的代码，实现可以对不同对象（实例中是Car ）的按照不同排序类型（实例中是价格和名称）的方式排序。好了，Code is cheap。看代码了：

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

namespace Sorter
{
    //声明委托，可以选择排序方式进行排序（而不局限于按整数排序）
    public delegate bool CompareOperation（object carPrev,object carNext）;
    /// <summary>
    /// 汽车类  用来构建汽车数组按照价格或者车名排序
    /// </summary>
    public class Car
    {
        private string name;
        public string Name
        {
            get { return name; }
            set { name = value; }
        }
        private decimal price;
        public decimal Price
        {
            get { return price; }
            set { price = value; }
        }
        public Car（string name, decimal price）
        {
            this.name = name;
            this.price = price;
        }
        public override string ToString（）
        {
            return string.Format（"name:{0},price: {1:c}", name, price）;
        }
        /// <summary>
        /// 将object转换为Car类，按照车名比较
        /// </summary>
        /// <param name="carPrev"></param>
        /// <param name="carNext"></param>
        /// <returns></returns>
        public static bool OrderByCarName（object objPrev, object objNext）
        {
            Car carPrev = （Car）objPrev;
            Car carNext = （Car）objNext;
            return （carPrev.name.CompareTo（carNext.name） < 0） ？ true : false;
        }

        /// <summary>
        /// 将object转换为Car类，按照价格比较
        /// </summary>
        /// <param name="carPrev"></param>
        /// <param name="carNext"></param>
        /// <returns></returns>
        public static bool OrderByCarPrice（object objPrev, object objNext）
        {
            Car carPrev = （Car）objPrev;
            Car carNext = （Car）objNext;
            return （carPrev.price < carNext.price） ？ true : false;
        }
    }

    /// <summary>
    /// 冒泡排序
    /// </summary>
    public class BubbleSorter
    {
        static public void Sort（Object[] objArr, CompareOperation sortOp）
        {
            bool flag = false; //交换标志
            for （int i = 1; i < objArr.Length; i++） //最 多做objArr.Length-1趟排序
            {
                flag = false;
                for （int j = objArr.Length - 1; j >= i; j--） //对当前无序区自下向上扫描
                {
                    if （sortOp（objArr[j], objArr[j - 1]）） //当前无序区: 轻的在下面，“冒泡”到上面
                    {
                        object tmpObj = objArr [j];
                        objArr[j] = objArr[j - 1];
                        objArr[j - 1] = tmpObj;
                        flag = true;
                    }
                }
                if （！flag） //如果没有发生交换，终止算法 
                    return;
            }
        }
    }

    /// <summary>
    /// 快速排序
    /// </summary>
    public class QuickSort
    {
        public static void Sort（object[] objArr, CompareOperation sortOp）
        {
            Sort（objArr, sortOp, 0, objArr.Length - 1）;
        }

        private static void Sort （object[] objArr, CompareOperation sortOp, int left, int right）
        {
            if （left < right）
            {
                Object middle = objArr[（left + right） / 2];
                int i = left - 1;
                int j = right + 1;
                while （true）
                {
                    while （sortOp（objArr[++i], middle）） ;

                    while （sortOp（middle, objArr[--j]）） ;

                     if （i >= j）
                        break;

                     Swap（objArr, i, j）;
                }
                Sort（objArr, sortOp, left, i - 1）;
                Sort（objArr, sortOp, j + 1, right）;
            }
        }

        private static void Swap （object[] objArr, int i, int j）
        {
            object tmpObj = objArr[i];
            objArr[i] = objArr[j];
            objArr[j] = tmpObj;
        }
    }

    /// <summary>
    ///  选择排序（Selection Sort）的基本思想是：每一趟从待排序的记 录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录 排序完毕。
    /// </summary>
    public class SelectionSort
    {
        static public void Sort（Object[] objArr, CompareOperation sortOp）
        {
            int min;
            for （int i = 0; i < objArr.Length - 1; i++） 
            {
                min = i;
                for （int j = i + 1; j < objArr.Length; j++）
                {
                    if （sortOp（objArr[j], objArr [min]））
                    {
                        min = j;
                    }
                }
                object tmpObj = objArr[i];
                objArr[i] = objArr[min];
                objArr[min] = tmpObj;
            }
        }
    }

    /// <summary>
    /// 插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法 。它的工作原理是通过构建有序序列，对于未排序数据，
    /// 在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在 实现上，通常采用in-place排序（即只需用到O（1）的额外空间的排序），
    /// 因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位 ， 为最新元素提供插入空间。
    /// </summary>
    public class InsertSort
    {
        static public void Sort（Object[] objArr, CompareOperation sortOp）
        {
            for （int i = 1; i < objArr.Length; i++） //i 从1开始
            {
                object t = objArr[i]; //标志当前未排序 数据
                int j = i;
                while （（j > 0） && （sortOp （t,objArr[j - 1]）））
                {
                    objArr[j] = objArr[j - 1];
                    j--;
                }
                objArr[j] = t; //在已排序序列中插入当前 值
            }
        }
    }