c#实现冒泡、快速、选择和插入排序算法

c#实现冒泡、快速、选择和插入排序算法2011-06-30 博客园 kine去年11月份利用冒泡排序，用js实现了一个机票查询结果按照机票的票面价格和出发日期的页面无刷新排序。这一段时间客户又要求改为按照实际支付价格和日期进行排序，匆匆改好以后，感觉自己的算法和数据结构的能力几乎荒废了（好像以前也没有过这种能力^_^）。这里整理一下常用的排序算法，用c#实现，以备日后再用。Code is cheap.看具体实现吧。

1.冒泡排序

将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"（冒泡因此得名）。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

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

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

        public class Program
        {
            public static void Main（）
            {
                int[] testArr = new int[] { 1, 5, 11, 6, 4, 21, 99, 2, 15, 11, 34, 0, 33, 47 };
                BubbleSorter sh = new BubbleSorter（）;
                sh.Sort（testArr）;
                for （int m = 0; m < testArr.Length; m++）
                    Console.Write（"{0} ", testArr[m]）;
                Console.Read（）;
            }
        }
    }
}

冒泡算法小结：

因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量flag,在每趟排序开始前，先将其置为false,若排序过程中发生了交换，则将其置为true.各趟排序结束时检查flag,若未曾发生过交换则终止算法，不再进行下一趟排序。（不加flag也可以实现排序，但是会造成不必要的循环和比较）。