波斯马BOSSMA Information Technology

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

发布时间:2010年9月9日 / 分类:DOTNET / 11,775 次浏览 / 评论

这篇文章介绍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个随机数测试

2、20000个随机字符测试

从上边的数据看选择排序执行交换的次数最少,插入排序执行比较的次数最少。插入排序用的时间最少,其次是选择排序,鸡尾酒排序,冒泡排序。没有经过大范围的验证,不保证每次都这样。

本博客所有文章如无特别注明均为原创。
复制或转载请以超链接形式注明转自波斯马,原文地址《C#排序算法之冒泡排序、选择排序、插入排序

关键字:

建议订阅本站,及时阅读最新文章!
【上一篇】 【下一篇】

发表评论