C#排序算法之冒泡排序、选择排序、插入排序

发布时间：2010年9月9日 / 分类：DOTNET / 13,054 次浏览 / 评论

这篇文章介绍C#实现的几种最简单的排序方法：冒泡排序、选择排序、插入排序，并简单测试了一下性能。排序在编程中占有很重要的位置，一定程度上体现了编程的功底。虽然学习过一段时间，感觉这东西总是记不住，时间长了就忘了或者搞混了。搞混了问题还不大，忘了就比较严重了。

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

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("冒泡排序：");
            BubbleSort();

            Console.WriteLine("插入排序：");
            InsertSort();
            Console.ReadLine();
        }

        /// <summary>
        /// 冒泡排序
        /// 外循环控制已排序部分的数量,内循环控制两两比较，交换元素位置
        /// </summary>
        static void BubbleSort()
        {
            int numberOfLoop = 0;
            int[] intArr = new int[] { 3, 2, 1, 6, 4, 8, 7, 9, 0, 5 };

            //未优化的冒泡排序
            //for (int i = 0; i < intArr.Length - 1; i++)
            //{
            //    for (int j = 0; j < intArr.Length - i - 1; j++)
            //    {
            //        numberOfLoop++;

            //        //两个数作比较，把小的排在前边，最大的就会走到最后
            //        if (intArr[j + 1] < intArr[j])
            //        {
            //            int temp = intArr[j + 1];
            //            intArr[j + 1] = intArr[j];
            //            intArr[j] = temp;
            //        }
            //    }
            //}

            //优化后的冒泡排序
            //判断本次排序是否进行过位置调换，如果没有说明不用排序了
            for (int i = 0; i < intArr.Length - 1; i++)
            {
                bool flag = true;
                for (int j = 0; j < intArr.Length - i - 1; j++)
                {
                    numberOfLoop++;

                    //两个数作比较，把小的排在前边，最大的就会走到最后
                    if (intArr[j + 1] < intArr[j])
                    {
                        int temp = intArr[j + 1];
                        intArr[j + 1] = intArr[j];
                        intArr[j] = temp;
                        flag = false;
                    }
                }

                if (flag)
                {
                    break;
                }
            }

            DisplaySortResult(numberOfLoop, intArr);
        }

        /// <summary>
        /// 选择排序
        /// </summary>
        static void SelectSort()
        {

int numberOfLoop = 0;
            int[] intArr = new int[] { 0, 3, 2, 1, 6, 4, 7, 8, 9, 5 };
            int min;
            for (int i = 0; i < intArr.Length-1; i++)
            {
                min = i;
                for (int j = i + 1; j < intArr.Length; j++)
                {
                    numberOfLoop++;

                    //获取最小的
                    if (intArr[min] > intArr[j])
                    {
                        min = j;
                    }
                }

                if (min != i)
                {
                    //交换位置
                    int temp = intArr[i];
                    intArr[i] = intArr[min];
                    intArr[min] = temp;
                }
            }
            DisplaySortResult(numberOfLoop, intArr);
        }

        /// <summary>
        /// 直接插入排序
        /// 复杂度不是固定的，逆序越多，复杂度越高
        /// </summary>
        static void InsertSort()
        {
            int numberOfLoop = 0;
            int[] intArr = new int[] { 3, 2, 1, 6, 4, 8, 7, 9, 0, 5 };
            for (int i = 1; i < intArr.Length; i++)
            {
                //处理第i个数，i之前的数字排列是有序的
                int j;
                int temp = intArr[i];
                //包含第i个数的前序列
                for (j = i; j > 0; j--)
                {
                    numberOfLoop++;

                    //比较第i个数与第j-1个数，如果第i个数小于第j-1个数，则i应该排在j-1的前边，将第j-1个数后移
                    //这样j-1的位置就是一个可以插入的位置，然后继续比较j-1前边的数，如果仍旧大于第i个数，则继续后移
                    //最后剩下一个位置，插入第i个数，这样包含i的前部分的序列就是有序的了。
                    if (intArr[j - 1] > temp)
                    {
                        intArr[j] = intArr[j - 1];
                    }
                    else
                    {
                        break;
                    }
                }

                //最后一个位置设置成要排序数
                intArr[j] = temp;
            }

            DisplaySortResult(numberOfLoop, intArr);
        }

        /// <summary>
        /// 显示排序结果
        /// </summary>
        /// <param name="numberOfLoop"></param>
        /// <param name="intArr"></param>
        private static void DisplaySortResult(int numberOfLoop, int[] intArr)
        {
            foreach (int i in intArr)
            {
                Console.Write(i.ToString() + ",");
            }

            Console.WriteLine("");
            Console.WriteLine(numberOfLoop.ToString());
        }
    }
}

这篇文章用C#实现了几种基本的数据排序方式，这几种排序方式比较容易理解。下边是我做的测试：

1、20000个随机数测试