程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> 關於C# >> c#冒泡、快速、選擇和插入排序算法的項目應用

c#冒泡、快速、選擇和插入排序算法的項目應用

編輯:關於C#

在之前的一篇文章裡,我們簡單地實現了對一維數組的四種排序算法,但是 在實際的項目中,我們排序的方式可能(幾乎是一定)不止僅僅按照數字排序, 我們常常按照合適的需要的排序方式進行排序,比如航班信息可能按時間排序, 商品信息可能按價格排序等等。下面改進之前的那一篇“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; //在已排序序列中插入當前 值
            }
        }
    }

public class Program
    {
        public static void Main()
        {
            Car[] carArr ={
                new Car("Benz",210000), new Car("BMW",150000), new Car("VW",130000),
                 new Car("Ford",140000), new Car("Kia",58000), new Car("QQ",30000),
                 new Car("Fiat",200000), new Car("Toyota",170000), new Car("Mazda",140000),

            };
            CompareOperation sortOp = new CompareOperation (Car.OrderByCarPrice); //按照價格排序
            //CompareOperation sortOp = new CompareOperation(Car.OrderByCarName); //按照名稱排序
            //BubbleSorter.Sort(carArr, sortOp); //冒泡排序
            QuickSort.Sort(carArr, sortOp); //快速排序
            //SelectionSort.Sort(carArr, sortOp);//選擇排序
            //InsertSort.Sort(carArr, sortOp);//插入排序
            for (int i = 0; i < carArr.Length; i++)
            {
                Console.WriteLine(carArr[i].ToString ());
            }
            Console.Read();
        }
    }
}

小結:在實際的項目中,我們基本不用按照上面的方式寫排序 代碼,c#為我們定義了幾個泛型排序接口(IComparable,IComparer等),重新 實現接口中的方法,利用泛型的集合類的Sort方法就可以了。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved